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 18: | Línea 18: | ||
<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: | Esta demostración no es correcta (la dejo porque es lo primero que uno esta tentado a hacer). La falla esta en que estamos asumiendo que la unica manera de armar un grafo conexo de n ejes agregando un eje a un grafo inicial de n-1 ejes es suponiendo que este grafo inicial es un arbol (grafo conexo de n-1 ejes). El contraejemplo es el siguiente. | ||
o-o-o-o.....o-o-o que tiene n ejes sin embargo no tiene circuitos. | |||
<br>c) Verdadero (K4 sin una diagonal, o sea:) | |||
<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) | ||
Línea 60: | Línea 60: | ||
==Ejercicio 06.09:== | ==Ejercicio 06.09:== | ||
<br>a)Si, cualquier camino simple es un arbol binario (en particular uno con un numero par de vertices) | <br>a)Si, cualquier camino simple es un arbol binario (en particular uno con un numero par de vertices) | ||
<br>b)Un arbol m-ario tiene como maximo | <br>b)Un arbol m-ario tiene como maximo 1+Σ{i=1..h-1} m^(i+1) vertices | ||
<br>c)La cantidad maxima de hojas equivale a la cantidad de hojas del ultimo nivel, que es a lo sumo m^h hojas | <br>c)La cantidad maxima de hojas equivale a la cantidad de hojas del ultimo nivel, que es a lo sumo m^h hojas | ||
<br>d)l <= m^h -> log_m(l) <= log_m(m^h) = h*log_m(m) = h -> h >= log_m(l) | <br>d)l <= m^h -> log_m(l) <= log_m(m^h) = h*log_m(m) = h -> h >= log_m(l) | ||
Línea 71: | Línea 71: | ||
<br>a)Sup que no fuera un arbol. Entonces existe un eje que no es puente, con lo cual hay mas ejes que conectan dos comp. conexas -> Se puede obtener otro arbol generador pasando por otro eje que las conecta -> No se tiene un unico arbol generador -> ABS | <br>a)Sup que no fuera un arbol. Entonces existe un eje que no es puente, con lo cual hay mas ejes que conectan dos comp. conexas -> Se puede obtener otro arbol generador pasando por otro eje que las conecta -> No se tiene un unico arbol generador -> ABS | ||
<br>b)Creo que si se conocen todos los arboles generadores, uniendolos se pueden obtener todos los ejes que existian originalmente para cada vertice | <br>b)Creo que si se conocen todos los arboles generadores, uniendolos se pueden obtener todos los ejes que existian originalmente para cada vertice | ||
<br>c) | <br>c) | ||
==Ejercicio 06.12:== | ==Ejercicio 06.12:== | ||
Línea 91: | Línea 88: | ||
<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 108: | ||
<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 117: | ||
==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:== |