variantes del problema de coloreo de grafos
TRANSCRIPT
![Page 1: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/1.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Variantes del problema de coloreo de grafos
Flavia Bonomo
Departamento de MatematicaFacultad de Ciencias Exactas y Naturales
Universidad de Buenos Aires
14 de diciembre de 2005
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 2: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/2.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
¿Que es un grafo?
I Un grafo esta formado por un conjunto de vertices y unconjunto de aristas que unen pares de vertices.
I Es un objeto matematico abstracto pero se usa para modelarproblemas reales.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 3: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/3.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Grafos en la vida real
Red de subtes
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 4: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/4.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Grafos en la vida real
2
226
205
33
5
152
22
23
237
Rutas entre ciudades
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 5: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/5.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Grafos en la vida real
Moleculas
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 6: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/6.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Grafos en la vida real
Draw de un torneo de tenis
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 7: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/7.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Grafos en la vida real
Relaciones sociales
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 8: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/8.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
Pintar mapas
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 9: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/9.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
Pintar mapas
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 10: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/10.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
Pintar mapas
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 11: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/11.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
El Teorema de los 4 colores
Teorema
Todo mapa puede ser coloreado sin que dos regiones limıtrofestengan el mismo color, y usando 4 o menos colores.
I 1852: De Morgan le plantea por carta (no existıa el e-mail!)un problema a Hamilton, que habıan planteado dos de susalumnos, los hermanos F & F Guthrie.
I Entre 1879 y 1976 se presentaron varias demostraciones queresultaron tener falacias logicas.
I 1976: demostracion computacional de Appel, Haken y Koch.
I 1997: nueva prueba computacional pero mucho mas sencilla(Robertson, Sanders, Seymour y Thomas).
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 12: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/12.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
El Teorema de los 4 colores
Teorema
Todo mapa puede ser coloreado sin que dos regiones limıtrofestengan el mismo color, y usando 4 o menos colores.
I 1852: De Morgan le plantea por carta (no existıa el e-mail!)un problema a Hamilton, que habıan planteado dos de susalumnos, los hermanos F & F Guthrie.
I Entre 1879 y 1976 se presentaron varias demostraciones queresultaron tener falacias logicas.
I 1976: demostracion computacional de Appel, Haken y Koch.
I 1997: nueva prueba computacional pero mucho mas sencilla(Robertson, Sanders, Seymour y Thomas).
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 13: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/13.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
El Teorema de los 4 colores
Teorema
Todo mapa puede ser coloreado sin que dos regiones limıtrofestengan el mismo color, y usando 4 o menos colores.
I 1852: De Morgan le plantea por carta (no existıa el e-mail!)un problema a Hamilton, que habıan planteado dos de susalumnos, los hermanos F & F Guthrie.
I Entre 1879 y 1976 se presentaron varias demostraciones queresultaron tener falacias logicas.
I 1976: demostracion computacional de Appel, Haken y Koch.
I 1997: nueva prueba computacional pero mucho mas sencilla(Robertson, Sanders, Seymour y Thomas).
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 14: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/14.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
El Teorema de los 4 colores
Teorema
Todo mapa puede ser coloreado sin que dos regiones limıtrofestengan el mismo color, y usando 4 o menos colores.
I 1852: De Morgan le plantea por carta (no existıa el e-mail!)un problema a Hamilton, que habıan planteado dos de susalumnos, los hermanos F & F Guthrie.
I Entre 1879 y 1976 se presentaron varias demostraciones queresultaron tener falacias logicas.
I 1976: demostracion computacional de Appel, Haken y Koch.
I 1997: nueva prueba computacional pero mucho mas sencilla(Robertson, Sanders, Seymour y Thomas).
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 15: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/15.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
Coloreo de grafos
Colorear un grafo consiste en asignar un “color” (usualmente unnumero) a cada vertice de manera tal que vertices distintos recibancolores distintos.
Formalmente, un coloreo de un grafo G = (V ,E ) es una funcionf : V → N tal que f (v) 6= f (w) si v es adyacente a w .
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 16: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/16.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
k-coloreo
Dado un grafo G = (V ,E ), un k-coloreo de G es un coloreo f parael cual f (v) ≤ k para todo v ∈ V (solo hay k colores disponibles).
Un grafo G es k-coloreable si existe un k-coloreo de G .
k=3 k=3
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 17: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/17.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
List-coloreo
Dado un grafo G = (V ,E ) y una lista finita L(v) ⊆ N de colorespara cada vertice v ∈ V , G es list-coloreable si existe un coloreo fpara el cual f (v) ∈ L(v) para cada v ∈ V (Vizing, 1976).
1,2
1,3
1
2,3
3
2,3
21,3
1,2
1,3
1
2,3
3
2,3
21,3
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 18: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/18.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
µ-coloreo
Dado un grafo G = (V ,E ) y una funcion µ : V → N, un µ-coloreode G es un coloreo f para el cual f (v) ≤ µ(v) para cada verticev ∈ V .
Un grafo G es µ-coloreable si existe un µ-coloreo de G .
3
1
3
3
2
2
3
2
3
1
3
3
2
2
3
2
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 19: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/19.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
Aplicaciones
Estamos organizando un congreso de matematicos, y cualquierhotel de la ciudad tiene capacidad para alojar a todos losmatematicos, pero hay algunos que estan peleados a tal punto queno pueden alojarse en el mismo hotel.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 20: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/20.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
Aplicaciones
Si hay k hoteles en la ciudad, una distribucion valida es equivalentea un k-coloreo valido del “grafo de enemistades”, donde cada colorrepresenta un hotel.
k=cant. hoteles
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 21: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/21.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
Aplicaciones
Si ademas de peleadores son muy caprichosos, y cada uno tieneuna lista de hoteles preferidos, una distribucion valida esequivalente a un list-coloreo valido en el “grafo de enemistades”,donde cada color representa un hotel.
1,21,3,5
2,41,5
2,3
2,4,5
3
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 22: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/22.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
El Teorema de los 4 coloresDefinicionesAplicaciones
Aplicaciones
Si no son taaan caprichosos, pero cada uno tiene una pretensionmınima de cantidad de estrellas, una distribucion valida esequivalente a un µ-coloreo valido en el “grafo de enemistades”,donde cada color representa un hotel, ordenados por categorıa, y elµ es el maximo de los hoteles dentro de la categorıa pretendida.
23
35
2
5
3
1,23
4,5
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 23: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/23.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Relacion entre k-coloreo, list-coloreo, µ-coloreo
El problema de µ-coloreo es un problema intermedio entrek-coloreo y list-coloreo.
I Una reduccion trivial de k-coloreo a µ-coloreo se obtienedefiniendo µ(v) = k para todo v .
I Una reduccion de µ-coloreo a list-coloreo se obtiene definiendoL(v) = {1, . . . ,min{µ(v), |V (G )|}}.
3
3
3
3
3
3
3k=3 3
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 24: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/24.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Relacion entre k-coloreo, list-coloreo, µ-coloreo
El problema de µ-coloreo es un problema intermedio entrek-coloreo y list-coloreo.
I Una reduccion trivial de k-coloreo a µ-coloreo se obtienedefiniendo µ(v) = k para todo v .
I Una reduccion de µ-coloreo a list-coloreo se obtiene definiendoL(v) = {1, . . . ,min{µ(v), |V (G )|}}.
3
3
3
3
3
3
3k=3 3
1,2
1
1
1,2,3
1,2,3
2
1
1
3
3
3
2
1,2,3
1,21,22
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 25: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/25.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Algoritmo para 2-coloreo
Un algoritmo para decidir si un grafo es 2-coloreable o no, usandouna pila, es el siguiente:
I Mientras queden vertices sin pintar:I Tomar un vertice sin pintar del grafo, pintarlo de 1 y ponerlo
en la pila.I Repetir el siguiente procedimiento, mientras la pila no quede
vacıa:I Sacar un vertice v de la pila. Para cada vecino, si esta pintado
del mismo color que v , devolver “no se puede”. Si estapintado del color contrario que v , nada. Si no esta pintado,pintarlo del color contrario que v y ponerlo en la pila.
1 1 2
2
1 2
2
1
1
2
2
1 2
2
1
1
2
21
1 1 2
2
1 2
2
1 2
2no se puede
1 2
2
1
1
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 26: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/26.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Algoritmo para 2-coloreo
¿Cuantos pasos realiza el algoritmo?
A cada vertice lo “mira” una vez cuando lo pinta y apila, una vezcuando lo desapila, y una vez por cada vecino suyo.
Si hay n vertices, cada vertice tiene a lo sumo n − 1 vecinos, y elalgoritmo realiza a lo sumo ∼ n2 pasos.
Se die que el algoritmo es O(n2), y cuadratico en el tamano de laentrada.
Un grafo 2-coloreable se llama bipartito.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 27: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/27.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Algoritmo para 2-coloreo
¿Cuantos pasos realiza el algoritmo?
A cada vertice lo “mira” una vez cuando lo pinta y apila, una vezcuando lo desapila, y una vez por cada vecino suyo.
Si hay n vertices, cada vertice tiene a lo sumo n − 1 vecinos, y elalgoritmo realiza a lo sumo ∼ n2 pasos.
Se die que el algoritmo es O(n2), y cuadratico en el tamano de laentrada.
Un grafo 2-coloreable se llama bipartito.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 28: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/28.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Algoritmo para 2-coloreo
¿Cuantos pasos realiza el algoritmo?
A cada vertice lo “mira” una vez cuando lo pinta y apila, una vezcuando lo desapila, y una vez por cada vecino suyo.
Si hay n vertices, cada vertice tiene a lo sumo n − 1 vecinos, y elalgoritmo realiza a lo sumo ∼ n2 pasos.
Se die que el algoritmo es O(n2), y cuadratico en el tamano de laentrada.
Un grafo 2-coloreable se llama bipartito.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 29: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/29.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Algoritmo para 2-coloreo
¿Cuantos pasos realiza el algoritmo?
A cada vertice lo “mira” una vez cuando lo pinta y apila, una vezcuando lo desapila, y una vez por cada vecino suyo.
Si hay n vertices, cada vertice tiene a lo sumo n − 1 vecinos, y elalgoritmo realiza a lo sumo ∼ n2 pasos.
Se die que el algoritmo es O(n2), y cuadratico en el tamano de laentrada.
Un grafo 2-coloreable se llama bipartito.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 30: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/30.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Algoritmo goloso para k-coloreo o µ-coloreo
El algoritmo goloso de coloreo consiste en ordenar de alguna formalos vertices y para cada vertice v , colorearlo del menor colordisponible (que no haya sido usado ya para alguno de sus vecinos).Si ese color es mayor que k o que µ(v), devolver “no se puede”.
1 1
2
1
2
2
1
2
2
3
1
3
2
3
2
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 31: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/31.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Algoritmo goloso para k-coloreo o µ-coloreo
No siempre resuelve el problema. Puede llegar a no conseguir unk-coloreo, y sin embargo este existe.
Ejemplo:
1 11 1 12 1 12 3 1 22 1
Sin embargo, para cografos (grafos sin un camino de 4 verticesinducido), funciona tanto para k-coloreo como para µ-coloreo,ordenando los vertices en forma creciente respecto de µ.
Pero para grafos en general, no se conoce un algoritmo eficientepara k-coloreo.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 32: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/32.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Clases de complejidad
I P: problemas de decision que se pueden resolver en tiempoacotado por un polinomio en el tamano de la entrada.
Ejemplo: 2-coloreo, µ-coloreo de cografos.
I NP: problemas de decision tales que toda instancia derespuesta SI, tiene un “certificado” verificable en tiempopolinomial.
Ejemplo: k-coloreo, µ-coloreo o list-coloreo de grafos. Me danun coloreo y puedo chequear facilmente si es valido.
I NP-completos: problemas en NP tales que todo problema enNP se puede reducir polinomialmente a ellos.
Ejemplo: 3-coloreo, µ-coloreo de grafos bipartitos, list-coloreode cografos y de grafos bipartitos.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 33: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/33.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Clases de complejidad
I P: problemas de decision que se pueden resolver en tiempoacotado por un polinomio en el tamano de la entrada.
Ejemplo: 2-coloreo, µ-coloreo de cografos.
I NP: problemas de decision tales que toda instancia derespuesta SI, tiene un “certificado” verificable en tiempopolinomial.
Ejemplo: k-coloreo, µ-coloreo o list-coloreo de grafos. Me danun coloreo y puedo chequear facilmente si es valido.
I NP-completos: problemas en NP tales que todo problema enNP se puede reducir polinomialmente a ellos.
Ejemplo: 3-coloreo, µ-coloreo de grafos bipartitos, list-coloreode cografos y de grafos bipartitos.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 34: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/34.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Clases de complejidad
I P: problemas de decision que se pueden resolver en tiempoacotado por un polinomio en el tamano de la entrada.
Ejemplo: 2-coloreo, µ-coloreo de cografos.
I NP: problemas de decision tales que toda instancia derespuesta SI, tiene un “certificado” verificable en tiempopolinomial.
Ejemplo: k-coloreo, µ-coloreo o list-coloreo de grafos. Me danun coloreo y puedo chequear facilmente si es valido.
I NP-completos: problemas en NP tales que todo problema enNP se puede reducir polinomialmente a ellos.
Ejemplo: 3-coloreo, µ-coloreo de grafos bipartitos, list-coloreode cografos y de grafos bipartitos.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 35: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/35.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
¿P 6= NP? La pregunta del millon...
Si existe un problema en NP-c ∩ P, entonces P=NP. No se conoceninguno, ası como tampoco se conoce un problema en NP \ P.
NPNP-c
P
si P=NP...
NPNP-c
P
si P=NP...
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 36: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/36.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
Complejidades
Problema Grafos Cografos Grafos Grafoscompletos Cografos bipartitos en general
k-coloreo P P [2] P NP-c [1]µ-coloreo P P [5] NP-c [5] NP-clist-coloreo P NP-c [4] NP-c [3] NP-c
[1] Karp, 1976.[2] Chvatal, 1984.[3] Hujter y Tuza, 1993.[4] Jansen y Scheffler, 1997.[5] B. y Cecowski, 2005.
Flavia Bonomo Variantes del problema de coloreo de grafos
![Page 37: Variantes del problema de coloreo de grafos](https://reader035.vdocumento.com/reader035/viewer/2022063020/62bc175ba9736c4c2b6dd382/html5/thumbnails/37.jpg)
¿Que es un grafo?Problemas de coloreo de grafos
Complejidad algorıtmica
Algoritmos para coloreoClases de complejidad
¿Como se prueba que un problema es NP-completo?
Queremos probar que µ-coloreo es NP-completo para grafosbipartitos. Ya estaba demostrado que list-coloreo es NP-completopara grafos bipartitos. Entonces buscamos una reduccionpolinomial de ese problema al nuestro.
3 3
3 3
3 3
3 3
1 1
2
3
2
3
1 1
2
3
2
3
1,2
1,3
1
2,3
3
2,3
21,3
3 3
3 3
3 3
3 3
Flavia Bonomo Variantes del problema de coloreo de grafos