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:== | ||
<font color="red"> (Esta mal esto) | |||
<br> Sup. que no. Sea T arbol. Como T no es planar <math> \Rightarrow </math> m > 3n-6 | |||
<br> Como T es arbol <math> \Rightarrow </math> m = n-1 | |||
<br> Entonces n-1 <math> > </math> 3n-6 <=> 5 > 2n <=> n < 5/2 <math> \Rightarrow </math> n <math> \le </math> 2. | |||
<br> Pero entonces los unicos arboles posibles (K1 y K2) son planares <math> \Rightarrow </math> ABS | |||
</font> | |||
<br> A ver esta: | |||
<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> |