Colorante fraccionario

La coloración fraccionaria es el tema de un campo joven de teoría de grafos conocido como teoría de grafos fraccionarios. La coloración fraccionada es una generalización de la coloración ordinaria . En la coloración tradicional de gráficos, a cada vértice se le asigna un color y a los vértices adyacentes (aquellos conectados por aristas) se les deben asignar diferentes colores. En la coloración fraccionada, a cada vértice se le asigna un conjunto de colores. Las restricciones sobre los vértices adyacentes siguen vigentes, de modo que si dos vértices están conectados por una arista, no deben compartir el mismo color.

La coloración de gráficos fraccionarios puede verse como una relajación de las restricciones la coloración de gráficos tradicional. Además, desde el punto de vista de la programación lineal, los problemas de coloración fraccionarios están más cerca que los problemas de coloración tradicionales.

Definiciones

Una coloración b -fold de un gráfico G es la asignación de conjuntos de b colores a los vértices del gráfico de tal manera que los vértices adyacentes no comparten colores comunes. a : b -coloring es un b - fold coloring que contiene un total de a colores. El número cromático de plegado b χ b ( G ) es el a más pequeño para el que existe una coloración a : b .

El número cromático fraccionario χ f (''G'') es

\chi_{f}(G)=\lim_{b\to \infty} {\frac {\chi_{b}(G)}{b))=\inf_{b}{\ fracción {\chi _{b}(G)}{b}}

Tenga en cuenta que el límite existe porque χ b ( G ) es subaditivo de , lo que significa que χ a + b ( G ) ≤ χ a ( G ) + χ b ( G ).

El número cromático fraccionario también se puede definir en términos de la teoría de la probabilidad. χ f ( G ) es el k más pequeño para el que existe una distribución de probabilidad en conjuntos independientes del gráfico G tal que para cualquier vértice v y conjunto independiente S

\Pr(v\in S)\geq {\frac {1}{k))

Varias propiedades : ${\ estilo de visualización \ chi _ {f} (G)}$

\chi _{f}(G)\geq n(G)/\alpha (G)

{\ estilo de visualización \ omega (G) \ leq \ chi _ {f} (G) \ leq \ chi (G)}

Aquí n( G ) es el orden del gráfico G , α( G ) es el número independiente , ω( G ) es el número clique y χ( G ) es el número cromático .

Número cromático fraccionario en términos de programación lineal

El número cromático fraccionario χ f ( G ) de un gráfico G se puede encontrar resolviendo un problema de programación lineal . Sean ( G ) el conjunto de todos los conjuntos independientes del grafo G , y sean ( G , x ) todos aquellos conjuntos independientes que incluyen el vértice x . Para cada conjunto independiente , definimos una variable real x I no negativa . Ahora χ f ( G ) es el valor mínimo de la función $\mathcal{yo}$ $\mathcal{yo}$ $yo$

\sum _{I\in {\mathcal {I}}(G)}x_{I}

, bajo restricciones para cada vértice .

\sum _{I\in {\mathcal {I}}(G,x)}x_{I}\geq 1

X

El problema dual de este problema de programación lineal calcula un "número de camarilla fraccionario", una relajación a números fraccionarios del concepto entero de un número de camarilla . Así, es posible introducir un peso para los vértices del grafo G para los que el peso total de cualquier conjunto independiente no exceda de 1 . Según el teorema de la dualidad estricta de los problemas de programación lineal, las soluciones óptimas de ambos problemas son las mismas. Tenga en cuenta, sin embargo, que ambos problemas tienen un tamaño que depende exponencialmente del número de vértices del gráfico G , por lo que calcular el número cromático fraccionario del gráfico es un problema NP-difícil . [1] Esto contrasta con el problema de coloración de líneas de gráficos fraccionarios, que se puede encontrar en tiempo polinomial, que es una consecuencia directa del teorema de Edmonds. [2] [3]

Aplicaciones

La coloración de gráficos fraccionarios se utiliza en la programación . En este caso, el gráfico G es un gráfico de conflicto : una arista en G entre los vértices u y v significa que u y v no se pueden ejecutar al mismo tiempo. Entonces , los trabajos que se ejecutan al mismo tiempo deben ser un conjunto independiente en el gráfico G.

Una coloración fraccionada óptima en G proporciona un programa con el menor tiempo total en el que cualquier vértice (trabajo) se ejecuta (al menos) una vez y en cualquier momento dado los vértices activos forman un conjunto independiente. Si tenemos una solución x para el problema de programación lineal descrito anteriormente, simplemente recorremos todos los conjuntos independientes I en un orden arbitrario. Para cada I , realizamos trabajos desde I en intervalos de tiempo. El resto del tiempo no se realizan trabajos de I. ${\ Displaystyle x_ {yo}}$

Ejemplo más específico. Sea cada vértice del grafo G un transmisor de radio en una red inalámbrica. Entonces los bordes G se pueden representar como la interferencia de los transmisores de radio. Cada uno de los transmisores de radio debe trabajar una unidad de tiempo en total. La coloración fraccional óptima proporciona el programa de tiempo mínimo (es decir, el programa de rendimiento máximo) sin conflictos.

Comparación con la coloración tradicional de gráficos

Si existe el requisito de que el vértice debe funcionar de forma continua , sin cambiar, entonces la coloración tradicional del gráfico proporciona el programa óptimo: primero, los vértices con el primer color funcionan durante una unidad de tiempo, luego los vértices del color 2, y pronto. Nuevamente, en cada momento del tiempo, los vértices de trabajo forman un conjunto independiente.

Como regla general, la coloración fraccionada del gráfico da un horario más corto que el habitual. Pero este horario más corto se obtiene encendiendo/apagando dispositivos (como radios) más de una vez.

Notas

↑ Carsten Lund y Mihalis Yannakakis : " Sobre la dificultad de aproximar problemas de minimización ", J. ACM 41:5(1994), p. 960-981.
↑ Bruce Hajek y Galen Sasaki: " Programación de enlaces en tiempo polinomial ", IEEE Transactions on Information Theory 34:5(1988), p. 910-917.
↑ Alexander Schrijver. Optimización Combinatoria: Poliedros y Eficiencia . — Berlín; Heidelberg; Nueva York, NY: Springer-Verlag, 2003. - página 474 . — ISBN 3540443894 .

Enlaces

Edward R. Scheinerman, Daniel H. Ullman. Teoría de grafos fraccionarios. - Nueva York: Wiley-Interscience, 1997. - ISBN 0-471-17864-0 . .
Chris Godsil, Gordon Royle. Teoría algebraica de grafos. - Nueva York: Springer-Verlag, 2001. - ISBN 0-387-95241-1 . .