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:== | ||
Línea 91: | Línea 92: | ||
==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 106: | ||
<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 115: | ||
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: |