Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... ·...
Transcript of Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... ·...
![Page 1: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/1.jpg)
Camiones, encomiendas, y teorıa de grafos
Flavia Bonomo
Facultad de Ciencias Exactas y NaturalesUniversidad de Buenos Aires
Semana de la Matematica 2010
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 2: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/2.jpg)
¿Que es un grafo?
Un grafo esta formado por un conjunto de vertices y unconjunto de aristas que unen pares de vertices.
Es un objeto matematico abstracto pero se usa para modelarproblemas reales.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 3: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/3.jpg)
Grafos en la vida real
Red de subtes
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 4: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/4.jpg)
Grafos en la vida real
Rutas entre ciudades
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 5: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/5.jpg)
Grafos en la vida real
Moleculas
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 6: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/6.jpg)
Grafos en la vida real
Draw de un torneo de tenis (los grafos de este tipo se llamanarboles)
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 7: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/7.jpg)
Grafos en la vida real
Relaciones sociales o redes tipo facebook
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 8: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/8.jpg)
Pintando mapas
Todos alguna vez pintamos un mapa. La regla es que provinciasque limitan en mas de un punto tienen que tener colores distintos.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 9: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/9.jpg)
Pintando mapas
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 10: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/10.jpg)
Pintando mapas
Si ponemos un vertice por cada provincia y unimos dos vertices sila respectivas provincias limitan, nos queda definido un grafo.Vamos a decir entonces que un coloreo de un grafo es unaasignacion de colores a los vertices de manera tal que verticesadyacentes reciban colores distintos.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 11: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/11.jpg)
Pintando mapas
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 12: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/12.jpg)
Pintando mapas
El grafo que queda no es cualquier grafo. Se puede dibujar sin quelas aristas se crucen (salvo en los vertices). Ese tipo de grafos sellaman planares.Algunos grafos que no son planares son estos:
Una cosa que podemos preguntarnos es, ¿Cuantos coloresnecesitamos para pintar un mapa?
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 13: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/13.jpg)
Pintando mapas
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 14: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/14.jpg)
El Teorema de los 4 colores
Teorema
Todo mapa puede ser coloreado sin que dos regiones limtrofestengan el mismo color, y usando 4 o menos colores.
Teorema
Todo grafo planar puede ser coloreado usando 4 o menos colores.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 15: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/15.jpg)
Como se trabaja en matematica aplicada?
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 16: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/16.jpg)
Como se trabaja en matematica aplicada?
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 17: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/17.jpg)
Como se trabaja en matematica aplicada?
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 18: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/18.jpg)
Como se trabaja en matematica aplicada?
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 19: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/19.jpg)
Como se trabaja en matematica aplicada?
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 20: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/20.jpg)
Como se trabaja en matematica aplicada?
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 21: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/21.jpg)
Otra clase de grafos particular: grafos de permutacion
Tenemos dos rectas paralelas, sobre una de ellas los numeros de 1a n y en la otra una permutacion de ellos. Unimos cada par denumeros iguales con un segmento. El grafo de permutacioncorrespondiente tiene n vertices numerados de 1 a n, y dos verticesi y j son adyacentes si los segmentos correspondientes se cruzan.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 22: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/22.jpg)
El problema de las encomiendas
Tenemos un cambion que tiene que buscar encomiendas en unaciudad en un cierto orden prefijado y entregarlas en otra ciudad enotro orden prefijado tambien.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 23: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/23.jpg)
El problema de las encomiendas
k stacks (tıpicamente k = 3)
maximo t cajas por stack (tıpicamente t = 11)
no se pueden reacomodar las cajas durante la entrega
¿en que stack debo poner cada caja?
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 24: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/24.jpg)
El problema de las encomiendas
Restriccion: Si dos cajas se retiran en el mismo orden en que sereparten, no pueden ir en el mismo stack.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 25: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/25.jpg)
Modelo matematico: coloreo de grafos!
Dos vertices son adyacentes si sus correspondientes cajas se retiranen el mismo orden en que se reparten.
Cada stack es un color. Tenemos k colores disponibles....
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 26: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/26.jpg)
Modelo matematico: coloreo de grafos!
Dos vertices son adyacentes si sus correspondientes cajas se retiranen el mismo orden en que se reparten.
Cada stack es un color. Tenemos k colores disponibles....
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 27: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/27.jpg)
Modelo matematico: coloreo de grafos!
Dos vertices son adyacentes si sus correspondientes cajas se retiranen el mismo orden en que se reparten.
Cada stack es un color. Tenemos k colores disponibles....
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 28: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/28.jpg)
Modelo matematico: coloreo de grafos!
Dos vertices son adyacentes si sus correspondientes cajas se retiranen el mismo orden en que se reparten.
Cada stack es un color. Tenemos k colores disponibles....
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 29: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/29.jpg)
Modelo matematico
El grafo que se genera, es un grafo cualquiera?
Por suerte, sabemos resolver coloreo de grafos de permutacion!(gracias a M. Golumbic)
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 30: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/30.jpg)
Modelo matematico
El grafo que se genera, es un grafo cualquiera?
Por suerte, sabemos resolver coloreo de grafos de permutacion!(gracias a M. Golumbic)
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 31: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/31.jpg)
Modelo matematico
El grafo que se genera, es un grafo cualquiera?
Por suerte, sabemos resolver coloreo de grafos de permutacion!(gracias a M. Golumbic)
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 32: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/32.jpg)
Modelo matematico
¿y las capacidades?
Hay que introducir la variante de coloreo capacitado, donde hayuna cantidad maxima de vertices de cada color.
Resulto que ya estaba estudiado porque surge de otros problemasaplicados tambien.
Se sabıa que si la capacidad es chiquita pero la cantidad de colorespuede ser arbitrariamente grande, el problema es difıcil aun engrafos de permutacion.
Junto con un grupo de colegas italianos (S. Mattia y G. Oriolo),encontramos un algoritmo eficiente para coloreo capacitado engrafos de permutacion para cuando la cantidad de colores eschiquita pero la capacidad puede ser arbitrariamente grande. Y elproblema de las encomiendas cuadra en ese caso.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 33: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/33.jpg)
Modelo matematico
¿y las capacidades?
Hay que introducir la variante de coloreo capacitado, donde hayuna cantidad maxima de vertices de cada color.
Resulto que ya estaba estudiado porque surge de otros problemasaplicados tambien.
Se sabıa que si la capacidad es chiquita pero la cantidad de colorespuede ser arbitrariamente grande, el problema es difıcil aun engrafos de permutacion.
Junto con un grupo de colegas italianos (S. Mattia y G. Oriolo),encontramos un algoritmo eficiente para coloreo capacitado engrafos de permutacion para cuando la cantidad de colores eschiquita pero la capacidad puede ser arbitrariamente grande. Y elproblema de las encomiendas cuadra en ese caso.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 34: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/34.jpg)
Modelo matematico
¿y las capacidades?
Hay que introducir la variante de coloreo capacitado, donde hayuna cantidad maxima de vertices de cada color.
Resulto que ya estaba estudiado porque surge de otros problemasaplicados tambien.
Se sabıa que si la capacidad es chiquita pero la cantidad de colorespuede ser arbitrariamente grande, el problema es difıcil aun engrafos de permutacion.
Junto con un grupo de colegas italianos (S. Mattia y G. Oriolo),encontramos un algoritmo eficiente para coloreo capacitado engrafos de permutacion para cuando la cantidad de colores eschiquita pero la capacidad puede ser arbitrariamente grande. Y elproblema de las encomiendas cuadra en ese caso.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 35: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/35.jpg)
Modelo matematico
¿y las capacidades?
Hay que introducir la variante de coloreo capacitado, donde hayuna cantidad maxima de vertices de cada color.
Resulto que ya estaba estudiado porque surge de otros problemasaplicados tambien.
Se sabıa que si la capacidad es chiquita pero la cantidad de colorespuede ser arbitrariamente grande, el problema es difıcil aun engrafos de permutacion.
Junto con un grupo de colegas italianos (S. Mattia y G. Oriolo),encontramos un algoritmo eficiente para coloreo capacitado engrafos de permutacion para cuando la cantidad de colores eschiquita pero la capacidad puede ser arbitrariamente grande. Y elproblema de las encomiendas cuadra en ese caso.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos
![Page 36: Camiones, encomiendas, y teoría de grafoscms.dm.uba.ar/Members/slaplagn/semana_bak/2010/... · grafos de permutaci on para cuando la cantidad de colores es chiquita pero la capacidad](https://reader035.fdocumento.com/reader035/viewer/2022071008/5fc5493eb822ae62c2138902/html5/thumbnails/36.jpg)
Modelo matematico
¿y las capacidades?
Hay que introducir la variante de coloreo capacitado, donde hayuna cantidad maxima de vertices de cada color.
Resulto que ya estaba estudiado porque surge de otros problemasaplicados tambien.
Se sabıa que si la capacidad es chiquita pero la cantidad de colorespuede ser arbitrariamente grande, el problema es difıcil aun engrafos de permutacion.
Junto con un grupo de colegas italianos (S. Mattia y G. Oriolo),encontramos un algoritmo eficiente para coloreo capacitado engrafos de permutacion para cuando la cantidad de colores eschiquita pero la capacidad puede ser arbitrariamente grande. Y elproblema de las encomiendas cuadra en ese caso.
Flavia Bonomo · Semana de la Matematica 2010, FCEyN, UBA Camiones, encomiendas, y teorıa de grafos