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 51: | Línea 51: | ||
<br> | <br> | ||
<br> Paso inductivo: | <br> Paso inductivo: | ||
<br>Sea T un árbol de k+1 vértices. | |||
<br>Sea T un árbol de k+1 | |||
<br>Sea T' = T - (w,v), con v una hoja de T. | <br>Sea T' = T - (w,v), con v una hoja de T. | ||
<br | <br>Por HI, T' es planar. | ||
<br> | <br>Llamemos R a una región de la representación planar de T' que tiene a w en su frontera. | ||
<br>Luego, podemos | <br>Luego, podemos añadir a v dentro de dicha región y unirlo con w mediante una arista. | ||
<br>De esta forma obtenemos una representación planar de T. | <br>De esta forma obtenemos una representación planar de T. | ||
<br>Entonces T es planar, como queríamos probar. | <br>Entonces T es planar, como queríamos probar. | ||
==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 |