Diferencia entre revisiones de «Práctica 6: Árboles (Algoritmos III)»
De Cuba-Wiki
Sin resumen de edición |
|||
| Línea 1: | Línea 1: | ||
==Ejercicio 01:== | ==Ejercicio 06.01:== | ||
<br>a) | <br>a) | ||
<br>Si es conexo entonces todos los vertices tienen grado >= 1 -> | <br>Si es conexo entonces todos los vertices tienen grado >= 1 -> | ||
| Línea 14: | Línea 14: | ||
<br>c) | <br>c) | ||
==Ejercicio 02:== | ==Ejercicio 06.02:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 03:== | ==Ejercicio 06.03:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 04:== | ==Ejercicio 06.04:== | ||
==Ejercicio 05:== | ==Ejercicio 06.05:== | ||
==Ejercicio 06:== | ==Ejercicio 06.06:== | ||
==Ejercicio 07:== | ==Ejercicio 06.07:== | ||
==Ejercicio 08:== | ==Ejercicio 06.08:== | ||
==Ejercicio 09:== | ==Ejercicio 06.09:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
| Línea 32: | Línea 32: | ||
<br>d) | <br>d) | ||
<br>e) | <br>e) | ||
==Ejercicio 10:== | ==Ejercicio 06.10:== | ||
==Ejercicio 11:== | ==Ejercicio 06.11:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 12:== | ==Ejercicio 06.12:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 13:== | ==Ejercicio 06.13:== | ||
==Ejercicio 14:== | ==Ejercicio 06.14:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 15:== | ==Ejercicio 06.15:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 16:== | ==Ejercicio 06.16:== | ||
==Ejercicio 17:== | ==Ejercicio 06.17:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 18:== | ==Ejercicio 06.18:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 19:== | ==Ejercicio 06.19:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
<br>d) | <br>d) | ||
==Ejercicio 20:== | ==Ejercicio 06.20:== | ||
==Ejercicio 21:== | ==Ejercicio 06.21:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 22:== | ==Ejercicio 06.22:== | ||
==Ejercicio 23:== | ==Ejercicio 06.23:== | ||
==Ejercicio 24:== | ==Ejercicio 06.24:== | ||
Revisión del 15:43 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)
b)
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)
