Coloración fraccionaria

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

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

La coloración fraccionaria es un tema de 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 grafos ordinaria . En una coloración de grafos tradicional, a cada vértice de un grafo 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 fraccionaria, se asigna un conjunto de colores a cada vértice de un grafo. El requisito sobre los vértices adyacentes aún se mantiene, 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 fraccionarios puede considerarse como una relajación de la coloración de gráficos tradicional en la programación lineal. De hecho, los problemas de coloración fraccionaria 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: coloración 5:2 del mismo gráfico.

Una coloración b -fold de un grafo G es una asignación de conjuntos de tamaño b a vértices de un grafo de modo que los vértices adyacentes reciban conjuntos disjuntos. Una coloración a : b es una coloración b -fold de entre los colores disponibles. De manera equivalente, se puede definir como un homomorfismo del grafo de Kneser KG _{a , b} . El número cromático b -fold 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}}}$

Nótese 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 puede definirse 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értice , 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 que ${\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 (PL)

El número cromático fraccionario de un grafo 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 incluyen 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 el peso total asignado a cualquier conjunto independiente sea como máximo 1. El teorema de dualidad fuerte de la programación lineal garantiza que las soluciones óptimas de ambos programas lineales tengan el mismo valor. Sin embargo, hay que tener 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 grafo es NP-hard . ^[3] Esto contrasta con el problema de colorear fraccionariamente los bordes de un grafo, que se puede resolver en tiempo polinomial. Esta es una consecuencia directa del teorema de politopo coincidente de Edmonds. ^{[4] [5]}

Aplicaciones

Las aplicaciones de la coloración de grafos fraccionarios incluyen la programación de actividades . En este caso, el grafo G es un grafo de conflictos : una arista 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 activos simultáneamente debe ser un conjunto independiente en el grafo G.

Una coloración óptima de gráficos fraccionarios en G proporciona entonces 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 punto del tiempo 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 interferencias entre transmisiones de radio. Cada transmisión de radio debe estar activa durante 1 unidad de tiempo en total; una coloración óptima del gráfico fraccionario proporciona un programa de longitud mínima (o, equivalentemente, un programa de ancho de banda máximo) que no presenta conflictos.

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

Si además se requiriera 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 los vértices del gráfico proporcionaría un cronograma óptimo: primero los nodos de color 1 están activos durante 1 unidad de tiempo, luego los nodos de color 2 están activos durante 1 unidad de tiempo, y así sucesivamente. Nuevamente, en cualquier punto en el tiempo, el conjunto de nodos activos es un conjunto independiente.

En general, la coloración de gráficos fraccionarios proporciona un cronograma más corto que la coloración de gráficos no fraccionarios; existe una brecha de integralidad . Es posible encontrar un cronograma 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, un enfoque racional a la teoría de grafos . Dover Publication. p. 42. ISBN 978-0486485935., Proposición 3.1.1.
2. László Lovász : "Sobre la relación de coberturas óptimas integrales y fraccionarias", Matemáticas discretas. 13:4 (1975), pág. 383-390.
3. Carsten Lund y Mihalis Yannakakis : "Sobre la dificultad de aproximar problemas de minimización", J. ACM 41:5(1994), pág. 960-981.
4. Hajek, B.; Sasaki, G. (1988). "Programación de enlaces en tiempo polinomial". IEEE Transactions on Information Theory . 34 (5): 910–917. doi :10.1109/18.21215.
5. Schrijver, Alexander (2003). Optimización combinatoria: poliedros y eficiencia . Berlín; Heidelberg; Nueva York, NY: Springer-Verlag. pp. 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.

Véase también

• Coincidencia fraccionaria