Práctica 9: Planaridad - Coloreo (Algoritmos III)

Ejercicio 09.02:

Si G es planar => m <= 3n-6

Si T es arbol => m = n-1

Hay que ver si n-1 <= 3n-6

n-1 <= 3n-6  <=>  5 <= 2n  

Esto vale para n > 2 . (Para n=1, n=2 son casos triviales)

Ejercicio 09.04:

a)
b)
c)

Ejercicio 09.08:

a)
b)

Ejercicio 09.09:

a)
b)
c)
d)

Ejercicio 09.10:

a)
b)

Ejercicio 09.11:

a)
b)

Ejercicio 09.12:

a)
b)

Ejercicio 09.14:

a)
b)

Ejercicio 09.17:

a)
b)
c)
d)

Ejercicio 09.19:

a)
b)
c)

Ejercicio 09.21:

a)
b)
c)

Ejercicio 09.22:

a)
b)
c)

Ejercicio 09.23:

a)
b)
c)

Ejercicio 09.25:

a)
b)

Ejercicio 09.26:

a)
b)
c)

Ejercicio 09.27:

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

Ejercicio 09.28:

a)
b)
c)
d)

Ejercicio 09.29:

a)
b)
c)
d)
e)

Ejercicio 09.31:

a)
b)

Ejercicio 09.33:

a)
b)