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

Propiedades

(Para todo G: grafo)

• (DEF) G es planar <=> se puede dibujar en un plano sin que sus ejes se crucen
• (TEO) G es planar <=> no contiene un subgrafo homeomorfo a K5 o K3,3
• (TEO) G es planar y conexo -> n-m+r = 2
• (COR) G es planar y conexo -> 3*r >= 2*m y m <= 3*n-6

• (DEF) Numero cromatico X(G) = minimo # de colores para colorear los vertices de G
• (OBS)
  • 1. Si G es Kn -> X(G) = n
  • 2. Si G es bipartito y m>0 -> X(G) = 2
  • 3. Si G es un circuito simple par -> X(G) = 2
  • 4. Si G es un circuito simple impar -> X(G) = 3
  • 5. Si G es arbol y n>1 -> X(G) = 2
• (TEO) Si H es subgrafo de G -> X(H) <= X(G)
• (DEF) w(G) = # de vertices de una clique maxima de G
• (TEO) w(G) <= X(G) <= max d(v)+1
• (TEO) Si G es conexo y no un circuito impar ni es completo, tq max d(v) >= 3 -> X(G) <= max d(v)
• (TEO) Si G es planar -> X(G) <= 4

• (DEF) Polinomio cromatico PG(c) = # de formas de colorear los vertices de G un c colores
• (OBS)
  • 1. Si G no tiene ejes -> PG(c) = c^n
  • 2. Si G es Kn -> PG(c) = c(c-1)...(c-n+1)
  • 3. Si G es un camino simple de k vertices -> PG(c) = c(c-1)^(k-1)
  • 4. Si G esta formado por k comp. conexas -> PG(c) = PG1(c)*PG2(c)*...*PGk(c)

• (DEF) Indice cromatico X'(G) = minimo # de colores para colorear los ejes de G
• (TEO) X'(G) = max d(v) o X'(G) = max d(v)+1

Planaridad

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:

Sea T arbol. T es planar <=> no contiene un subgrafo homeomorfo a K5 o K33. Como no son isomorfos (todo arbol tiene hojas -> hay vertices de grado 1, pero K5 y K33 no tienen) -> y no se pueden obtener de otro grafo mediante subdiv. elementales (ya que cualquier subdiv. de K5 o K33 tiene ciclos -> no se puede llegar a un arbol) entonces vale.

Ejercicio 09.03:

G planar y para todo v, d(v) >= 3 -> 2 = n-m+r y 3*n <= 2*m = Σd(v) -> n <= 2/3*m
-> 2 = n-m+r <= 2/3*m-m+r <=> 6 <= 2*m-3*m+3*r = 3*r-m <=> m <= 3*r-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) Sup. que no. Entonces para todo v, d(v) >= 5 -> Σ d(v) = 2*m >= 5*n
G es planar -> m <= 3*n-6 -> 2*(3*n-6) >= 2*m >= 5*n -> 6*n-12 >= 5*n -> n >= 12 -> ABS

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²-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:

Sea G = K5. Si a G le agrego un nodo, (con o sin aristas) este grafo será no planar y no será homeomorfo a K3,3 ni a K5.

Ejercicio 09.06:

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
Se puede verificar en el grafico: 8 lineas + 16 puntos + 1 = 25 regiones

Ejercicio 09.07:

m <= 3*n-6 = 3*(n-2) <= k(n-2) (la minima longitud de un circuito es 3) (Ahora lo seguimos)

Ejercicio 09.08:

a) Hacemos la cuenta en cada componente conexa. El único problema es la región exterior, que se está contando muchas veces (k-1 veces de más):

.Σ{i=1..k} (ni - mi + ri) = n - m + (r+(k-1)) = 2k <=> n-m+r=k+1 <=> n-m+r-k = 1

b)Sumando la desigualdad de cada componente conexa parece que: m <= 3*n-6*k

El problema con esto es que está aplicando la fórmula a componentes conexas que podrían no cumplir la hipótesis de la desigualdad (que pide n >= 3). Por esa razón hay que tener cuidado con la justificación dada.

Ejercicio 09.09:

a)
2*m = d1*n -> m = d1*n/2
d2*r = 2*m = d1*n -> r = d1/d2*n

b)Usando que 1. d2*r = 2*m = d1*n y 2. n-m+r=2 -> r+n = 2+m:
n*(2*d1 + 2*d2 - d1*d2) = 2*d1*n + 2*d2*n - d2*d1*n =(1.) 2*d2*r + 2*d2*n - d2*2*m = 2*d2*(r+n) - d2*2*m =(2.) 2*d2*(2+m) - d2*2*m = 4*d2 + d2*2*m - d2*2*m = 4*d2

c)
(d1-2)(d2-2) = d1*d2 - 2*d1 - 2*d2 + 4 = d1*d2 - (2*d1 + 2*d2) + 4 = -(2*d1 + 2*d2 - d1*d2) + 4 < 0 + 4 = 4

d)Usando que d1 >= 3 y d2 >= 3:
(d1-2)(d2-2) < 4 <=> (d1-2)(d2-2) <= 3
-> 1 = (3-2) <= (d2-2) = (d2-2)(3-2) <= (d1-2)(d2-2) <= 3 -> 3 <= d2 <= 5
Entonces reemplazando los 3 casos de d2:
d2 = 3 -> (d1-2)(3-2) <= 3 <=> d1-2 <= 3 <=> d1 <= 5 -> 3 <= d1 <= 5
d2 = 4 -> (d1-2)(4-2) <= 3 <=> (d1-2)*2 <= 3 <=> d1-2 <= 3/2 ~ 1 -> d1 <= 3 -> d1 = 3
d2 = 5 -> (d1-2)(5-2) <= 3 <=> (d1-2)*3 <= 3 <=> d1-2 <= 1 -> d1 <= 3 -> 3 <= d1 <= 3 -> d1 = 3
Con lo cual, los grafos son:
{d1=3,d2=3}{d1=4,d2=3}{d1=3,d2=4}{d1=3,d2=5}{d1=5,d2=3}
http://mathworld.wolfram.com/images/eps-gif/PlatonicGraphs_1000.gif

Ejercicio 09.10:

a)
b)

Inicialización. Tomar como R inicial un circuito de G.
• Mientras R no sea una representación planar de G:
	• Particionar R en partes relativas a G\R
	• Identificar para cada parte p el conjunto F(p) de las caras en las que p es potencialmente dibujable
	Si para algún p, F(p) es vacío
		Parar y Return FALSE
	Sino
		si hay algun p para el cual F(p) tiene una sola cara f
			elegir esa cara
		sino
			elegir una cara cualquiera f correspondiente a un p cualquiera.
	Determinar un camino q, formado por ejes de p, entre un par de nodos de contacto de p.
	Poner R = R U q
Return R representación planar de G.

Coloreo

Ejercicio 09.11:

Notas:

• W(G) <= X(G) <= max d(G)+1
• Si G es planar -> X(G) <= 4

a)
1. 3 <= X(G) <= 4; X(G) =
2. 3 <= X(G) <= 4; X(G) = 3
3. 3 <= X(G) <= 5; X(G) =
4. 3 <= X(G) <= 4; X(G) = 3
b)

Ejercicio 09.12:

a)
Vertices = Variables
Ejes = Relacion "depende de"
Colores = Posiciones de Memoria
b)

Ejercicio 09.13:

Vertices = Comisiones
Ejes = Relacion "comparte legisladores con"
Colores = Reuniones

Ejercicio 09.14:

a)
Vertices = Experimentos
Ejes = Relacion "se superpone con"
Colores = Observatorios
b)

Ejercicio 09.15:

Vertices = Matematicos
Ejes = Relacion "tiene conflicto con"
Colores = Hoteles

Ejercicio 09.16:

Vertices = Radios
Ejes = Relacion "esta a menos de 100 km de"
Colores = Frecuencias

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 є 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:

Por induccion:

• CB n = 2 !
• PI:

Sea G' = G-v (G sin el vertice v). Agregamos el vertice. Si X(G') < X(G), G era k-critico y listo. Si no, X(G') = X(G), con lo cual, si G' tenia un subgrafo k-critico, G tambien lo tiene -> OK

Ejercicio 09.19:

a)
=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS
<=)Como G no tiene circuitos de long. impar -> G es bipartito -> X(G) = 2 (ya que se puede usar un color para la primer particion y otro para la segunda) -> G es 2-coloreable OK
b) Con BFS (si llego a un vertice marcado y se quiere pintar con el mismo color -> no es 2-coloreable)
c) O(n+m)

Ejercicio 09.20:

El grafo de Grotzsch.

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:

Creo que sale con Teorema de Brooks

Ejercicio 09.23:

a) Si toda region tiene un numero par de aristas frontera -> todos los circuitos de G tienen longitud par -> G es bipartito -> G es 2-coloreable
b) Sup. que G es 2-coloreable -> G es bipartito -> el caso con mas ejes seria el del bipartito completo, entonces tomando V1 como una de las particiones, la cant. de ejes seria |V1|(8-|V1|) = 13 -> -1|V1|^2 + 8|V1| - 13 = 0. Pero no hay un numero entero que cumpla esto -> ABS
c)

Ejercicio 09.25:

a)
1. k(k-1)
2. k(k-1)^2
3. k(k-1)(k-2)
4. k(k-1)^2(k-2) + k(k-1)^2(k-1) = k(k-1)^2)(k-2 + k-1) = k(k-1)^2)(2k-3)
5. k(k-1)(k-2)(k-3)
6. k(k-1)(k-2)(k-1)^2
7. k(k-1)(k-2)...(k-(n-1))

b) Creo que es igual a la cant. de raices del polinomio cromatico

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)

Ejercicio 09.34:

1. X'(G) = 4
2. X'(G) = 3 (es bipartito)
3. X'(G) = 3 (n-1, es completo con n par)
4. X'(G) = 5 (n, es completo con n impar)

Ejercicio 09.35:

Se puede resolver coloreando los ejes de un multigrafo, asignando vertices a los profesores y los alumnos, y cada eje representa 1 hora, entonces por ej. si un profesor le da 3 horas a un grupo, hay 3 ejes entre los dos vertices.