Edición de «Práctica 6: Árboles (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 49: | Línea 49: | ||
Por induccion: | Por induccion: | ||
* CB: n = 1. ! | * CB: n = 1. ! | ||
* PI: | * PI: | ||
Sea G un arbol de n vertices, y G' arbol = G-v / v es hoja. Por HI, Gc' es conexo o tiene un vertice aislado y el resto forma un subgrafo completo. Agregamos el vertice v que sacamos. Como cada hoja tiene un solo padre, en Gc esa hoja estara conectada con todos los vertices salvo el padre. De aqui sale que: | <br>Sea G un arbol de n vertices, y G' arbol = G-v / v es hoja. Por HI, Gc' es conexo o tiene un vertice aislado y el resto forma un subgrafo completo. Agregamos el vertice v que sacamos. Como cada hoja tiene un solo padre, en Gc esa hoja estara conectada con todos los vertices salvo el padre. De aqui sale que: | ||
<br> Si Gc' era conexo, Gc tambien lo sera ya que v estara conectado a otro vertice w de Gc'. Entonces para llegar a v, se podra llegar por el mismo camino que se llegaba a w. Todo esto ocurre salvo que el unico vertice de Gc' sea el padre de v, caso en que se cumple la otra propiedad. | |||
<br> Si Gc' tenia un vertice aislado, entonces v estara conectado a todos los vertices del subgrafo completo, lo cual hara que en Gc' este el mismo vertice aislado que en G', entonces en G', v estara conectado con el vertices que estaba aislado en Gc' y con vertices del subgrafo completo en Gc'. Esto hara que G' sea conexo (Salvo en el caso que el padre de v sea el subgrafo completo de Gc') | |||
==Ejercicio 06.08:== | ==Ejercicio 06.08:== |