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.03:

G planar -> 2 = n-m+r
-> 3*r <= 2*m = Σd(v) -> r <= 2/3*m
-> 2 = n-m+r <= n-m+2/3*m <=> 6 <= 3*n-3*m+2*m = 3*n-m <=> m <= 3*n-6

Ejercicio 09.04:

a) Es trivial para n = 1, 2. Si n = 3, como G es planar -> m <= 3*n-6 ->
k*n <= Σ d(v) = 2*m <= 6*n-12 -> k <= 5 -> Ex. un vertice con grado <= 5
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)