Coloración fraccionada

Coloración de gráficos donde a los elementos del gráfico se les asignan conjuntos de colores

Coloración 5:2 del gráfico dodecaédrico . No existe una coloración 4:2 de este gráfico.

La coloración fraccional es un tema de una rama joven de la teoría de grafos conocida como teoría de grafos fraccionados. Es una generalización de la coloración de gráficos ordinaria . En la coloración tradicional de un gráfico, a cada vértice de un gráfico se le asigna un color, y a los vértices adyacentes (aquellos conectados por aristas) 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 sigue siendo válido, por lo que si dos vértices están unidos por una arista, no deben tener colores en común.

La coloración de gráficos fraccionados puede verse como la relajación de la 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

Arriba: coloración 3:1 del ciclo en 5 vértices y la coloración 6:2 correspondiente.
Abajo: Coloreado 5:2 del mismo gráfico.

Una coloración b veces de un gráfico G es una asignación de conjuntos de tamaño b a vértices de un gráfico de modo que los vértices adyacentes reciban conjuntos disjuntos. Una coloración a : b es una coloración b de los colores disponibles. De manera equivalente, se puede definir como un homomorfismo del gráfico de Kneser KG _{a , b} . El número cromático b veces es el menor a tal que existe una coloración a : b . ${\displaystyle \chi _{b}(G)}$

El número cromático fraccionario se define como: ${\displaystyle \chi _{f}(G)}$

${\displaystyle \chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}}$

Tenga en cuenta que el límite existe porque es subaditivo , es decir: ${\displaystyle \chi _{b}(G)}$ ${\displaystyle \chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G).}$

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 cual 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: ${\displaystyle \chi _{f}(G)}$

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

Propiedades

Tenemos:

${\displaystyle \chi _{f}(G)\geq {\frac {n(G)}{\alpha (G)}},}$

con igualdad para gráficos transitivos de vértices , donde n ( G ) es el orden de G , α( G ) es el número de independencia . ^[1]

Además:

${\displaystyle \omega (G)\leq \chi _{f}(G)\leq \chi (G),}$

donde ω( G ) es el número de camarilla y es el número cromático . ${\displaystyle \chi (G)}$

Además, el número cromático fraccionario se aproxima al número cromático dentro de un factor logarítmico, ^[2] de hecho:

${\displaystyle {\frac {\chi (G)}{1+\ln \alpha (G)}}\leq \chi _{f}(G)\leq {\frac {\chi _{b}(G)}{b}}\leq \chi (G).}$

Los gráficos de Kneser dan ejemplos donde: es arbitrariamente grande, ya que: mientras ${\displaystyle \chi (G)/\chi _{f}(G)}$ ${\displaystyle \chi (KG_{m,n})=m-2n+2,}$ ${\displaystyle \chi _{f}(KG_{m,n})={\tfrac {m}{n}}.}$

Formulación de programación lineal (LP)

El número cromático fraccionario de un gráfico G se puede obtener como solución de un programa lineal . Sea el conjunto de todos los conjuntos independientes de G , y sea el conjunto de todos aquellos conjuntos independientes que incluyan el vértice x . Para cada conjunto independiente I , defina una variable real no negativa x _I. Entonces es el valor mínimo de: ${\displaystyle \chi _{f}(G)}$ ${\displaystyle {\mathcal {I}}(G)}$ ${\displaystyle {\mathcal {I}}(G,x)}$ ${\displaystyle \chi _{f}(G)}$

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

sujeto a:

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

para cada vértice . ${\displaystyle x}$

El dual de este programa lineal calcula el "número de camarilla fraccionario", 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 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 fraccionario de un gráfico es NP-duro . ^[3] Esto contrasta con el problema de colorear fraccionariamente 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. ^{[4] [5]}

Aplicaciones

Las aplicaciones de coloración de gráficos fraccionarios 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 otra manera, el conjunto de nodos que están activos simultáneamente debe ser un conjunto independiente en el gráfico G.

Una coloración de gráfico fraccional óptima en G proporciona el cronograma 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 sea 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 en I estén activos durante unidades de tiempo; mientras tanto, cada nodo que no esté en I está inactivo. ${\displaystyle x_{I}}$

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 interferencia entre transmisiones de radio. Cada transmisión de radio debe estar activa durante 1 unidad de tiempo en total; una coloración de gráfico fraccional óptima proporciona una programación de longitud mínima (o, equivalentemente, una programación de ancho de banda máximo) que está libre de conflictos.

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

Si se requiriera además que cada nodo deba 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 cronograma óptimo: primero, los nodos del color 1 están activos por 1 vez. unidad, entonces los nodos del color 2 están activos durante 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áficos fraccionados proporciona un cronograma más corto que la coloración de gráficos no fraccionarios; hay una brecha de integralidad . Es posible encontrar un horario más corto, a costa de encender y apagar dispositivos (como transmisores de radio) más de una vez.

Notas

1. Scheinerman, Edward R.; Ullman, Daniel H. (2013). Teoría de grafos fraccionarios, una aproximación racional a la teoría de grafos . Publicación de Dover. pag. 42.ISBN​ 978-0486485935., Proposición 3.1.1.
2. László Lovász : "Sobre la relación de coberturas integrales y fraccionarias óptimas", Matemáticas discretas. 13:4 (1975), pág. 383-390.
3. Carsten Lund y Mihalis Yannakakis : "Sobre la dureza de la aproximación de problemas de minimización", J. ACM 41:5(1994), p. 960-981.
4. Hajek, B.; Sasaki, G. (1988). "Programación de enlaces en tiempo polinómico". Transacciones IEEE sobre teoría de la información . 34 (5): 910–917. doi : 10.1109/18.21215.
5. Schrijver, Alejandro (2003). Optimización combinatoria: poliedros y eficiencia . Berlina; Heidelberg; Nueva York, Nueva York: 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.

Ver también

• Emparejamiento fraccional