Edición de «Práctica 10: Coloreo (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 66: | Línea 66: | ||
==Ejercicio 10.06:== | ==Ejercicio 10.06:== | ||
<br>b) Si G es k-cromático entonces contiene algún subgrafo k-cromático y color crítico. Si G es color crítico entonces es trivial. Si G no es color crítico, existen nodos al ser removidos disminuyen la cantidad de colores y nodos que no. Los nodos que disminuyen la cantidad de colores hacen la implicación verdadera. Veamos que el caso que falta puede probarse por inducción en la cantidad de nodos. Se prueba el caso base con dos nodos. Luego por HI el grafo G con n-1 nodos contiene un subgrafo color crítico y k-cromático. Al quitar de G un nodo, si la cantidad de colores se redujo, entonces G era color crítico. Si no disminuyó la cantidad de colores, se obtuvo un grafo con un nodo menos que, por hipótesis inductiva, contiene un grafo que es color crítico. | <br>b) Si G es k-cromático entonces contiene algún subgrafo k-cromático y color crítico. Si G es color crítico entonces es trivial. Si G no es color crítico, existen nodos al ser removidos disminuyen la cantidad de colores y nodos que no. Los nodos que disminuyen la cantidad de colores hacen la implicación verdadera. Veamos que el caso que falta puede probarse por inducción en la cantidad de nodos. Se prueba el caso base con dos nodos. Luego por HI el grafo G con n-1 nodos contiene un subgrafo color crítico y k-cromático. Al quitar de G un nodo, si la cantidad de colores se redujo, entonces G era color crítico. Si no disminuyó la cantidad de colores, se obtuvo un grafo con un nodo menos que, por hipótesis inductiva, contiene un grafo que es color crítico. | ||
==Ejercicio 10.07:== | ==Ejercicio 10.07:== |