Edición de «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

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

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

==Ejercicio 10.03:==
<br>Vertices = Comisiones
<br>Ejes = Relacion "comparte legisladores con"
<br>Colores = Reuniones

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

==Ejercicio 10.05:==
<br>Vértices = Torres
<br>Ejes = Relación "están a menos de 50 Km"
<br>Colores = Frecuencias

Se puede hacer con 3 colores:

Color 1: A,B,H<br>
Color 2: D,G<br>
Color 3: C,E,F<br>

==Ejercicio 10.06:==
<br>Vértices = Radios
<br>Ejes = Relación "esta a menos de 100 km de"
<br>Colores = Frecuencias

* CB n = 2 !
* PI:
Sea G' = G-v (G sin el vértice v). Agregamos el vértice. Si X(G') < X(G), G era k-crítico y listo. Si no, X(G') = X(G), con lo cual, si G' tenía un subgrafo k-crítico, G también lo tiene.

==Ejercicio 10.07:==
<br>a) Sup. que no es conexo. Sea G' = G-C1, es decir, G sin la comp. conexa C1.
<br> Como es color critico -> X(G') < X(G) y X(C1) < X(G)
<br> 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)

<br>b) Sup. Ex. v є V / d(v) < k-1. Hacemos G' = G-v
<br> Como es color critico -> X(G') < X(G) (Obs: para todo G, X(G-v)=X(G)-1)
<br> 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

<br>c) Sea C1 una comp. conexa de G-v -> X(C1+v) < X(G) y X(G-C1) < X(G)
<br> 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

<br>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:==

==Ejercicio 10.09:==

==Ejercicio 10.10:==
<br>a)
<br>=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS
<br><=)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
<br>b) Con BFS (si llego a un vertice marcado y se quiere pintar con el mismo color -> no es 2-coloreable)
<br>c) O(n+m)

==Ejercicio 10.11:==
<br>a) Por induccion en n:
* CB: n = 1
X(G) = X(Gc) = 1 -> 2 <= 2 OK
* PI:
<br> Sea G un grafo de n vértices, q.v.q. X(G) + X(Gc) <= n+1
<br>HI: Sea G' un grafo con n' vértices con n'<n entonces X(G') + X(G'c) <= n'+1
<br>Saco un vertice a G -> G' = G-v
<br>X(G)+X(Gc) = X(G')+X(G'c)+k (k cte.). Separamos en casos:
<br>Caso 1. X(G) = X(G') o X(Gc) = X(G'c) -> k <= 1 (ya que a lo sumo se puede reducir en 1 color al quitar un vértice)
<br> -> X(G)+X(Gc) = X(G')+X(G'c)+k <= X(G')+X(G'c) + 1 <=(HI) n'+2 = (n-1)+2 = n+1 OK
<br>Caso 2. X(G) > X(G') y X(Gc) > X(G'c) 
<br> -> dG(v) >= X(G') y dGc(v) >= X(G'c) (ya que v agrega un color a ambos grafos por lo que en ambos es adyacente a cada color al menos una vez)
<br> -> X(G) = X(G')+1 y  X(Gc) = X(G'c)+1 (porque agregar un vértice no puede agregar más de un color)
<br> -> X(G) + X(Gc) = X(G') + X(G'c) + 2 <= dG(v) + dGc(v) + 2 = n-1 + 2 = n+1 OK

<br>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)
<br> 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)

<br>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. 
<br> X(G) <= maximoGrado(G).
<br> Como el grafo es regular, maximoGrado(G)= d(G).
<br> Para el grafo complemento vale que X(Gc) <= maximoGrado(Gc)+1 = d(Gc)+1.
(el complemento de un regular es regular).
<br> d(Gc)+1 = n-d(G)+1-1
<br> X(G) + X(Gc) <= d(G)+n-d(G) = n Absurdo, porque deberia ser n+1

==Ejercicio 10.13:==
<br>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
<br>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.


<br>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:==
<br>a)
<br>1. k(k-1)
<br>2. k(k-1)^2
<br>3. k(k-1)(k-2)
<br>4. k(k-1)^2(k-2) + k(k-1)^2 = (k-1)^4+(k-1)
<br>
Numerar los vertices de C4 v1,v2,v3,v4
<br>v1---v2
<br>|____|
<br>v4---v3
<br>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.
<br>5. k(k-1)(k-2)(k-3)
<br>6. k(k-1)(k-2)(k-1)^2
<br>7. k(k-1)(k-2)...(k-(n-1))

<br>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:==
<br>a)
<br>b)
<br>c)
==Ejercicio 10.17:==
<br>a)
<br>b)
<br>c)
<br>d)
<br>e)
<br>f)
==Ejercicio 10.18:==
<br>a)
<br>b)
<br>c)
<br>d)
==Ejercicio 10.19:==
<br>a)
<br>b)
<br>c)
<br>d)
<br>e)
==Ejercicio 10.20:==
==Ejercicio 10.21:==
<br>a)
<br>b)
==Ejercicio 10.22:==
==Ejercicio 10.23:==
<br>a)
<br>b)
==Ejercicio 10.24:==
<br>1. X'(G) = 4
<br>2. X'(G) = 3 (es bipartito)
<br>3. X'(G) = 3 (n-1, es completo con n par)
<br>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.

[[Category: Prácticas]]