Coloración fraccionada

La coloración fraccionaria es un tema de una rama de la teoría de grafos conocida como teoría fraccionaria de grafos . Es una generalización de la coloración de grafos convencional . En la coloración tradicional, a cada vértice de un grafo se le asigna un color, y los vértices adyacentes —aquellos conectados por aristas— deben tener colores diferentes. En la coloración fraccionaria, sin embargo, se asigna un conjunto de colores a cada vértice. El requisito sobre los vértices adyacentes 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 fraccionaria de grafos puede considerarse como una relajación de programación lineal de la coloración tradicional de grafos. De hecho, los problemas de coloración fraccionaria se prestan mucho mejor a un enfoque de programación lineal que los problemas de coloración tradicionales.

Una coloración b -ésima de un grafo G es una asignación de conjuntos de tamaño b a los vértices de un grafo tal que los vértices adyacentes reciben conjuntos disjuntos . Una coloración a : b es una coloración b -ésima de entre a colores disponibles. De forma equivalente, se puede definir como un homomorfismo al grafo de Kneser KG _{a , b} . El número cromático b -ésimo${\displaystyle \chi _{b}(G)}$es el menor a tal que existe una coloración a : b . Nótese que el número cromático regular${\displaystyle \chi (G)}$es exactamente${\displaystyle \chi _{1}(G)}$.

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

${\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${\displaystyle \chi _{b}(G)}$es subaditivo , lo que significa:${\displaystyle \chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G).}$

El número cromático fraccional puede definirse de forma equivalente en términos probabilísticos.${\displaystyle \chi _{f}(G)}$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 \Pr(v\in S)\geq {\frac {1}{k}}.}$

Tenemos:

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

con igualdad para grafos transitivos en 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${\displaystyle \chi (G)}$es el número cromático .

Además, el número cromático fraccional 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:${\displaystyle \chi (G)/\chi _{f}(G)}$es arbitrariamente grande, ya que:${\displaystyle \chi (KG_{m,n})=m-2n+2,}$mientras${\displaystyle \chi _{f}(KG_{m,n})={\tfrac {m}{n}}.}$

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

${\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 clique fraccionario", una relajación a los racionales del concepto entero de número de clique . 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 tienen el mismo valor. Sin embargo, cabe señalar 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-difícil . ^{[ 3 ]} Esto contrasta con el problema de colorear fraccionariamente las aristas de un grafo, que puede resolverse en tiempo polinomial. Esta es una consecuencia directa del teorema del politopo de emparejamiento de Edmonds . ^{[ 4 ] [ 5 ]}

Las aplicaciones de la coloración fraccionaria de grafos 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 indica 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 fraccionaria óptima de grafos en G proporciona entonces la programación más corta 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 , hacemos que los nodos en I estén activos durante${\displaystyle x_{I}}$unidades 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; las aristas de G representan la interferencia entre transmisiones de radio. Cada transmisión de radio debe estar activa durante una unidad de tiempo; una coloración fraccionaria óptima del grafo proporciona una programación de longitud mínima (o, equivalentemente, una programación de ancho de banda máximo) libre de conflictos.

• 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 algebraica de grafos , Nueva York: Springer-Verlag, ISBN 978-0-387-95241-3.

• Coincidencia fraccionaria