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 1: | Línea 1: | ||
==Ejercicio 06.01:== | ==Ejercicio 06.01:== | ||
<br>a) | <br>a) | ||
<br> | <br>Si es conexo entonces todos los vertices tienen grado >= 1 -> | ||
<br>n = Σ<sub>v</sub> 1 <= Σ<sub>v</sub> d(v) = 2*m = 2*20 = 40 | |||
<br>Entonces n <= 40 | |||
<br>b) | <br>b) | ||
Línea 12: | Línea 12: | ||
<br>-> Si G es Arbol tiene al menos un nodo de grado par | <br>-> Si G es Arbol tiene al menos un nodo de grado par | ||
<br>c) | <br>c) | ||
==Ejercicio 06.02:== | ==Ejercicio 06.02:== | ||
<br>a) Falso (K4 no tiene puentes y para todo v, d(v) = 3) | <br>a) Falso (K4 no tiene puentes y para todo v, d(v) = 3) | ||
<br>b) Si un grafo es conexo, la min. cantidad de ejes (sin ciclos) es n-1. Sea G' un arbol. Sean 2 vertices v,w en G'. Como G' es conexo -> Ex. Unico camino C de v a w, con lo cual C+(v,w) es un ciclo, y ya que antes no habia es el unico posible. -> G' tiene n ejes y un solo ciclo. | <br>b) Si un grafo es conexo, la min. cantidad de ejes (sin ciclos) es n-1. Sea G' un arbol. Sean 2 vertices v,w en G'. Como G' es conexo -> Ex. Unico camino C de v a w, con lo cual C+(v,w) es un ciclo, y ya que antes no habia es el unico posible. -> G' tiene n ejes y un solo ciclo. | ||
<br>c) Verdadero (K4 sin una diagonal, o sea:) | |||
<br>c) Verdadero: | <br>o-o | ||
<br>|\| | |||
<br>o-o | |||
==Ejercicio 06.03:== | ==Ejercicio 06.03:== | ||
<br>a) La idea informal es agarrar la raiz y ponerla en la primera particion, luego a sus hijos en la segunda, luego a sus hijos en la primera otra vez, etc etc.. Y como los hijos nunca estan conectados entre si, entonces las dos particiones forman un grafo bipartito. | <br>a) La idea informal es agarrar la raiz y ponerla en la primera particion, luego a sus hijos en la segunda, luego a sus hijos en la primera otra vez, etc etc.. Y como los hijos nunca estan conectados entre si, entonces las dos particiones forman un grafo bipartito. | ||
<br>b) Si, el K<sub>2,1</sub> (Una raiz con dos hojas) | <br>b) Si, el K<sub>2,1</sub> (Una raiz con dos hojas) | ||
==Ejercicio 06.04:== | ==Ejercicio 06.04:== | ||
==Ejercicio 06.05:== | ==Ejercicio 06.05:== | ||
Por induccion; | |||
* CB: n = 2 | |||
Hay un solo arbol posible (K2,1). Como tiene 2 hojas -> OK | |||
* PI: | |||
Sea G un arbol de 2 hojas y G'=G-v (sacamos un vertice v a G, que debera ser una hoja (sino queda un grafo no conexo -> no seria arbol). Como vale P(n-1), G' tiene 2 hojas (por HI), entonces al agregar una hoja se tendra la misma cantidad de hojas que antes o mayor -> OK | |||
==Ejercicio 06.06:== | ==Ejercicio 06.06:== | ||
Línea 49: | Línea 48: | ||
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:== | ||
==Ejercicio 06.09:== | ==Ejercicio 06.09:== | ||
<br>a | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
<br>d | <br>d) | ||
<br>e) | <br>e) | ||
==Ejercicio 06.10:== | ==Ejercicio 06.10:== | ||
==Ejercicio 06.11:== | ==Ejercicio 06.11:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 06.12:== | ==Ejercicio 06.12:== | ||
<br>a) | <br>a) | ||
Línea 91: | Línea 81: | ||
<br>b) | <br>b) | ||
==Ejercicio 06.18:== | ==Ejercicio 06.18:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 06.19:== | ==Ejercicio 06.19:== | ||
<br>a) | <br>a) | ||
Línea 117: | Línea 101: | ||
<br>-> T(Kruskal) = O(m log m + m*n) = O(m*n) | <br>-> T(Kruskal) = O(m log m + m*n) = O(m*n) | ||
<br>c) | <br>c) | ||
<br>d) | <br>d) | ||
Línea 131: | Línea 110: | ||
==Ejercicio 06.22:== | ==Ejercicio 06.22:== | ||
<pre> | <pre> | ||
Lema 1: T es | Lema 1: T es arbol y e no en E -> T+e tienen un ciclo C que contiene a e | ||
Dem: | Dem: | ||
e = (u,v). T es conexo -> Ex. camino C1 entre u y v. En T+e, C1+e forman un circuito que | e = (u,v). T es conexo -> Ex. camino C1 entre u y v. En T+e, C1+e forman un circuito que inclute a e. | ||
Lema 2: T es | Lema 2: T es arbol, T+e tiene un ciclo, T+e-e'con e y e' en C -> T+e-e' es arbol | ||
Dem: | Dem: | ||
* E(T+e-e') = n-1 + 1 - 1 = n-1 | * E(T+e-e') = n-1 + 1 - 1 = n-1 | ||
* Sup e'=(w1,w2). T+e tiene un ciclo que incluye a e' -> Ex. 2 caminos en T+e entre w1 y w2 -> T+e-e' tiene un camino entre w1 y w2 -> no se desconecto nada -> T+e-e' es conexo | * Sup e'=(w1,w2). T+e tiene un ciclo que incluye a e' -> Ex. 2 caminos en T+e entre w1 y w2 -> T+e-e' tiene un camino entre w1 y w2 -> no se desconecto nada -> T+e-e' es conexo | ||
-> T+e-e' es | -> T+e-e' es arbol | ||
</pre> | </pre> | ||
<br> Sup. que G tiene 2 AGMs, S y T -> | <br> Sup. que G tiene 2 AGMs, S y T -> Habra ejes en S y no en T, y viceversa | ||
<br> Sea | <br> Sea eS el menor eje que esta en S y no en T ->(Lema 1) T+eS tiene un ciclo C que contiene a eS | ||
<br> En C Ex. eT en T que no esta en S (en S no habia ciclos). Por HI l(eS) != l(eT) | |||
<br> Puede pasar que l(eS) > l(eT)? ABS (por ser el menor eje) -> l(eS) < l(eT) | |||
<br> En C Ex. eT en T que no esta en S (en S no | <br> -> l(T+eS-eT) = l(T)+l(eS)-l(eT) < l(T) -> AG es mas chico que T (ABS) | ||
<br> Puede pasar que l( | |||
<br> -> l(T+ | |||
<br> -> Ex. Unico AGM | <br> -> Ex. Unico AGM | ||
==Ejercicio 06.23:== | ==Ejercicio 06.23:== | ||
==Ejercicio 06.24:== | ==Ejercicio 06.24:== | ||