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)
b)
c)

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.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)
Sea 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)