Diferencia entre revisiones de «Práctica 5: Clases de Grafos (Algoritmos III)»
Sin resumen de edición |
|||
Línea 1: | Línea 1: | ||
==Ejercicio 01:== | ==Ejercicio 05.01:== | ||
<br>3*n = Σ<sub>v</sub> 3 <= Σ<sub>v</sub> d(v) = 2*m = 2*19 = 38 | <br>3*n = Σ<sub>v</sub> 3 <= Σ<sub>v</sub> d(v) = 2*m = 2*19 = 38 | ||
<br>Entonces n <= 38/3 ∼ 12 | <br>Entonces n <= 38/3 ∼ 12 | ||
==Ejercicio 02:== | ==Ejercicio 05.02:== | ||
<br>a) | <br>a) | ||
<br>2*n = Σ<sub>v</sub> 2 = Σ<sub>v</sub> d(v) = 2*m = 2*12 = 24 | <br>2*n = Σ<sub>v</sub> 2 = Σ<sub>v</sub> d(v) = 2*m = 2*12 = 24 | ||
Línea 14: | Línea 14: | ||
<br>Entonces n = 40/k | <br>Entonces n = 40/k | ||
==Ejercicio 03:== | ==Ejercicio 05.03:== | ||
==Ejercicio 04:== | ==Ejercicio 05.04:== | ||
Sup. que todos los grados son distintos. Entonces los vertices tienen todos los grados posibles, de 0 a n-1. Pero si esto pasa, entonces tengo un vertice conectado a todos (el de grado n-1) y al mismo tiempo otro conectado a ninguno (el de grado 0). ABS | Sup. que todos los grados son distintos. Entonces los vertices tienen todos los grados posibles, de 0 a n-1. Pero si esto pasa, entonces tengo un vertice conectado a todos (el de grado n-1) y al mismo tiempo otro conectado a ninguno (el de grado 0). ABS | ||
=> Existen 2 vertices del mismo grado. | => Existen 2 vertices del mismo grado. | ||
==Ejercicio 05:== | ==Ejercicio 05.05:== | ||
Si esto pasara entonces Σ<sub>v</sub> d(v) = 2*m <=> 21 = 3*7 = Σ<sub>v</sub> 3 = 2*m <=> Impar = Par ABS => No es posible. | Si esto pasara entonces Σ<sub>v</sub> d(v) = 2*m <=> 21 = 3*7 = Σ<sub>v</sub> 3 = 2*m <=> Impar = Par ABS => No es posible. | ||
==Ejercicio 06:== | ==Ejercicio 05.06:== | ||
==Ejercicio 07:== | ==Ejercicio 05.07:== | ||
==Ejercicio 08:== | ==Ejercicio 05.08:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 09:== | ==Ejercicio 05.09:== | ||
==Ejercicio 10:== | ==Ejercicio 05.10:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 11:== | ==Ejercicio 05.11:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 12:== | ==Ejercicio 05.12:== | ||
==Ejercicio 13:== | ==Ejercicio 05.13:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 14:== | ==Ejercicio 05.14:== | ||
==Ejercicio 15:== | ==Ejercicio 05.15:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 16:== | ==Ejercicio 05.16:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
<br>d) | <br>d) | ||
==Ejercicio 17:== | ==Ejercicio 05.17:== | ||
==Ejercicio 18:== | ==Ejercicio 05.18:== | ||
==Ejercicio 19:== | ==Ejercicio 05.19:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
Línea 58: | Línea 58: | ||
<br>f) | <br>f) | ||
<br>g) | <br>g) | ||
==Ejercicio 20:== | ==Ejercicio 05.20:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 21:== | ==Ejercicio 05.21:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 22:== | ==Ejercicio 05.22:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 23:== | ==Ejercicio 05.23:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
Línea 75: | Línea 75: | ||
<br>f) | <br>f) | ||
<br>g) | <br>g) | ||
==Ejercicio 24:== | ==Ejercicio 05.24:== | ||
==Ejercicio 25:== | ==Ejercicio 05.25:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 26:== | ==Ejercicio 05.26:== | ||
==Ejercicio 27:== | ==Ejercicio 05.27:== | ||
==Ejercicio 28:== | ==Ejercicio 05.28:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 29:== | ==Ejercicio 05.29:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 30:== | ==Ejercicio 05.30:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) |
Revisión del 15:41 11 nov 2006
Ejercicio 05.01:
3*n = Σv 3 <= Σv d(v) = 2*m = 2*19 = 38
Entonces n <= 38/3 ∼ 12
Ejercicio 05.02:
a)
2*n = Σv 2 = Σv d(v) = 2*m = 2*12 = 24
Entonces n = 24/2 = 12
b)
3*n + 3 = 12 + 3*n - 9 = 3*4+(n-3)*3 = Σv d(v) = 2*m = 2*15 = 30
Entonces n = 27/3 = 9
c)
k*n = Σv d(v) = 2*m = 2*20 = 40
Entonces n = 40/k
Ejercicio 05.03:
Ejercicio 05.04:
Sup. que todos los grados son distintos. Entonces los vertices tienen todos los grados posibles, de 0 a n-1. Pero si esto pasa, entonces tengo un vertice conectado a todos (el de grado n-1) y al mismo tiempo otro conectado a ninguno (el de grado 0). ABS => Existen 2 vertices del mismo grado.
Ejercicio 05.05:
Si esto pasara entonces Σv d(v) = 2*m <=> 21 = 3*7 = Σv 3 = 2*m <=> Impar = Par ABS => No es posible.
Ejercicio 05.06:
Ejercicio 05.07:
Ejercicio 05.08:
a)
b)
Ejercicio 05.09:
Ejercicio 05.10:
a)
b)
c)
Ejercicio 05.11:
a)
b)
Ejercicio 05.12:
Ejercicio 05.13:
a)
b)
Ejercicio 05.14:
Ejercicio 05.15:
a)
b)
Ejercicio 05.16:
a)
b)
c)
d)
Ejercicio 05.17:
Ejercicio 05.18:
Ejercicio 05.19:
a)
b)
c)
d)
e)
f)
g)
Ejercicio 05.20:
a)
b)
Ejercicio 05.21:
a)
b)
Ejercicio 05.22:
a)
b)
Ejercicio 05.23:
a)
b)
c)
d)
e)
f)
g)
Ejercicio 05.24:
Ejercicio 05.25:
a)
b)
Ejercicio 05.26:
Ejercicio 05.27:
Ejercicio 05.28:
a)
b)
c)
Ejercicio 05.29:
a)
b)
c)
Ejercicio 05.30:
a)
b)
c)