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

Ejercicio 09.02:

Si G es planar $\Rightarrow$ m $\leq$ 3n-6

Si T es arbol $\Rightarrow$ m = n-1

Hay que ver si n-1 $\leq$ 3n-6

n-1 $\leq$ 3n-6 $\Leftrightarrow$ 5 $\leq$ 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)