Práctica 10: Coloreo (Algoritmos III)

Propiedades

(Para todo G: grafo)

• (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

Ejercicio 10.01:

Notas:

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

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

Ejercicio 10.02:

Vértices = Tareas
Ejes = Relación "utiliza el mismo recurso que"
Colores = "pueden ejecutarse en simultáneo" (conjuntos independientes)

Ejercicio 10.03:

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

Ejercicio 10.04:

Vértices = Cursos
Ejes = Relación "fue requerido por al menos un inscripto al mismo tiempo que"
Colores = "horarios distintos" (conjuntos independientes)

Ejercicio 10.05:

Vértices = Torres
Ejes = Relación "están a menos de 50 Km"
Colores = Frecuencias

W(G)<=X(G)<=D(G)+1 3<=X(G)<=7 3<=X(G)<=4 (planar) X(G)=4

A(2)-B(2)-C(2)-D(1)-E(2)-F(3)-G(4)-H(3)

Ejercicio 10.06:

b) Si G es k-cromático entonces contiene algún subgrafo k-cromático y color crítico. Si G es color crítico entonces es trivial. Si G no es color crítico, existen nodos al ser removidos disminuyen la cantidad de colores y nodos que no. Los nodos que disminuyen la cantidad de colores hacen la implicación verdadera. Veamos que el caso que falta puede probarse por inducción en la cantidad de nodos. Se prueba el caso base con dos nodos. Luego por HI el grafo G con n-1 nodos contiene un subgrafo color crítico y k-cromático. Al quitar de G un nodo, si la cantidad de colores se redujo, entonces G era color crítico. Si no disminuyó la cantidad de colores, se obtuvo un grafo con un nodo menos que, por hipótesis inductiva, contiene un grafo que es color crítico.

Ejercicio 10.07:

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) Por abs. Supongamos que G tiene una clique de corte S. Sean Gi,...,Gs las componentes de sacar a S de G, pero ademas esas componentes tiene la clique S. Como el grafo es color critico, vale que cada componente es k-1 coloreable. En particular como S es una cloque cada vertice de esa clique usa colores distintos. Ahora tenemos que los Gi son k-1 coloreables y cada una tiene distintos colores en S. Si cada Gi usa los mismos colores en S, se puede generar un coloreo k-1 de G. (no fiarse de mi dem., pero quiza sirve de idea)

Ejercicio 10.08:

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

Otra forma: Ir borrando vértices, hasta que el subgrafo que queda al sacar cualquier vertice queda critico.

Ejercicio 10.09:

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

El grafo de Grotzsch. (Es el grafo de Mycielski 4, M_4.)

Ejercicio 10.11:

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(G) + 1 <= dG(v) + 1 y X(G'c) <= X(Gc) + 1 <= dGc(v) + 1 entonces
X(G') + X(G'c) <= 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 10.12:

Por absurdo. Supongamos que G no es ninguno de los que dice el enunciado, entonces se puede usar el teorema de brooks.
X(G) <= maximoGrado(G).
Como el grafo es regular, maximoGrado(G)= d(G).
Para el grafo complemento vale que X(Gc) <= maximoGrado(Gc)+1 = d(Gc)+1. (el complemento de un regular es regular).
d(Gc)+1 = n-d(G)+1-1
X(G) + X(Gc) <= d(G)+n-d(G) = n Absurdo, porque deberia ser n+1

Ejercicio 10.13:

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

Hay otra manera de resolver este punto. Suponemos que G es 2-Coloreable. Entonces G es bipartito. Como el enunciado dice que G es planar, y asumimos que es bipartito, G debe cumplir con m<=2n-4. (esta es una condiciòn de los grafos planares bipartitos). Como m=13 y n=8, m<=2n-4 <=> 13<=12, lo cual no es cierto. Luego nuestro supuesto de que G es bipartito es falso.

c)

Ejercicio 10.14:

En la clase se mostró la demo de que todo grafo planar puede ser coloreado con 5 colores. Esta demo usaba el hecho de que todo grafo planar tiene al menos un vertice de grado menor o igual a 5. Este ejercicio es similar a dicha demostración, salvo por el hecho de que aquí sabemos, por enunciado, que tenemos al menos un vertice de grado menor o igual a 4.

Ejercicio 10.15:

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)^4+(k-1)
Numerar los vertices de C4 v1,v2,v3,v4
v1---v2
|____|
v4---v3
En el circuito el primer termino de la suma corresponde a v2,v4 con distintos colores, lo que obliga a v3 tener k-2 elecciones. El segundo termino corresponde a v2 y v4 con los mismos colores.
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) Vamos tomando k crecientes a partír de 0. Luego, el primer valor de k para el que PG(k)!=0 es el número cromático. Por ejemplo en el 2) PG(0)=0, PG(1)=0, PG(2)=2. Entonces X(G)=2.

Ejercicio 10.16:

a)
b)
c)

Ejercicio 10.17:

a)
b)
c)
d)
e)
f)

Ejercicio 10.18:

a)
b)
c)
d)

Ejercicio 10.19:

a)
b)
c)
d)
e)

Ejercicio 10.21:

a)
b)

Ejercicio 10.23:

a)
b)

Ejercicio 10.24:

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

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.