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 58: | Línea 58: | ||
<br>Colores = Frecuencias | <br>Colores = Frecuencias | ||
W(G)<=X(G)<=D(G)+1 | |||
3<=X(G)<=7 | |||
3<=X(G)<=4 (planar) | |||
X(G)=4 | |||
A(2)-B(2)-C(2)-D(1)-E(2)-F(3)-G(4)-H(3) | |||
==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:== | ||
Línea 91: | Línea 88: | ||
==Ejercicio 10.08:== | ==Ejercicio 10.08:== | ||
Por induccion: | |||
* CB n = 2 ! | |||
* PI: | |||
Sea G' = G-v (G sin el vertice v). Agregamos el vertice. Si X(G') < X(G), G era k-critico y listo. Si no, X(G') = X(G), con lo cual, si G' tenia un subgrafo k-critico, G tambien lo tiene -> OK | |||
<br> Otra forma: | |||
Ir borrando vértices, hasta que el subgrafo que queda al sacar cualquier vertice queda critico. | |||
==Ejercicio 10.09:== | ==Ejercicio 10.09:== | ||
<br>a) | <br>a) | ||
<br>=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS | <br>=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS | ||
Línea 100: | Línea 102: | ||
<br>b) Con BFS (si llego a un vertice marcado y se quiere pintar con el mismo color -> no es 2-coloreable) | <br>b) Con BFS (si llego a un vertice marcado y se quiere pintar con el mismo color -> no es 2-coloreable) | ||
<br>c) O(n+m) | <br>c) O(n+m) | ||
==Ejercicio 10.10:== | |||
El grafo de Grotzsch. (Es el grafo de Mycielski 4, M_4.) | |||
==Ejercicio 10.11:== | ==Ejercicio 10.11:== | ||
Línea 106: | Línea 111: | ||
X(G) = X(Gc) = 1 -> 2 <= 2 OK | X(G) = X(Gc) = 1 -> 2 <= 2 OK | ||
* PI: | * PI: | ||
Saco un vertice -> G' = G-v | |||
<br>X(G)+X(Gc) = X(G')+X(Gc')+k (k cte.). Separamos en casos: | |||
<br>1. X(G) = X(G') o X(Gc) = X(Gc') -> k <= 1 -> X(G)+X(Gc) <= X(G')+X(Gc')+1 <= (HI) n+1 OK | |||
<br>X(G)+X(Gc) = X(G')+X( | <br>2. dG(v) >= X(G') y dGc(v) >= X(Gc') -> | ||
<br> | X(G') <= X(G) + 1 <= dG(v) + 1 y | ||
X(G'c) <= X(Gc) + 1 <= dGc(v) + 1 entonces | |||
<br> | <br>X(G') + X(G'c) <= dG(v) + dGc(v) + 2 (como dGc(v)=n-dG(v)-1) dG(v)+(n-dG(v)-1)+2 = n+1 OK | ||
<br> | |||
<br>b) Probamos ambas desigualdades: | <br>b) Probamos ambas desigualdades: |