Edición de «Práctica 6: Árboles (Algoritmos III)»

{{Back|Algoritmos y Estructuras de Datos III}}

==Ejercicio 06.01:==
<br>a)
<br>Puede tener 21 vértices.

<br>b)
<br>Si G es arbol -> m = n-1 -> n = m+1 = Par+Impar = Impar
<br>Sup que todos los grados son impares. Entonces todos los grados se pueden escribir como di = 2*ki+1 para algun ki ->
<br>Σ<sub>v</sub> d(v) = Σ<sub>v</sub> (2*ki+1) = 2*Σ<sub>v</sub> ki + n = Par + Impar = Impar
<br>Pero Σ<sub>v</sub> d(v) = 2*m -> Impar = Par ABS
<br>-> Si G es Arbol tiene al menos un nodo de grado par

<br>c) Σ d(v)/n = 2 -> 2*m = Σ d(v) = 2*n -> m=n. Un grafo minimalmente conexo es un arbol, y este tiene n-1 ejes. Con lo cual, si se agrega un eje, queda m=n, y ademas se forma exactamente 1 ciclo.

==Ejercicio 06.02:==
<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.

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.

'''PREGUNTA: Oye tío! pues en ese contraejemplo tienes n ejes pero cuantos nodos tienes? n ó n+1?'''

<br>c) Verdadero (K4 sin una diagonal, o sea:)
<br>o-o
<br>|\|
<br>o-o

Hombre!, la pregunta es verdadera pero ahí veo 3 circuitos, si etiquetamos los nodos "a,b,c,d" en sentido horario, tenemos los ciclos: a-b-c-d-a; a-b-c-a; a-c-d-a. Yo propongo el siguiente ejemplo que va de coña:
<br>o-o
<br>| |
<br>o-o
<br>|\
<br>o-o

==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.

Pues vale, como un grafo es bipartito si y solo si todos sus circuitos tienen longitud par, como todo àrbol tiene todos sus circuitos pares entonces es bipartito. 
<br>todos == ninguno.
<br>b) Si, el K<sub>2,1</sub> (Una raiz con dos hojas)

==Ejercicio 06.04:==
==Ejercicio 06.05:==
Sea P=<v1,v2,..,vn> el camino simple de máxima longitud en un árbol T
Supongamos que v1 o vn tienen grado >1. 
Si es v1, sabemos que esta conectado a v2 y a otro w distinto de v2. Si w no pertenece a P, tendríamos un camino más largo (<w> U P), abs. Si w pertenece a P, tendríamos un ciclo (<w,v1,v2,...w>), también absurdo. Entonces v1 tiene que tener grado <=1, y como T es conexo, debe tener grado 1, o sea, es una hoja. Lo mismo podemos hacerlo para ver que vn debe ser una hoja.

==Ejercicio 06.06:==
<br> =>) Sea V={v1,..,vn} y G' = G sin un eje (Sup. que ese eje conectaba a vk con vk+1). Elegimos:
<br> W1 = conj. de vertices alcanzables desde vk
<br> W2 = conj. de vertices alcanzables desde vk+1
<br> X = conj. de vertices no alcanzables desde vk o vk+1
<br> Es claro que los vertices de G' = W1 U W2 U X. Tambien se ve que W1 U X = {} y W2 U X = {}. Ahora debemos analizar W1 ∩ W2.
* Si W1 ∩ W2 = {vi,..,vj}, entonces {vk,vi,..,vj,vk+1,vk} forma un ciclo en G -> ABS (era un bosque)
* Si W1 ∩ W2 = {}, podemos dividir W1 y W2 en 2 componentes conexas, las cuales formaban 1 sola componente conexa en G.

<br> <=) Sup que no, es decir, sacar un eje aumenta la cant. de componentes conexas de G (pero G tiene ciclos). Si se saca el eje que conecta vk con vk+1 aumenta la cant. de componentes conexas de G'. Pero si G tenia ciclos, uno de ellos podria ser {vk,vi,vk+1,vj,vk}. En este caso, en G' podria ir de vk a vk+1 del mismo modo. ABS (tengo la misma cant. de componentes conexas)

==Ejercicio 06.07:==
Por induccion:
* CB: n = 1. !
* 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:
* 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.
* 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:==
<br> =>) Como un arbol tiene m = n-1 ejes, y por otro lado sabemos que para todo grafo Σ d(v) = 2*m, entonces  si {d1,..,dn} es secuencia de arbol -> Σ d(v) = 2*m = 2*(n-1)
<br> <=) Σ d(v) = 2*(n-1) <=> m = n-1. Si m = n-1 y es conexo -> es arbol por definicion

==Ejercicio 06.09:==
<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 <math>1+\sum_{i=1}^{h} m^i = \sum_{i=0}^{h} m^i</math> vértices
<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>e)

==Ejercicio 06.10:==
(Facil Facil)

==Ejercicio 06.11:==
<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>c)

==Ejercicio 06.12:==
<br>a)
<br>b)
==Ejercicio 06.13:==
==Ejercicio 06.14:==
<br>a)
<br>b)
==Ejercicio 06.15:==
<br>a)
<br>b)
==Ejercicio 06.16:==
==Ejercicio 06.17:==
<br>a)
<br>b)
==Ejercicio 06.18:==
<br>a)
<br>b)
<br>c)
==Ejercicio 06.19:==
<br>a)
<br>Ti es un bosque de i ejes y n vertices -> T(n-1) es AG

<b>qvq T = {e1,..,e(n-1)} es AGM</b>
<br> Sea K = {k1,..,k(n-1)} el AG de Kruskal. Sup. que no es minimo
<br> T es AGM y ei <= ei+1 "mas parecido a K" (K∩T) es maxima)
<br> Sean i minimo / ei != ki, G = T+{ki}
<br> G tiene exactamente un ciclo C (ej 6.2 b). Como T es aciclico -> ki en C
<br> Sea eMAX el eje maximo de C. Como ki no forma un ciclo con e1,..,ei-1 -> eMAX != ki
<br> Tomemos T'=G-{eMAX} = T+{ki}-{eMAX} -> T' es un arbol
<br> W(T') = W(T)+l(ki)-l(eMAX) <= W(T) -> T' es AGM y es mas parecido a K (ABS)

<br>b)
<br>1. O(n) 2. O(m log m) 3. O(1) 4. O(1) n veces 5. O(1) n veces 6. O(n)
<br>-> T(Kruskal) = O(m log m + m*n) = O(m*n)

<br>c)
<br>d)

==Ejercicio 06.20:==
==Ejercicio 06.21:==
<br>a)
<br>b)
==Ejercicio 06.22:==
<pre>
Lema 1: T es arbol y e no en E -> T+e tienen un ciclo C que contiene a e
Dem:
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 arbol, T+e tiene un ciclo, T+e-e'con e y e' en C -> T+e-e' es arbol
Dem:
* 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
-> T+e-e' es arbol
</pre>

<br> Sup. que G tiene 2 AGMs, S y T -> Habra ejes en S y no en T, y viceversa
<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> -> l(T+eS-eT) = l(T)+l(eS)-l(eT) < l(T) -> AG es mas chico que T (ABS)
<br> -> Ex. Unico AGM

==Ejercicio 06.23:==
==Ejercicio 06.24:==


[[Category: Prácticas]]
@@ 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>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.
-[[Archivo:Algo3_P6_Ej6.2c_Grafo_m_n_2_circuitos.jpg]]
+'''PREGUNTA: Oye tío! pues en ese contraejemplo tienes n ejes pero cuantos nodos tienes? n ó n+1?'''
+<br>c) Verdadero (K4 sin una diagonal, o sea:)
+<br>o-o
+<br>|\|
+<br>o-o
+Hombre!, la pregunta es verdadera pero ahí veo 3 circuitos, si etiquetamos los nodos "a,b,c,d" en sentido horario, tenemos los ciclos: a-b-c-d-a; a-b-c-a; a-c-d-a. Yo propongo el siguiente ejemplo que va de coña:
+<br>o-o
+<br>| |
+<br>o-o
+<br>|\
+<br>o-o
 ==Ejercicio 06.03:==
@@ Línea 71: / Línea 84: @@
 <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>c) Encontré algo llamado "teorema de contracción-eliminación", que dice que T(G) = T(G-e) + T(G/e), con e cualquier arista del grafo, G/e es el grafo resultante de contraer la arista e (unir ambos extremos en un sólo nodo), y G-e el grafo resultante de eliminar la arista, como es usual.
+<br>c)
-También hay una manera sacando un cofactor de la matriz laplaciana (eliminando una fila y columna y haciendo el determinante de la matriz resultante)
-https://math.stackexchange.com/questions/90950/finding-the-number-of-spanning-trees-of-a-graph-g
-http://www.student.dtu.dk/~dawi/01227/01227-GraphTheory.pdf
 ==Ejercicio 06.12:==
@@ Línea 91: / Línea 101: @@
 <br>b)
 ==Ejercicio 06.18:==
-<br>a) Se pueden tomar ideas de este link:
+<br>a)
-http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml
-Tiene el algoritmo y una "live demo" en java donde se puede correr Prim sobre grafos y ver el seguimiento paso a paso.
-Además tiene el .java para compilar y jugar.
 <br>b)
 <br>c)
 ==Ejercicio 06.19:==
 <br>a)
@@ Línea 117: / Línea 121: @@
 <br>-> T(Kruskal) = O(m log m + m*n) = O(m*n)
-<br>c) Se pueden tomar ideas de este link:
+<br>c)
-http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml
-Tiene el algoritmo con el .java para compilar.
-Y además una "live demo" en java donde se puede correr Kruskal sobre grafos y ver el seguimiento paso a paso.
 <br>d)
@@ Línea 131: / Línea 130: @@
 ==Ejercicio 06.22:==
 <pre>
-Lema 1: T es árbol y e no en E -> T+e tienen un ciclo C que contiene a e
+Lema 1: T es arbol y e no en E -> T+e tienen un ciclo C que contiene a e
 Dem:
-e = (u,v). T es conexo -> Ex. camino C1 entre u y v. En T+e, C1+e forman un circuito que incluye a e.
+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 árbol, T+e tiene un ciclo, T+e-e' con e y e' en C -> T+e-e' es árbol
+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:
 * 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
--> T+e-e' es árbol
+-> T+e-e' es arbol
 </pre>
-<br> Sup. que G tiene 2 AGMs, S y T -> Habrá ejes en S y no en T, y viceversa
+<br> Sup. que G tiene 2 AGMs, S y T -> Habra ejes en S y no en T, y viceversa
-<br> Sea e el menor de los ejes que están en sólo uno de los dos árboles (e pertenece a S unión T menos S intersección T)
+<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> Sin perdida de generalidad, supongo que e pertenece a S (podría haber sido T)
+<br> En C Ex. eT en T que no esta en S (en S no habia ciclos). Por HI l(eS) != l(eT)
-<br>->(Lema 1) T+e tiene un ciclo C que contiene a e
+<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 había ciclos). Por HI l(e) != l(eT)
+<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(e) > l(eT)? ABS (por ser el menor eje) -> l(e) < l(eT)
-<br> (Lema 2) T+e-eT es árbol
-<br> -> l(T+e-eT) = l(T)+l(e)-l(eT) < l(T) -> AG es mas chico que T (ABS)
 <br> -> Ex. Unico AGM
-Otra opción es correr o generar el árbol generador mínimo con kruskal, aprovechando que al ser todos los ejes distintos kruskal se vuelve determinístico y no puede dar dos arboles distintos.
 ==Ejercicio 06.23:==