Edición de «Práctica 10: Coloreo (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
=Propiedades= | |||
(Para todo G: grafo) | (Para todo G: grafo) | ||
Línea 25: | Línea 25: | ||
* (TEO) X'(G) = max d(v) o X'(G) = max d(v)+1 | * (TEO) X'(G) = max d(v) o X'(G) = max d(v)+1 | ||
=Ejercicio 10.01:= | |||
Notas: | Notas: | ||
* W(G) <= X(G) <= max d(G)+1 | * W(G) <= X(G) <= max d(G)+1 | ||
Línea 31: | Línea 31: | ||
<br>a) | <br>a) | ||
<br> 1. 3 <= X(G) <= 4; X(G) = | <br> 1. 3 <= X(G) <= 4; X(G) = | ||
<br> 2. | <br> 2. 3 <= X(G) <= 4; X(G) = 3 | ||
<br> 3. | <br> 3. 3 <= X(G) <= 5; X(G) = | ||
<br> 4. 3 <= X(G) <= 4; X(G) = 3 | <br> 4. 3 <= X(G) <= 4; X(G) = 3 | ||
<br> | <br>b) | ||
=Ejercicio 10.02:= | |||
<br> | <br>a) | ||
<br>Ejes = | <br>Vertices = Variables | ||
<br>Colores = | <br>Ejes = Relacion "depende de" | ||
<br>Colores = Posiciones de Memoria | |||
<br>b) | |||
=Ejercicio 10.03:= | |||
<br>Vertices = Comisiones | <br>Vertices = Comisiones | ||
<br>Ejes = Relacion "comparte legisladores con" | <br>Ejes = Relacion "comparte legisladores con" | ||
<br>Colores = Reuniones | <br>Colores = Reuniones | ||
=Ejercicio 10.04:= | |||
<br> | <br>a) | ||
<br>Ejes = | <br>Vertices = Experimentos | ||
<br>Colores = " | <br>Ejes = Relacion "se superpone con" | ||
<br>Colores = Observatorios | |||
<br>b) | |||
=Ejercicio 10.05:= | |||
<br>Vertices = Matematicos | |||
<br>Ejes = Relacion "tiene conflicto con" | |||
<br>Colores = Hoteles | |||
=Ejercicio 10.06:= | |||
<br> | <br>Vertices = Radios | ||
<br>Ejes = | <br>Ejes = Relacion "esta a menos de 100 km de" | ||
<br>Colores = Frecuencias | <br>Colores = Frecuencias | ||
=Ejercicio 10.07:= | |||
<br>a) Sup. que no es conexo. Sea G' = G-C1, es decir, G sin la comp. conexa C1. | <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> Como es color critico -> X(G') < X(G) y X(C1) < X(G) | ||
Línea 90: | Línea 85: | ||
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) | 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 | |||
<br> Otra forma: | |||
Ir borrando vértices, hasta que el subgrafo que queda al sacar cualquier vertice queda critico. | |||
=Ejercicio 10.09:= | |||
<br>a) | <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>=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS | ||
Línea 101: | Línea 101: | ||
<br>c) O(n+m) | <br>c) O(n+m) | ||
==Ejercicio 10.11: | =Ejercicio 10.10:= | ||
El grafo de Grotzsch. (Es el grafo de Mycielski 4, M_4.) | |||
=Ejercicio 10.11:= | |||
<br>a) Por induccion en n: | <br>a) Por induccion en n: | ||
* CB: n = 1 | * CB: n = 1 | ||
X(G) = X(Gc) = 1 -> 2 <= 2 OK | X(G) = X(Gc) = 1 -> 2 <= 2 OK | ||
* PI: | * PI: | ||
Saco un vertice -> G' = G-v | |||
<br>X(G)+X(Gc) = X(G')+X(Gc')+k (k cte.). Separamos en casos: | |||
<br>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 | |||
<br>X(G)+X(Gc) = X(G')+X( | <br>2. dG(v) >= X(G') y dGc(v) >= X(Gc') -> | ||
<br> | X(G') <= X(G) + 1 <= dG(v) + 1 y | ||
X(G'c) <= X(Gc) + 1 <= dGc(v) + 1 entonces | |||
<br> | <br>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 | ||
<br> | |||
<br>b) Probamos ambas desigualdades: | <br>b) Probamos ambas desigualdades: | ||
Línea 128: | Línea 128: | ||
(X(G)+X(Gc))/2 >= (por b) √(X(G)*X(Gc)) >= √n -> X(G)+X(Gc) >= 2√n | (X(G)+X(Gc))/2 >= (por b) √(X(G)*X(Gc)) >= √n -> X(G)+X(Gc) >= 2√n | ||
=Ejercicio 10.12:= | |||
Por absurdo. | Por absurdo. | ||
Línea 139: | Línea 139: | ||
<br> X(G) + X(Gc) <= d(G)+n-d(G) = n Absurdo, porque deberia ser n+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>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 | <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 | ||
Línea 150: | Línea 150: | ||
<br>c) | <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. | 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. | 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>a) | ||
<br>1. k(k-1) | <br>1. k(k-1) | ||
Línea 175: | Línea 175: | ||
Por ejemplo en el 2) PG(0)=0, PG(1)=0, PG(2)=2. Entonces X(G)=2. | Por ejemplo en el 2) PG(0)=0, PG(1)=0, PG(2)=2. Entonces X(G)=2. | ||
=Ejercicio 10.16:= | |||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
=Ejercicio 10.17:= | |||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
Línea 186: | Línea 186: | ||
<br>e) | <br>e) | ||
<br>f) | <br>f) | ||
=Ejercicio 10.18:= | |||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
<br>d) | <br>d) | ||
=Ejercicio 10.19:= | |||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
Línea 197: | Línea 197: | ||
<br>d) | <br>d) | ||
<br>e) | <br>e) | ||
=Ejercicio 10.20:= | |||
=Ejercicio 10.21:= | |||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
=Ejercicio 10.22:= | |||
=Ejercicio 10.23:= | |||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
=Ejercicio 10.24:= | |||
<br>1. X'(G) = 4 | <br>1. X'(G) = 4 | ||
<br>2. X'(G) = 3 (es bipartito) | <br>2. X'(G) = 3 (es bipartito) | ||
Línea 211: | Línea 211: | ||
<br>4. X'(G) = 5 (n, es completo con n impar) | <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. | 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]] | [[Category: Prácticas]] |