Diferencia entre revisiones de «Práctica 6: Árboles (Algoritmos III)»
De Cuba-Wiki
| Línea 1: | Línea 1: | ||
==Ejercicio 01:== | ==Ejercicio 01:== | ||
<br>a) | <br>a) | ||
Si es conexo entonces todos los vertices tienen grado >= 1 -> | <br>Si es conexo entonces todos los vertices tienen grado >= 1 -> | ||
n = Σ<sub>v</sub> 1 <= Σ<sub>v</sub> d(v) = 2*m = 2*20 = 40 | <br>n = Σ<sub>v</sub> 1 <= Σ<sub>v</sub> d(v) = 2*m = 2*20 = 40 | ||
Entonces n <= 40 | <br>Entonces n <= 40 | ||
<br>b) | <br>b) | ||
Si G es arbol -> m = n-1 -> n = m+1 = Par+Impar = Impar | <br>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 -> | <br>Sup que todos los grados son impares. Entonces todos los grados se pueden escribir como di = <br>2*ki+1 para algun ki -> | ||
Σ<sub>v</sub> d(v) = Σ<sub>v</sub> (2*ki+1) = 2*Σ<sub>v</sub> ki + n = Par + Impar = Impar | <br>Σ<sub>v</sub> d(v) = Σ<sub>v</sub> (2*ki+1) = 2*Σ<sub>v</sub> ki + n = Par + Impar = Impar | ||
Pero Σ<sub>v</sub> d(v) = 2*m -> Impar = Par ABS | <br>Pero Σ<sub>v</sub> d(v) = 2*m -> Impar = Par ABS | ||
-> Si G es Arbol tiene al menos un nodo de grado par | <br>-> Si G es Arbol tiene al menos un nodo de grado par | ||
<br>c) | <br>c) | ||
Revisión del 15:27 11 nov 2006
Ejercicio 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 02:
a)
b)
c)
Ejercicio 03:
a)
b)
Ejercicio 04:
Ejercicio 05:
Ejercicio 06:
Ejercicio 07:
Ejercicio 08:
Ejercicio 09:
a)
b)
c)
d)
e)
Ejercicio 10:
Ejercicio 11:
a)
b)
c)
Ejercicio 12:
a)
b)
Ejercicio 13:
Ejercicio 14:
a)
b)
Ejercicio 15:
a)
b)
Ejercicio 16:
Ejercicio 17:
a)
b)
Ejercicio 18:
a)
b)
c)
Ejercicio 19:
a)
b)
c)
d)
Ejercicio 20:
Ejercicio 21:
a)
b)
