La coloración fraccionada es un tema en una rama joven de la teoría de grafos conocida como teoría de grafos fraccionarios . Es una generalización de la coloración de gráficos ordinaria . En una coloración de gráfico tradicional, a cada vértice de un gráfico se le asigna un color, y a los vértices adyacentes, los que están conectados por bordes, se les deben asignar colores diferentes. Sin embargo, en una coloración fraccionada, se asigna un conjunto de colores a cada vértice de un gráfico. El requisito sobre los vértices adyacentes todavía se mantiene, por lo que si dos vértices están unidos por un borde, no deben tener colores en común.
La coloración fraccional de gráficos se puede ver como la relajación de programación lineal de la coloración de gráficos tradicional. De hecho, los problemas de coloración fraccionada son mucho más susceptibles a un enfoque de programación lineal que los problemas de coloración tradicionales.
Definiciones
Una coloración b- pliegue de un gráfico G es una asignación de conjuntos de tamaño b a los vértices de un gráfico de manera que los vértices adyacentes reciben conjuntos disjuntos. Una un : b -Coloreado es un b -fold coloración de un colores disponibles. De manera equivalente, se puede definir como un homomorfismo al gráfico de Kneser KG a , b . El número cromático b -fold es el menos una de tal manera que una un : b existe -Coloreado.
El número cromático fraccionario se define como
Tenga en cuenta que el límite existe porque es subaditivo , es decir
El número cromático fraccionario se puede definir de manera equivalente en términos probabilísticos. es el k más pequeño para el que existe una distribución de probabilidad sobre los conjuntos independientes de G tal que para cada vértice v , dado un conjunto independiente S extraído de la distribución,
Propiedades
Tenemos
donde n ( G ) es el orden de G , α ( G ) es el número de independencia , ω ( G ) es el número de clique yes el número cromático .
Además, el número cromático fraccionario se aproxima al número cromático dentro de un factor logarítmico, [1] de hecho:
Los gráficos de Kneser dan ejemplos donde es arbitrariamente grande, ya que tiempo
Formulación de programación lineal (LP)
El número cromático fraccionario de un gráfico G se puede obtener como solución a un programa lineal . Dejarser el conjunto de todos los conjuntos independientes de G , y seaser el conjunto de todos esos conjuntos independientes que incluyen el vértice x . Para cada conjunto independiente que , a definir una variable real no negativo x I . Luego es el valor mínimo de
sujeto a
para cada vértice .
El dual de este programa lineal calcula el "número de camarilla fraccional", una relajación de los racionales del concepto entero de número de camarilla . Es decir, una ponderación de los vértices de G tal que la ponderación total asignada a cualquier conjunto independiente sea como máximo 1 . El fuerte teorema de la dualidad de la programación lineal garantiza que las soluciones óptimas para ambos programas lineales tengan el mismo valor. Sin embargo, tenga en cuenta que cada programa lineal puede tener un tamaño exponencial en el número de vértices de G , y que calcular el número cromático fraccional de un gráfico es NP-difícil . [2] Esto contrasta con el problema de colorear fraccionadamente los bordes de un gráfico, que se puede resolver en tiempo polinomial. Ésta es una consecuencia directa del teorema del politopo coincidente de Edmonds. [3] [4]
Aplicaciones
Las aplicaciones de la coloración de gráficos fraccionados incluyen la programación de actividades . En este caso, el gráfico G es un gráfico de conflicto : un borde en G entre los nodos u y v denota que u y v no pueden estar activos simultáneamente. Dicho de otro modo, el conjunto de nodos que están activas simultáneamente debe ser un conjunto independiente en el gráfico G .
Una coloración de gráfico fraccional óptima en G proporciona un programa más corto posible, de modo que cada nodo está activo durante (al menos) 1 unidad de tiempo en total, y en cualquier momento el conjunto de nodos activos es un conjunto independiente. Si tenemos una solución x para el programa lineal anterior, simplemente recorremos todos los conjuntos independientes I en un orden arbitrario. Para cada I , dejamos que los nodos de I estén activos duranteunidades de tiempo; mientras tanto, cada nodo que no está en I está inactivo.
En términos más concretos, cada nodo de G podría representar una transmisión de radio en una red de comunicación inalámbrica; los bordes de G representan la interferencia entre transmisiones de radio. Cada transmisión de radio debe estar activa durante 1 unidad de tiempo en total; un color de gráfico fraccional óptimo proporciona un programa de duración mínima (o, de manera equivalente, un programa de ancho de banda máximo) que no presenta conflictos.
Comparación con la coloración de gráficos tradicional
Si uno requiriera además que cada nodo debe estar activo continuamente durante 1 unidad de tiempo (sin apagarlo y encenderlo de vez en cuando), entonces la coloración tradicional de vértices del gráfico proporcionaría un programa óptimo: primero los nodos del color 1 están activos durante 1 vez unidad, entonces los nodos del color 2 están activos por 1 unidad de tiempo, y así sucesivamente. Nuevamente, en cualquier momento, el conjunto de nodos activos es un conjunto independiente.
En general, la coloración de gráficas fraccionarias proporciona un programa más corto que la coloración de gráficas no fraccionarias; hay una brecha de integralidad . Puede ser posible encontrar un horario más corto, a costa de encender y apagar dispositivos (como transmisores de radio) más de una vez.
Notas
- ^ László Lovász : " Sobre la proporción de cubiertas óptimas integrales y fraccionarias ", Matemáticas discretas. 13: 4 (1975), pág. 383-390.
- ^ Carsten Lund y Mihalis Yannakakis : " Sobre la dureza de aproximar los problemas de minimización ", J. ACM 41: 5 (1994), p. 960-981.
- ^ Hajek, B .; Sasaki, G. (1988). "Programación de enlaces en tiempo polinomial". Transacciones IEEE sobre teoría de la información . 34 (5): 910–917. doi : 10.1109 / 18.21215 .
- ^ Schrijver, Alexander (2003). Optimización combinatoria: poliedros y eficiencia . Berlín; Heidelberg; Nueva York, NY: Springer-Verlag. págs. 474 . ISBN 978-3540443896.
Referencias
- Scheinerman, Edward R .; Ullman, Daniel H. (1997), Teoría de grafos fraccionarios , Nueva York: Wiley-Interscience, ISBN 978-0-471-17864-4.
- Godsil, Chris ; Royle, Gordon (2001), Teoría de grafos algebraicos , Nueva York: Springer-Verlag, ISBN 978-0-387-95241-3.