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

Ejercicio 09.01:

1.No
2.
3.
4.
5.

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 y 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) Sup. que no. Entonces para todo v, d(v) >= 6. Como G es planar -> m <= 3*n-6.
6*n <= Σ d(v) = 2*m <= -> 6*n <= 2*m -> m >= 3*n ABS (m <= 3*n-6)
b)
c) Sup. G y Gc son planares
-> m(G) <= 3*n-6, m(Gc) = n(n-1)/2 - m(G) >= n(n-1)/2 - (3*n-6), y m(Gc) <= 3*n-6
-> n(n-1)/2 - (3*n-6) <= m(Gc) <= (3*n-6)
Con lo cual hay que ver para que valores se cumple n(n-1)/2 - (3*n-6) <= (3*n-6). Esto pasa si n^2-13*n+24 <= 0 <=> (n-10,77)(n-2,22) <= 0 -> n <= 10 y n >= 3. Pero por HI n >= 11 -> ABS

Ejercicio 09.06:

(Faltaria postear el dibujo de la "parrilla") Nota: p = puntos, l = cuerdas
G es planar -> r = m-n+2. Queremos averiguar m-n+1 (o sea, sin la region que cubre todo)
n = p + 2*l
2*mInt = Σ d(v) = 4*p + 2*l -> mInt = 2*p + l
m = mExt + mInt = 2*l + (2*p + l) = 3*l + 2*p
-> m-n+1 = (3*l + 2*p) - (p + 2*l) + 1 = l + p + 1

Ejercicio 09.08:

a)
b)

Ejercicio 09.09:

a)
b)
c)
d)

Ejercicio 09.10:

a)
b)

Ejercicio 09.11:

W(G) <= X(G) <= max d(G)+1

a)
1. 3 <= X(G) <= 5; X(G) =
2. 3 <= X(G) <= 6; X(G) =
3. 3 <= X(G) <= 5; X(G) =
4. 3 <= X(G) <= 4; X(G) = 3
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)