Diferencia entre revisiones de «Práctica 6: Árboles (Algoritmos III)»

De Cuba-Wiki
Línea 20: Línea 20:
==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, 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, entonces las dos particiones forman un grafo bipartito.
<br>b) Si, el K<sub>2,1</sub>
<br>b) Si, el K<sub>2,1</sub> (Una raiz con dos hojas)


==Ejercicio 06.04:==
==Ejercicio 06.04:==

Revisión del 15:55 11 nov 2006

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, entonces las dos particiones forman un grafo bipartito.
b) Si, el K2,1 (Una raiz con dos hojas)

Ejercicio 06.04:

Ejercicio 06.05:

Ejercicio 06.06:

Ejercicio 06.07:

Ejercicio 06.08:

Ejercicio 06.09:


a)
b)
c)
d)
e)

Ejercicio 06.10:

Ejercicio 06.11:


a)
b)
c)

Ejercicio 06.12:


a)
b)

Ejercicio 06.13:

Ejercicio 06.14:


a)
b)

Ejercicio 06.15:


a)
b)

Ejercicio 06.16:

Ejercicio 06.17:


a)
b)

Ejercicio 06.18:


a)
b)
c)

Ejercicio 06.19:


a)
b)
c)
d)

Ejercicio 06.20:

Ejercicio 06.21:


a)
b)

Ejercicio 06.22:

Ejercicio 06.23:

Ejercicio 06.24: