Práctica 6: Árboles (Algoritmos III)

Ejercicio 06.01:

a)
Si es conexo entonces todos los vertices tienen grado >= 1 ->
n = Σ_v 1 <= Σ_v d(v) = 2*m = 2*20 = 40
Entonces n <= 40

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

c)

Ejercicio 06.02:

a) Falso (K4 no tiene puentes y para todo v, d(v) = 3)
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.
c) Verdadero (K4 sin una diagonal, o sea:)
o-o
|\|
o-o

Ejercicio 06.03:

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.
b) Si, el K_2,1 (Una raiz con dos hojas)

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:

=>) Sea V={v1,..,vn} y G' = G sin un eje (Sup. que ese eje conectaba a vk con vk+1). Elegimos:
W1 = conj. de vertices alcanzables desde vk
W2 = conj. de vertices alcanzables desde vk+1
X = conj. de vertices no alcanzables desde vk o vk+1
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.

<=) 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.09:

a)
b)
c)
d)
e)

Ejercicio 06.11:

a)
b)
c)

Ejercicio 06.12:

a)
b)

Ejercicio 06.14:

a)
b)

Ejercicio 06.15:

a)
b)

Ejercicio 06.17:

a)
b)

Ejercicio 06.18:

a)
b)
c)

Ejercicio 06.19:

a)
Ti es un bosque de i ejes y n vertices -> T(n-1) es AG

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

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

c)
d)

Ejercicio 06.21:

a)
b)

Ejercicio 06.22:

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

Sup. que G tiene 2 AGMs, S y T -> Habra ejes en S y no en T, y viceversa
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
En C Ex. eT en T que no esta en S (en S no habia ciclos). Por HI l(eS) != l(eT)
Puede pasar que l(eS) > l(eT)? ABS (por ser el menor eje) -> l(eS) < l(eT)
-> l(T+eS-eT) = l(T)+l(eS)-l(eT) < l(T) -> AG es mas chico que T (ABS)
-> Ex. Unico AGM