Edición de «Final del 01/08/18 (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 23: | Línea 23: | ||
== Ejercicio 4 == | == Ejercicio 4 == | ||
Un grafo G es coloreable en forma única si todo coloreo con <math>\chi(G)</math> colores induce la misma partición de los vértices. | Un grafo G es coloreable en forma única si todo coloreo con <math>\chi(G)</math> colores induce la misma partición de los vértices. Mostarr si G es coloreable ne forma única el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida dpor los <math>\chi(G)</math>-colores es un subgrafo conexo. | ||
== Ejercicio 5 == | == Ejercicio 5 == | ||
Línea 58: | Línea 58: | ||
Tomar dos conjuntos <math>A</math> y <math>B</math> de la partición inducida <math>P</math>. | Tomar dos conjuntos <math>A</math> y <math>B</math> de la partición inducida <math>P</math>. | ||
Suponer que no son conexos. | Suponer que no son conexos. | ||
Pero entonces se les puede asignar el mismo color pues entre ellos no hay adyacencias en el grafo original y con el resto de los vértices no hay problemas pues pertenecen a otro conjunto, es decir tenían otro color. | Pero entonces se les puede asignar el mismo color pues entre ellos no hay adyacencias en el grafo original y con el resto de los vértices no hay problemas pues pertenecen a otro conjunto, es decir tenían otro color. | ||
Línea 130: | Línea 92: | ||
<math> \sum\limits_{e \in SS_c} c(e) \leq \sum\limits_{e' \in S'S_c'} c(e') </math> | <math> \sum\limits_{e \in SS_c} c(e) \leq \sum\limits_{e' \in S'S_c'} c(e') </math> | ||
con <math>S_c = V\ | con <math>S_c = V\S</math> es decir, el complemento. | ||
si multiplicamos por una constante mayor que cero, no cambia nada: | si multiplicamos por una constante mayor que cero, no cambia nada: |