Práctica 5: Clases de Grafos (Algoritmos III)

Ejercicio 01:

3*n = Σ_v 3 <= Σ_v d(v) = 2*m = 2*19 = 38
Entonces n <= 38/3 ∼ 12

Ejercicio 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 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 08:

a)
b)

Ejercicio 10:

a)
b)
c)

Ejercicio 11:

a)
b)

Ejercicio 13:

a)
b)

Ejercicio 15:

a)
b)

Ejercicio 16:

a)
b)
c)
d)

Ejercicio 19:

a)
b)
c)
d)
e)
f)
g)

Ejercicio 20:

a)
b)

Ejercicio 21:

a)
b)

Ejercicio 22:

a)
b)

Ejercicio 23:

a)
b)
c)
d)
e)
f)
g)

Ejercicio 25:

a)
b)

Ejercicio 28:

a)
b)
c)

Ejercicio 29:

a)
b)
c)

Ejercicio 30:

a)
b)
c)