Práctica 5: Clases de Grafos (Algoritmos III)
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)