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 41: | Línea 41: | ||
==Ejercicio 09.02:== | ==Ejercicio 09.02:== | ||
<< Gente, para escribir eso, mejor dejen el ejercicio vacío; al menos así, no confunden a nadie. La primera resolución está mal. La segunda, es cualquier cosa. >> | |||
<br> Sea T arbol. T es planar <=> no contiene un subgrafo homeomorfo a K5 o K33. Como no son isomorfos (todo arbol tiene hojas -> hay vertices de grado 1, pero K5 y K33 no tienen) -> y no se pueden obtener de otro grafo mediante subdiv. elementales (ya que cualquier subdiv. de K5 o K33 tiene ciclos -> no se puede llegar a un arbol) entonces vale. | <br> Sea T arbol. T es planar <=> no contiene un subgrafo homeomorfo a K5 o K33. Como no son isomorfos (todo arbol tiene hojas -> hay vertices de grado 1, pero K5 y K33 no tienen) -> y no se pueden obtener de otro grafo mediante subdiv. elementales (ya que cualquier subdiv. de K5 o K33 tiene ciclos -> no se puede llegar a un arbol) entonces vale. | ||
<br> | <br> Por induccion. Sea T un arbol de k+1 nodos.Sea T'=T-v. Por HI T' es planar. | ||
Al agregar a v a T', en ningun momento hace falta re dibujar el grafo por lo tanto T es planar. (le hace falta chamuyo a la dem,casos base, pero para dar otra idea) | |||
==Ejercicio 09.03:== | ==Ejercicio 09.03:== | ||
<br>G planar y para todo v, d(v) >= 3 -> 2 = n-m+r y 3*n <= 2*m = Σd(v) -> n <= 2/3*m | <br>G planar y para todo v, d(v) >= 3 -> 2 = n-m+r y 3*n <= 2*m = Σd(v) -> n <= 2/3*m | ||
<br>-> 2 = n-m+r <= 2/3*m-m+r <=> 6 <= 2*m-3*m+3*r = 3*r-m <=> m <= 3*r-6 | <br>-> 2 = n-m+r <= 2/3*m-m+r <=> 6 <= 2*m-3*m+3*r = 3*r-m <=> m <= 3*r-6 | ||
Línea 93: | Línea 57: | ||
<br>b) Sup. que no. Entonces para todo v, d(v) >= 5 -> Σ d(v) = 2*m >= 5*n | <br>b) Sup. que no. Entonces para todo v, d(v) >= 5 -> Σ d(v) = 2*m >= 5*n | ||
<br> G es planar -> m <= 3*n-6 | <br> G es planar -> m <= 3*n-6 -> 2*(3*n-6) >= 2*m >= 5*n -> 6*n-12 >= 5*n -> n >= 12 -> ABS | ||
<br>c) Sup. G y Gc son planares | <br>c) Sup. G y Gc son planares | ||
Línea 256: | Línea 216: | ||
<br> Otra forma: | <br> Otra forma: | ||
Ir borrando | Ir borrando ejes, hasta que el subgrafo que queda al sacar cualquier eje queda critico. | ||
==Ejercicio 09.19:== | ==Ejercicio 09.19:== |