Edición de «Práctica 9: Planaridad - 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 308: | Línea 308: | ||
-> -1|V1|^2 + 8|V1| - 13 = 0. Pero no hay un numero entero que cumpla esto -> ABS | -> -1|V1|^2 + 8|V1| - 13 = 0. Pero no hay un numero entero que cumpla esto -> ABS | ||
Hay otra manera de resolver este punto. Suponemos que G es 2-Coloreable. Entonces G es bipartito. Como el enunciado dice que G es planar, y asumimos que es bipartito, G debe cumplir con m<=2n-4. (esta es una condiciòn de los grafos planares bipartitos). | Hay otra manera de resolver este punto. Suponemos que G es 2-Coloreable. Entonces G es bipartito (* Me parece que esta mal porque es al reves: si es bipartito entonces es 2 coloreable *). Como el enunciado dice que G es planar, y asumimos que es bipartito, G debe cumplir con m<=2n-4. (esta es una condiciòn de los grafos planares bipartitos). | ||
Como m=13 y n=8, m<=2n-4 <=> 13<=12, lo cual no es cierto. Luego nuestro supuesto de que G es bipartito es falso. | Como m=13 y n=8, m<=2n-4 <=> 13<=12, lo cual no es cierto. Luego nuestro supuesto de que G es bipartito es falso. | ||