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 60: | Línea 60: | ||
Se puede hacer con 3 colores: | Se puede hacer con 3 colores: | ||
Color 1: A,B,H | Color 1: A,B,H | ||
Color 2: D,G | Color 2: D,G | ||
Color 3: C,E,F | Color 3: C,E,F | ||
==Ejercicio 10.06:== | ==Ejercicio 10.06:== | ||
Línea 106: | Línea 106: | ||
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: |