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