Diferencia entre revisiones de «Práctica 9: Planaridad - Coloreo (Algoritmos III)»
Línea 24: | Línea 24: | ||
<br> -> 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 | <br> -> 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 | ||
<br> -> n(n-1)/2 - (3*n-6) <= m(Gc) <= (3*n-6) | <br> -> n(n-1)/2 - (3*n-6) <= m(Gc) <= (3*n-6) | ||
<br> 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 | <br> 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<sup>2</sup>-13*n+24 <= 0 <=> (n-10,77)(n-2,22) <= 0 -> n <= 10 y n >= 3. Pero por HI n >= 11 -> ABS | ||
==Ejercicio 09.05:== | ==Ejercicio 09.05:== |
Revisión del 19:31 23 nov 2006
Ejercicio 09.01:
1.No (Es contraible a K5 por los ejes que tocan la "estrella" por afuera)
2.No (Es contraible a K5 por el eje que toca el triangulo por arriba)
3.
4.
5.No (Contiene un subgrafo contraible a K3,3)
Ejercicio 09.02:
Sup. que no. Sea T arbol. Como T no es planar m 3n-6 (Esta mal esto)
Como T es arbol m = n-1
Entonces n-1 3n-6 <=> 5 2n <=> n 5/2 n 2.
Pero entonces los unicos arboles posibles (K1 y K2) son planares ABS
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 n2-13*n+24 <= 0 <=> (n-10,77)(n-2,22) <= 0 -> n <= 10 y n >= 3. Pero por HI n >= 11 -> ABS
Ejercicio 09.05:
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.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:
Vertices = Comisiones
Ejes = Comisiones que comparten Legisladores
Ejercicio 09.14:
a)
b)
Ejercicio 09.15:
Ejercicio 09.16:
Ejercicio 09.17:
a) Sup. que no es conexo. Sea G' = G-C1, es decir, G sin la comp. conexa C1.
Como es color critico -> X(G') < X(G) y X(C1) < X(G)
Sea f1 un coloreo para C1' / ese coloreo se realiza con X(C1') colores. Definamos analogamente f2 para C1. Podemos construir un coloreo valido para G haciendo f1∪f2 -> tenemos un coloreo de max{ X(G'), X(C1) } -> X(G) < k -> ABS (porque X(G) = k)
b) Sup. Ex. v en V / d(v) < k-1. Hacemos G' = G-v
Como es color critico -> X(G') < X(G) (Obs: para todo G, X(G-v)=X(G)-1)
Sea f' un coloreo para G' con X(G)-1 colores. Si coloreamos a v con el color menor no usado por sus vecinos -> f(v) <= k-1 -> tenemos un coloreo para G con menos de k colores -> ABS
c) Sea C1 una comp. conexa de G-v -> X(C1+v) < X(G) y X(G-C1) < X(G)
Coloreamos en forma optima C1+v1 con f1 y G-C1 con f2.
- Si f1(v)=f2(v) -> tenemos un coloreo con menos de k colores -> ABS
- Si f1(v)!=f2(v) -> reordenamos los colores de f2 de forma que la particion en conj. indep. sea la misma y volvemos al caso f1(v)=f2(v) -> ABS
d)
Ejercicio 09.18:
Ejercicio 09.19:
a)
b)
c)
Ejercicio 09.20:
El grafo de Grotzsch (Jaja no es fruta, miren:)
http://www.informatyka.ibt.pl/matematyka/grafy/g_grotzsch.gif
Ejercicio 09.21:
a) Por induccion en n:
- CB: n = 1
X(G) = X(Gc) = 1 -> 2 <= 2 OK
- PI:
Saco un vertice -> G' = G-v
X(G)+X(Gc) = X(G')+X(Gc')+k (k cte.). Separamos en casos:
1. X(G) = X(G') o X(Gc) = X(Gc') -> k <= 1 -> X(G)+X(Gc) <= X(G')+X(Gc')+1 <= (HI) n+1 OK
2. dG(v) >= X(G') y dGc(v) >= X(Gc') -> X(G)+X(Gc) = X(G')+X(Gc')+2 <= dG(v)+dGc(v)+2 =
(como dGc(v)=n-dG(v)-1) dG(v)+(n-dG(v)-1)+2 = n+1 OK
b) Probamos ambas desigualdades:
- qvq n <= X(G)*X(Gc)
n <= X(G)*mayor particion del coloreo -> n <= X(G)*α(G) = X(G)*w(Gc)
X(G)*w(Gc) <= X(G)*X(Gc) -> n <= X(G)*X(Gc) OK
- qvq X(G)*X(Gc) <= [(n+1)/2]^2
Como para todo a,b: √(a*b) <= a+b/2 -> X(G)*X(Gc) <= [(X(G)+X(Gc))/2]^2 <= [(n+1)/2]^2 (por a)
c)
(X(G)+X(Gc))/2 >= (por b) √(X(G)*X(Gc)) >= √n -> X(G)+X(Gc) >= 2√n
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)