Diferencia entre revisiones de «Práctica 9: Planaridad - Coloreo (Algoritmos III)»
Línea 10: | Línea 10: | ||
<br> Si G es planar <math> \Rightarrow </math> <font color="red"> m <math> \le </math> 3n-6 </font> | <br> Si G es planar <math> \Rightarrow </math> <font color="red"> m <math> \le </math> 3n-6 </font> | ||
<br> Si T es arbol <math> \Rightarrow </math> m = n-1 | <br> Si T es arbol <math> \Rightarrow </math> m = n-1 | ||
<br> Hay que ver si n-1 <math> \le </math> 3n-6 | <br> Hay que ver si n-1 <math> \le </math> 3n-6 | ||
<br> n-1 <math> \le </math> 3n-6 <math> \Leftrightarrow </math> 5 <math> \le </math> 2n | <br> n-1 <math> \le </math> 3n-6 <math> \Leftrightarrow </math> 5 <math> \le </math> 2n | ||
<br> Esto vale para n <math> > </math> 2 . (Para n=1, n=2 son casos triviales) | <br> Esto vale para n <math> > </math> 2 . (Para n=1, n=2 son casos triviales) | ||
==Ejercicio 09.03:== | ==Ejercicio 09.03:== |
Revisión del 19:58 18 nov 2006
Ejercicio 09.01:
1.No
2.
3.
4.
5.
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.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) 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.05:
Ejercicio 09.06:
Ejercicio 09.07:
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.13:
Ejercicio 09.14:
a)
b)
Ejercicio 09.15:
Ejercicio 09.16:
Ejercicio 09.17:
a)
b)
c)
d)
Ejercicio 09.18:
Ejercicio 09.19:
a)
b)
c)
Ejercicio 09.20:
Ejercicio 09.21:
a)
b)
c)
Ejercicio 09.22:
a)
b)
c)
Ejercicio 09.23:
a)
b)
c)
Ejercicio 09.24:
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.30:
Ejercicio 09.31:
a)
b)
Ejercicio 09.32:
Ejercicio 09.33:
a)
b)