Algoritmo de coloración de bordes para Misra y Gris

El algoritmo de coloración de bordes de Misra y Gris es un algoritmo de tiempo polinomial en la teoría de grafos que encuentra una coloración de borde de cualquier gráfico. La coloración requiere un máximo de colores, donde es el grado máximo del gráfico. Este valor es óptimo para algunas gráficas, y por el teorema de Vizing es un color más que la coloración óptima del resto de las gráficas. $\Delta +1$ $\Delta$

El algoritmo fue publicado en 1992 por Jayadev Misra y David Gries [1] . Es una simplificación del algoritmo de Bela Bolobash [2] .

Este algoritmo es el más rápido de los algoritmos de coloración de bordes casi óptimos conocidos y se ejecuta en el tiempo . Finalmente, se anunció un algoritmo más rápido en un informe técnico de 1985 de Gabov et al., pero nunca se publicó [3] . ${\ estilo de visualización O (| E || V |)}$ $O(|E|{\sqrt {|V|\log |V|)))$

Como regla general, la coloración óptima de los bordes es un problema NP completo, por lo que es poco probable que exista un algoritmo de tiempo polinomial para este problema. Sin embargo, existen algoritmos para la coloración exacta de los bordes con tiempo de ejecución exponencial que brindan una solución óptima.

Aficionados

Se dice que un color x está ausente de un vértice u si para todo (u, z) E(G). ${\ estilo de visualización c (u, z) \ neq x}$ $\en$

El abanico en el vértice u es la secuencia de vértices F[1:k] que satisface las siguientes condiciones:

F[1:k] es una secuencia no vacía de distintos vecinos de u
El borde (F[1], u) E(G) no está coloreado $\en$
Falta el color de la arista (F[i+1], u) en el vértice F[i] para $1\leqslant i<k$

Dado un abanico F, cualquier arista (F[i], X) para es una arista del abanico . Sean c y d dos colores. El camino cd X es el camino que pasa por el vértice X, contiene solo aristas con los colores c y d , y es máximo (no podemos agregar ningún borde con el color de {c, d}). Tenga en cuenta que solo hay una ruta de este tipo para X, ya que como máximo un borde de cada color puede ser adyacente a un vértice dado. $1\leqslant i\leqslant k$

Rotación del ventilador

Dado un ventilador F [1: k ] de un vértice X , la operación "rotación del ventilador" hace lo siguiente (simultáneamente):

c(F[i],X)=c(F[i+1],X)
Decolora el borde (F[k],X)

Esta operación deja la coloración correcta, porque para cada i faltaba el color de . ${\ estilo de visualización c (F [i + 1], X)}$ ${\ estilo de visualización (F [i], X)}$

Inversión de ruta

La operación "cambiar el color de la ruta cd X " cambia todos los colores c en la ruta a d y todos los colores d a c . La inversión de la ruta puede ser útil para liberar un color en X si X es el vértice final de la ruta; si el vértice X estaba adyacente al color c pero no al d , ahora estará adyacente al color d pero no al c , lo que libera el color. c a otra arista adyacente a X. La aplicación de la operación no viola la admisibilidad de la coloración, ya que para los vértices finales solo uno de los colores de {c, d} puede ser adyacente al vértice, y para otros elementos del camino, la operación solo cambia los colores de los bordes, no se agrega ningún color nuevo.

Algoritmo

Entrada: Conde G.

Salida: coloración adecuada de los bordes del gráfico G

Sea U := E(G)

Siempre que U ≠ ∅ ejecute

Tome cualquier borde (u, v) de U.
Sea F[1:k] el abanico máximo u que comienza en F[1]=v.
Sea c el color que no está en u y d el color que no está en F[k].
Invirtiendo el camino cd u
Sea tal que sea un abanico y d esté ausente de w. ${\ estilo de visualización w \ en V (G)}$ $w\in F,F'=[F[1]\dots w]$
Gire F' y establezca c(u, w)=d.
U := U - {(u, v)}

terminar adiós

Prueba de corrección

La corrección del algoritmo se prueba en tres etapas. Primero, se muestra que recolorear el camino cd u garantiza un vértice w tal que es un abanico y d está ausente de w . Entonces esta coloración de borde es correcta y no requiere más colores. $w\in F,F'=[F[1]\dots w]$ $\Delta +1$

Inversión de ruta

Antes de volver a pintar el camino, hay dos casos:

El abanico no tiene bordes coloreados en d . Dado que F es un abanico máximo y d está ausente de F [ k ], se deduce que no hay borde con el color d adyacente a u . De lo contrario, si tal borde existiera, podría unirse a F [ k ], ya que d está ausente en F [ k ], pero F es máxima, obtenemos una contradicción. Entonces d está ausente de u y como c también está ausente de u , el camino cd u está vacío y la inversión no afecta el gráfico. deja _ ${\ estilo de visualización w = F [k]}$
El abanico tiene un borde con color d . Sea (u,F[x+1]) esta arista. Tenga en cuenta que dado que (u,F[1]) no está coloreado. Entonces falta el color d de F [ x ]. Además , dado que el ventilador tiene una longitud k , pero existe . Ahora podemos mostrar que después de volver a colorear para cada , no hay color en F[y]. Tenga en cuenta que antes de cambiar el color, el color no coincidía ni con c ni con d porque c no está en u pero contiene el color d y el coloreado es correcto. La inversión solo afecta a los bordes que están pintados en c o d , por lo que (1) se mantiene. ${\ estilo de visualización x + 1 \ neq 1}$ ${\ estilo de visualización x \ neq k}$ ${\ estilo de visualización F [x + 1]}$ ${\displaystyle y\in \{1,\dots,x-1,x+1,\dots,k\))$ ${\ estilo de visualización (F [y + 1], u)}$ ${\ estilo de visualización (u, F [y + 1])}$ ${\ estilo de visualización (u, F [x + 1])}$

F [ x ] puede o no estar contenido en la ruta de cdu . Si no está contenido en la ruta, el cambio de color no afecta el conjunto de colores faltantes en F [ x ] y d seguirá faltando en él. Podemos poner . De lo contrario, podemos mostrar que F sigue siendo un abanico y d permanece ausente de F [ k ]. Dado que d faltaba en F [ x ] antes del cambio de color, y F [ x ] está en la ruta, F [ x ] es el vértice final de la ruta cd u , y c faltará en F [ x ] después del cambio de color . El repintado cambiará de color de d a c . Entonces, dado que c ahora está ausente de F [ x ] y (1) se cumple, F sigue siendo un abanico. Además , d permanece ausente en F [ k ] porque F [ k ] no está en el camino c u (asumiendo que está en el camino, pero como d está ausente en F [ k ], debe ser el punto final del camino, pero los extremos son u y F [ x ]). Elijamos _ ${\ estilo de visualización w = F [x]}$ ${\ estilo de visualización (u, F [x + 1])}$ ${\ estilo de visualización w = F [k]}$

En cualquier caso, el ventilador es un prefijo de F , lo que significa que también es un ventilador. $F'$ $F'$

La coloración de los bordes es correcta

Esto se puede demostrar por inducción matemática sobre el número de bordes coloreados. Base de inducción: sin bordes coloreados, la coloración es correcta. Paso de inducción: suponga que la coloración fue correcta en la iteración anterior. En la iteración actual, después de volver a colorear la ruta, d desaparece en u y, de acuerdo con el resultado anterior, desaparecerá en w . La rotación no destruye la coloración correcta. Luego, después del ajuste , el color permanece correcto. $F'$ ${\ estilo de visualización c (u, w) = d}$

El algoritmo requiere un máximo de colores $\Delta +1$

En un paso dado, solo se usan los colores c y d . Dado que u es adyacente a al menos un borde no coloreado y su grado está acotado , al menos un color de está disponible para c . Para d F [ k ] puede tener un grado y no tener bordes adyacentes sin color. Entonces es posible que necesite flores. $\Delta$ ${\ estilo de visualización \ {1, \ puntos, \ Delta \}}$ $\Delta$ $\Delta +1$

Dificultad

En cada paso, la rotación elimina el color del borde (u, w), mientras colorea los bordes (u, F[1]) y (u, v), que anteriormente no tenían color. Por lo tanto, aparece un borde de color adicional. Por lo tanto, el bucle se ejecutará una vez. Encontrar el ventilador máximo, los colores c y d , y volver a colorear la ruta cd u se puede hacer a tiempo . Encontrar w y rotar F' toma tiempo. Encontrar y eliminar un borde (u, v) se puede hacer con una pila en tiempo constante (la operación de buscar el último elemento) y esta pila se puede llenar en el tiempo . Por lo tanto, cada operación del ciclo toma tiempo y el tiempo total de ejecución del algoritmo es . $O(|E|)$ ${\ estilo de visualización O (| V |)}$ ${\ estilo de visualización O (\ grados (u)) \ en O (| V |)}$ $O(|E|)$ ${\ estilo de visualización O (| V |)}$ $O(|E|+|E||V|)=O(|E||V|)$

Notas

↑ Misra, Gries, 1992 , pág. 131–133.
↑ Bollobás, 1982 , p. 94.
↑ Gabow, Nishizeki, Kariv, Leven, Terada, 1985 .

Literatura

Jayadev Misra, David Gries . Una demostración constructiva del teorema de Vizing // Cartas de procesamiento de información . - 1992. - T. 41 , núm. 3 . -doi : 10.1016 / 0020-0190(92)90041-S .
Bella Bollobas. Teoría de grafos. — Elsevier, 1982.
Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algoritmos para gráficos de coloración de bordes. - Universidad de Tohoku, 1985. - (Informe técnico TRECIS-8501).