TEORÍA DE TÉRMINOS DE GRAFOS

No debe confundirse con la coloración Edge .

Una coloración de vértice adecuada del gráfico de Petersen con 3 colores, el número mínimo posible.

En la teoría de grafos , la coloración de grafos es un caso especial de etiquetado de grafos ; es una asignación de etiquetas tradicionalmente llamadas "colores" a elementos de un gráfico sujetos a ciertas restricciones. En su forma más simple, es una forma de colorear los vértices de un gráfico de manera que no haya dos vértices adyacentes del mismo color; Esto se llama coloración de vértice . Del mismo modo, un color de borde asigna un color a cada borde para que no haya dos bordes adyacentes del mismo color, y un color de cara de un gráfico plano asigna un color a cada cara o región para que no haya dos caras que compartan un límite que tengan el mismo color. el mismo color.

La coloración de vértices se usa generalmente para introducir problemas de coloración de gráficos, ya que otros problemas de coloración se pueden transformar en una instancia de coloración de vértices. Por ejemplo, un color de borde de un gráfico es solo un color de vértice de su gráfico de línea , y un color de cara de un gráfico plano es solo un color de vértice de su dual . Sin embargo, los problemas de coloración que no son vértices a menudo se expresan y estudian tal como están . Esto es en parte pedagógico y en parte porque algunos problemas se estudian mejor en su forma no vértice, como en el caso de la coloración de bordes.

La convención de usar colores se origina al colorear los países de un mapa, donde cada cara está literalmente coloreada. Esto se generalizó para colorear las caras de un gráfico incrustado en el plano. Por dualidad plana se volvió coloreando los vértices, y de esta forma se generaliza a todos los gráficos. En las representaciones matemáticas e informáticas, es típico usar los primeros enteros positivos o no negativos como "colores". En general, se puede usar cualquier conjunto finito como "conjunto de colores". La naturaleza del problema de coloración depende de la cantidad de colores, pero no de lo que son.

La coloración gráfica disfruta de muchas aplicaciones prácticas, así como desafíos teóricos. Además de los tipos clásicos de problemas, también se pueden establecer diferentes limitaciones en el gráfico, o en la forma en que se asigna un color, o incluso en el color mismo. Incluso ha alcanzado popularidad entre el público en general en la forma del popular rompecabezas de números Sudoku . La coloración de gráficos sigue siendo un campo de investigación muy activo.

Historia [ editar ]

Ver también: Historia del teorema de los cuatro colores e Historia de la teoría de grafos.

Los primeros resultados sobre la coloración de gráficos tratan casi exclusivamente con gráficas planas en forma de coloración de mapas . Mientras intentaba colorear un mapa de los condados de Inglaterra, Francis Guthrie postuló la conjetura de cuatro colores , señalando que cuatro colores eran suficientes para colorear el mapa de modo que ninguna región que compartiera un borde común recibiera el mismo color. El hermano de Guthrie le pasó la pregunta a su profesor de matemáticas Augustus de Morgan en el University College , quien lo mencionó en una carta a William Hamilton en 1852. Arthur Cayley planteó el problema en una reunión de la London Mathematical Societyen 1879. El mismo año, Alfred Kempe publicó un artículo que afirmaba establecer el resultado, y durante una década se consideró resuelto el problema de los cuatro colores. Por su logro, Kempe fue elegido miembro de la Royal Society y más tarde presidente de la London Mathematical Society. ^[1]

En 1890, Heawood señaló que el argumento de Kempe estaba equivocado. Sin embargo, en ese documento demostró el teorema de los cinco colores , diciendo que cada mapa plano puede ser coloreado con no más de cinco colores, utilizando ideas de Kempe. En el siglo siguiente, se desarrolló una gran cantidad de trabajo y teorías para reducir el número de colores a cuatro, hasta que Kenneth Appel y Wolfgang Haken probaron finalmente el teorema de los cuatro colores en 1976 . La prueba se remonta a las ideas de Heawood y Kempe y en gran medida ignora los desarrollos que intervienen. ^[2] La prueba del teorema de los cuatro colores también es notable por ser la primera prueba importante asistida por computadora.

En 1912, George David Birkhoff introdujo el polinomio cromático para estudiar los problemas de coloración, que Tutte generalizó al polinomio de Tutte , estructuras importantes en la teoría de grafos algebraicos . Kempe ya había llamado la atención sobre el caso general, no plano en 1879, ^[3] y muchos resultados sobre generalizaciones de coloración de gráfico plano en superficies de orden superior seguido a principios del siglo XX.

En 1960, Claude Berge formuló otra conjetura sobre la coloración gráfica, la conjetura gráfica fuerte y perfecta , originalmente motivada por un concepto teórico de la información llamado capacidad de error cero de un gráfico introducido por Shannon . La conjetura quedó sin resolver durante 40 años, hasta que se estableció como el célebre teorema fuerte perfecta gráfico por Chudnovsky , Robertson , Seymour , y Thomas en 2002.

La coloración de gráficos se ha estudiado como un problema algorítmico desde principios de la década de 1970: el problema del número cromático es uno de los 21 problemas completos de NP de Karp de 1972, y aproximadamente al mismo tiempo se desarrollaron varios algoritmos de tiempo exponencial basados ​​en el retroceso y la eliminación -recurrencia de la contracción de Zykov (1949) . Una de las principales aplicaciones de la coloración de gráficos, la asignación de registros en compiladores, se introdujo en 1981.

Definición y terminología [ editar ]

Este gráfico puede ser de 3 colores de 12 maneras diferentes.

Coloración de vértices [ editar ]

Cuando se usa sin ninguna calificación, una coloración de un gráfico es casi siempre una coloración de vértice adecuada , es decir, un etiquetado de los vértices del gráfico con colores de modo que no haya dos vértices que compartan el mismo borde con el mismo color. Dado que un vértice con un bucle (es decir, una conexión directamente de vuelta a sí mismo) nunca podría tener el color adecuado, se entiende que los gráficos en este contexto no tienen bucles.

La terminología del uso de colores para las etiquetas de vértices se remonta al color del mapa. Las etiquetas como rojo y azul solo se usan cuando el número de colores es pequeño, y normalmente se entiende que las etiquetas se extraen de los enteros {1, 2, 3, ...}.

Una coloración utilizando en la mayoría de k colores se llama un (adecuado) k -Coloreado . El número más pequeño de colores necesarios para colorear un gráfico G se llama su número cromático , y a menudo se denota χ ( G ). A veces se usa γ ( G ), ya que χ ( G ) también se usa para denotar la característica de Euler de un gráfico. Un gráfico al que se le puede asignar un color k (apropiado) es k -colorable , y es k -cromático si su número cromático es exactamente k . Un subconjunto de vértices asignado al mismo color se denomina clase de color. , cada clase forma un conjunto independiente . Por lo tanto, un k- coloring es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k-partite y k-colorable tienen el mismo significado.

Polinomio cromático [ editar ]

Todos los gráficos no isomórficos en 3 vértices y sus polinomios cromáticos. El gráfico vacío E ₃ (rojo) admite una coloración 1, los otros no admiten tales coloraciones. El gráfico verde admite 12 colores con 3 colores.

Artículo principal: polinomio cromático

El polinomio cromático cuenta el número de formas en que se puede colorear un gráfico utilizando no más de un número dado de colores. Por ejemplo, usando tres colores, el gráfico en la imagen adyacente se puede colorear de 12 maneras. Con solo dos colores, no se puede colorear en absoluto. Con cuatro colores, se puede colorear de 24 + 4⋅12 = 72 formas: ¡usando los cuatro colores, hay 4! = 24 colores válidos ( cada asignación de cuatro colores a cualquier gráfico de 4 vértices es un color apropiado); y para cada elección de tres de los cuatro colores, hay 12 colores válidos de 3 colores. Entonces, para el gráfico en el ejemplo, una tabla del número de colores válidos comenzaría así:

Colores disponibles	1	2	3	4 4	...
Numero de colorantes	0 0	0 0	12	72	...

El polinomio cromático es una función P ( G ,  T ) que cuenta el número de t -colorings de  G . Como su nombre indica, para una G dada, la función es de hecho un polinomio en  t . Para el gráfico de ejemplo, P ( G ,  t ) =  t ( t  - 1) ² ( t  - 2), y de hecho  P ( G , 4) = 72.

El polinomio cromático incluye al menos tanta información sobre la colorabilidad de G como el número cromático. De hecho, χ es el entero positivo más pequeño que no es una raíz del polinomio cromático

{\ displaystyle \ chi (G) = \ min \ {k \, \ colon \, P (G, k)> 0 \}.}

Polinomios cromáticos para ciertos gráficos.

Triángulo K 3	$${\ displaystyle t (t-1) (t-2)}
Gráfico completo K n	$${\ displaystyle t (t-1) (t-2) \ cdots (t- (n-1))}
Árbol con n vértices	$${\ displaystyle t (t-1) ^ {n-1}}
Ciclo C n	$${\ displaystyle (t-1) ^ {n} + (- 1) ^ {n} (t-1)}
Gráfico de Petersen	$${\ displaystyle t (t-1) (t-2) (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775t-352)}

Coloración de bordes [ editar ]

Artículo principal: Coloración de bordes

Un color de borde de un gráfico es un color apropiado de los bordes , lo que significa una asignación de colores a los bordes para que ningún vértice incida en dos bordes del mismo color. Una coloración de borde con k colores se llama k -edge-coloring y es equivalente al problema de dividir el conjunto de bordes en k coincidencias . El número más pequeño de colores necesarios para una coloración de borde de un gráfico G es el índice cromático , o número cromático de borde , χ ′ ( G ). Una coloración Tait es una coloración de 3 bordes de un gráfico cúbico . losEl teorema de cuatro colores es equivalente a la afirmación de que cada gráfico cúbico plano sin puente admite una coloración Tait.

Coloración total [ editar ]

Artículo principal: coloración total

La coloración total es un tipo de coloración en los vértices y bordes de un gráfico. Cuando se usa sin ninguna calificación, siempre se supone que una coloración total es adecuada en el sentido de que no se asignan vértices adyacentes, ni bordes adyacentes, y ningún borde y sus vértices finales del mismo color. El número cromático total χ ″ (G) de un gráfico G es el menor número de colores necesarios en cualquier coloración total de G.

Coloración sin etiqueta [ editar ]

Un color sin etiquetar de un gráfico es una órbita de un color bajo la acción del grupo de automorfismo del gráfico. Si interpretamos una coloración de un gráfico en$${\ displaystyle d} vértices como un vector en $${\ displaystyle \ mathbb {Z} ^ {d}}, la acción de un automorfismo es una permutación de los coeficientes de la coloración. Hay análogos de los polinomios cromáticos que cuentan el número de colorantes no etiquetados de un gráfico de un conjunto de colores finitos dado.

Propiedades [ editar ]

Límites en el número cromático [ editar ]

Asignar colores distintos a vértices distintos siempre produce una coloración adecuada, por lo que

$${\ displaystyle 1 \ leq \ chi (G) \ leq n.}

Los únicos gráficos que pueden ser de 1 color son gráficos sin bordes . Un gráfico completo $${\ displaystyle K_ {n}}de n vértices requiere$${\ displaystyle \ chi (K_ {n}) = n}colores. En una coloración óptima debe haber al menos uno de los bordes m del gráfico entre cada par de clases de color, por lo que

$${\ displaystyle \ chi (G) (\ chi (G) -1) \ leq 2m.}

Si G contiene una camarilla de tamaño k , entonces se necesitan al menos k colores para colorear esa camarilla; en otras palabras, el número cromático es al menos el número de camarilla:

$${\ displaystyle \ chi (G) \ geq \ omega (G).}

Para gráficos perfectos, este límite es ajustado. Encontrar camarillas se conoce como problema de camarilla .

Los gráficos de 2 colores son exactamente los gráficos bipartitos , incluidos los árboles y los bosques. Según el teorema de los cuatro colores, cada gráfico plano puede ser de 4 colores.

Una coloración codiciosa muestra que cada gráfico se puede colorear con un color más que el grado máximo de vértice ,

$${\ displaystyle \ chi (G) \ leq \ Delta (G) +1.}

Los gráficos completos tienen $${\ displaystyle \ chi (G) = n} y $${\ displaystyle \ Delta (G) = n-1}, y los ciclos impares tienen$${\ displaystyle \ chi (G) = 3} y $${\ displaystyle \ Delta (G) = 2}, por lo que para estos gráficos, este límite es el mejor posible. En todos los demás casos, el límite puede mejorarse ligeramente; El teorema de Brooks ^[4] establece que

Teorema de Brooks :$${\ displaystyle \ chi (G) \ leq \ Delta (G)}para un gráfico simple conectado G , a menos que G sea ​​un gráfico completo o un ciclo impar.

Límites inferiores en el número cromático [ editar ]

Se han descubierto varios límites inferiores para los límites cromáticos a lo largo de los años:

El límite de Hoffman: Let$${\ displaystyle W} ser una matriz simétrica real tal que $${\ displaystyle W_ {i, j} = 0} cuando $${\ displaystyle (i, j)} no es una ventaja en $${\ displaystyle G}. Definir$${\ displaystyle \ chi _ {W} (G) = 1 - {\ tfrac {\ lambda _ {\ max} (W)} {\ lambda _ {\ min} (W)}}}, dónde $${\ displaystyle \ lambda _ {\ max} (W), \ lambda _ {\ min} (W)} son los valores propios más grandes y más pequeños de $${\ displaystyle W}. Definir$${\ displaystyle \ chi _ {H} (G) = \ max _ {W} \ chi _ {W} (G)}, con $${\ displaystyle W}como anteriormente. Luego:

$${\ displaystyle \ chi _ {H} (G) \ leq \ chi (G)}.

Número cromático del vector : Let$${\ displaystyle W} ser una matriz semi-definida positiva tal que $${\ displaystyle W_ {i, j} \ leq - {\ tfrac {1} {k-1}}} cuando $${\ displaystyle (i, j)} es una ventaja en $${\ displaystyle G}. Definir$${\ displaystyle \ chi _ {V} (G)} ser el menor k para el cual dicha matriz $${\ displaystyle W}existe Luego

$${\ displaystyle \ chi _ {V} (G) \ leq \ chi (G)}.

Número de Lovász : el número de Lovász de un gráfico complementario, también es un límite inferior en el número cromático:

$${\ displaystyle \ vartheta ({\ bar {G}}) \ leq \ chi (G)}.

Número cromático fraccionario : el número cromático fraccional de un gráfico es también un límite inferior en el número cromático:

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

Estos límites se ordenan de la siguiente manera:

$${\ displaystyle \ chi _ {H} (G) \ leq \ chi _ {V} (G) \ leq \ vartheta ({\ bar {G}}) \ leq \ chi _ {f} (G) \ leq \ chi (G)}.

Gráficos con alto número cromático [ editar ]

Los gráficos con grandes camarillas tienen un número cromático alto, pero lo contrario no es cierto. El gráfico de Grötzsch es un ejemplo de un gráfico de 4 cromáticos sin triángulo, y el ejemplo se puede generalizar a los Mycielskians .

Teorema de Mycielski ( Alexander Zykov  1949 , Jan Mycielski  1955 ): existen gráficos sin triángulos con un número cromático alto arbitrariamente.

Según el teorema de Brooks, los gráficos con un alto número cromático deben tener un alto grado máximo. Otra propiedad local que conduce a un alto número cromático es la presencia de una gran camarilla. Pero la colorabilidad no es un fenómeno completamente local: un gráfico con una circunferencia alta se ve localmente como un árbol, porque todos los ciclos son largos, pero su número cromático no necesita ser 2:

Teorema (Erdős): existen gráficos de circunferencia arbitrariamente alta y número cromático ^[5] .

Límites en el índice cromático [ editar ]

Una coloración de borde de G es una coloración de vértice de su gráfico lineal $${\ displaystyle L (G)}, y viceversa. Así,

$${\ displaystyle \ chi '(G) = \ chi (L (G)).}

Existe una fuerte relación entre la colorabilidad de los bordes y el grado máximo del gráfico. $${\ displaystyle \ Delta (G)}. Como todos los bordes incidentes con el mismo vértice necesitan su propio color, tenemos

$${\ displaystyle \ chi '(G) \ geq \ Delta (G).}

Además,

Teorema de Kőnig : $${\ displaystyle \ chi '(G) = \ Delta (G)}si G es bipartito

En general, la relación es aún más fuerte que la que da el teorema de Brooks para la coloración de vértices:

Teorema de Vizing: una gráfica de grado máximo$${\ displaystyle \ Delta} tiene número de borde cromático $${\ displaystyle \ Delta} o $${\ displaystyle \ Delta +1}.

Otras propiedades [ editar ]

Un gráfico tiene un color k si y solo si tiene una orientación acíclica para la cual el camino más largo tiene una longitud como máximo k ; Este es el teorema de Gallai – Hasse – Roy – Vitaver ( Nešetřil y Ossona de Mendez 2012 ).

Para los gráficos planos, los colores de los vértices son esencialmente duales a flujos de cero en ninguna parte .

Sobre gráficos infinitos, se sabe mucho menos. Los siguientes son dos de los pocos resultados sobre la coloración infinita de gráficos:

• Si todas las subgrafías finitas de un gráfico infinito G son k -colorables, entonces también lo es G , bajo el supuesto del axioma de elección . Este es el teorema de De Bruijn-Erd de De Bruijn y Erdős (1951) .
• Si un gráfico admite un color n completo por cada n ≥ n ₀ , admite un color completo infinito ( Fawcett 1978 ).

Problemas abiertos [ editar ]

Como se indicó anteriormente, $${\ displaystyle \ omega (G) \ leq \ chi (G) \ leq \ Delta (G) +1.} Una conjetura de Reed de 1998 es que el valor está esencialmente más cerca del límite inferior, ${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

Se desconoce el número cromático del plano , donde dos puntos son adyacentes si tienen una unidad de distancia, aunque es uno de 5, 6 o 7. Otros problemas abiertos relacionados con el número cromático de gráficos incluyen la conjetura de Hadwiger que indica que cada gráfico con el número cromático k tiene un gráfico completo en k vértices como menor , la conjetura de Erdős-Faber-Lovász que limita el número cromático de uniones de gráficos completos que tienen exactamente un vértice en común para cada par, y la conjetura de Albertson que entre k -Gráficos cromáticos, los gráficos completos son los que tienen menorcruzar número .

Cuando Birkhoff y Lewis introdujeron el polinomio cromático en su ataque al teorema de los cuatro colores, conjeturaron que para los gráficos planos G , el polinomio$${\ displaystyle P (G, t)} no tiene ceros en la región $${\ displaystyle [4, \ infty)}. Aunque se sabe que dicho polinomio cromático no tiene ceros en la región$${\ displaystyle [5, \ infty)} y eso $${\ displaystyle P (G, 4) \ neq 0}, su conjetura sigue sin resolverse. También sigue siendo un problema sin resolver caracterizar gráficos que tienen el mismo polinomio cromático y determinar qué polinomios son cromáticos.

Algoritmos [ editar ]

Coloración gráfica
Decisión
Nombre	Graph colorante, colorante vértice, k -Coloreado
Entrada	Grafica G con n vértices. Entero k
Salida	¿ Admite G una coloración de vértice adecuada con k colores?
Tiempo de ejecución	O (2 n n ) [6]
Complejidad	NP-complete
Reducción de	3-satisfacción
Garey – Johnson	GT4
Mejoramiento
Nombre	Número cromático
Entrada	Grafica G con n vértices.
Salida	χ ( G )
Complejidad	NP-hard
Aproximabilidad	O ( n  (log n ) −3 (log log n ) 2 )
Inaproximabilidad	O ( n 1 − ε ) a menos que P = NP
Problema de conteo
Nombre	Polinomio cromático
Entrada	Grafica G con n vértices. Entero k
Salida	El número P  ( G , k ) de colorantes k propios de G
Tiempo de ejecución	O (2 n n )
Complejidad	# P-completo
Aproximabilidad	FPRAS para casos restringidos
Inaproximabilidad	Sin PTAS a menos que P = NP

Tiempo polinómico [ editar ]

Determinar si un gráfico puede ser coloreado con 2 colores es equivalente a determinar si el gráfico es o no bipartito y, por lo tanto, computable en tiempo lineal usando la búsqueda de amplitud primero o la búsqueda de profundidad primero . De manera más general, el número cromático y una coloración correspondiente de gráficos perfectos se pueden calcular en tiempo polinómico usando programación semidefinida . Las fórmulas cerradas para polinomios cromáticos se conocen para muchas clases de gráficos, como bosques, gráficos cordales, ciclos, ruedas y escaleras, por lo que estos pueden evaluarse en tiempo polinómico.

Si el gráfico es plano y tiene un ancho de rama bajo (o no es plano pero tiene una descomposición de rama conocida), entonces puede resolverse en tiempo polinómico mediante programación dinámica. En general, el tiempo requerido es polinómico en el tamaño del gráfico, pero exponencial en el ancho de la rama.

Algoritmos exactos [ editar ]

La búsqueda de fuerza bruta para un k- coloring considera cada uno de los$${\ displaystyle k ^ {n}}asignaciones de k colores a n vértices y verifica para cada uno si es legal. Para calcular el número cromático y el polinomio cromático, este procedimiento se utiliza para cada$${\ displaystyle k = 1, \ ldots, n-1}, poco práctico para todos los gráficos de entrada, excepto los más pequeños.

Usando programación dinámica y un límite en el número de conjuntos independientes máximos , la capacidad de coloración k se puede decidir en tiempo y espacio$${\ displaystyle O (2.445 ^ {n})}. ^[7] Utilizando el principio de inclusión-exclusión y el algoritmo de Yates para la transformación rápida zeta, la capacidad de coloración k se puede decidir a tiempo$${\ displaystyle O (2 ^ {n} n)}^[6] para cualquier k . Se conocen algoritmos más rápidos para la colorabilidad 3 y 4, que se pueden decidir a tiempo$${\ displaystyle O (1.3289 ^ {n})}^[8] y$${\ displaystyle O (1.7272 ^ {n})}, ^[9] respectivamente.

Contracción [ editar ]

La contraccion $${\ displaystyle G / uv}de un gráfico G es el gráfico obtenido al identificar los vértices u y v , y eliminar cualquier borde entre ellos. Los bordes restantes originalmente incidente a U o V son ahora incidente a su identificación. Esta operación juega un papel importante en el análisis de la coloración de gráficos.

El número cromático satisface la relación de recurrencia :

$${\ displaystyle \ chi (G) = {\ text {min}} \ {\ chi (G + uv), \ chi (G / uv) \}}

debido a Zykov (1949) , donde u y v son vértices no adyacentes, y$${\ displaystyle G + uv}es el gráfico con el borde uv agregado. Varios algoritmos se basan en la evaluación de esta recurrencia y el árbol de cálculo resultante a veces se denomina árbol de Zykov. El tiempo de ejecución se basa en una heurística para elegir los vértices u y v .

El polinomio cromático satisface la siguiente relación de recurrencia

$${\ displaystyle P (G-uv, k) = P (G / uv, k) + P (G, k)}

donde u y v son vértices adyacentes, y$${\ displaystyle G-uv}es el gráfico con el borde uv eliminado.$${\ displaystyle P (G-uv, k)}representa el número de posibles colores adecuados del gráfico, donde los vértices pueden tener los mismos o diferentes colores. Luego, los colores adecuados surgen de dos gráficos diferentes. Para explicar, si los vértices u y v tienen colores diferentes, entonces también podríamos considerar un gráfico donde u y v son adyacentes. Si u y v tienen los mismos colores, también podríamos considerar un gráfico donde se contraigan u y v . La curiosidad de Tutte sobre qué otras propiedades gráficas satisfacían esta recurrencia lo llevó a descubrir una generalización bivariada del polinomio cromático, el polinomio de Tutte .

Estas expresiones dan lugar a un procedimiento recursivo llamado algoritmo de eliminación-contracción , que forma la base de muchos algoritmos para la coloración de gráficos. El tiempo de ejecución satisface la misma relación de recurrencia que los números de Fibonacci , por lo que, en el peor de los casos, el algoritmo se ejecuta a tiempo dentro de un factor polinómico de$${\ displaystyle \ left ({\ tfrac {1 + {\ sqrt {5}}} {2}} \ right) ^ {n + m} = O (1.6180 ^ {n + m})}para n vértices ym aristas. ^[10] El análisis se puede mejorar dentro de un factor polinómico del número$${\ displaystyle t (G)}de árboles de expansión del gráfico de entrada. ^[11] En la práctica, se emplean estrategias de ramificación y unión y rechazo de isomorfismo gráfico para evitar algunas llamadas recursivas. El tiempo de ejecución depende de la heurística utilizada para elegir el par de vértices.

Coloración codiciosa [ editar ]

Artículo principal: coloración codiciosa

Dos colores codiciosos del mismo gráfico usando diferentes órdenes de vértices. El ejemplo correcto generaliza a gráficos de 2 colores con n vértices, donde el algoritmo codicioso gasta$${\ displaystyle n / 2} colores.

El algoritmo codicioso considera los vértices en un orden específico$${\ displaystyle v_ {1}}, ...,$${\ displaystyle v_ {n}} y asigna a $${\ displaystyle v_ {i}} El color más pequeño disponible no utilizado por $${\ displaystyle v_ {i}}los vecinos entre $${\ displaystyle v_ {1}}, ...,$${\ displaystyle v_ {i-1}}, agregando un color fresco si es necesario. La calidad del color resultante depende del orden elegido. Existe un orden que conduce a una coloración codiciosa con el número óptimo de$${\ displaystyle \ chi (G)}colores. Por otro lado, los colores codiciosos pueden ser arbitrariamente malos; por ejemplo, el gráfico de la corona en n vértices puede ser de 2 colores, pero tiene un orden que conduce a un color codicioso con$${\ displaystyle n / 2} colores.

Para los gráficos cordales , y para casos especiales de gráficos cordales, como los gráficos de intervalos y los gráficos de indiferencia , el algoritmo de coloración codicioso se puede utilizar para encontrar coloraciones óptimas en el tiempo polinómico, eligiendo el orden de vértices como el reverso de un orden de eliminación perfecto para el grafico. Los gráficos perfectamente ordenables generalizan esta propiedad, pero es NP-difícil encontrar un orden perfecto de estos gráficos.

Si los vértices se ordenan de acuerdo con sus grados , la coloración codiciosa resultante utiliza como máximo$${\ displaystyle {\ text {max}} _ {i} {\ text {min}} \ {d (x_ {i}) + 1, i \}}colores, como máximo uno más que el grado máximo del gráfico. Esta heurística a veces se llama algoritmo galés-Powell. ^[12] Otra heurística debido a Brélaz establece el orden dinámicamente mientras el algoritmo continúa, eligiendo a continuación el vértice adyacente al mayor número de colores diferentes. ^[13] Muchas otras heurísticas de coloración de gráficos se basan de manera similar en la coloración codiciosa para una estrategia estática o dinámica específica de ordenar los vértices, estos algoritmos a veces se denominan algoritmos de coloración secuenciales .

El número máximo (peor) de colores que puede obtener el algoritmo codicioso, mediante el uso de un orden de vértices elegido para maximizar este número, se denomina número Grundy de un gráfico.

Algoritmos paralelos y distribuidos [ editar ]

En el campo de los algoritmos distribuidos , la coloración de gráficos está estrechamente relacionada con el problema de la ruptura de simetría . Los algoritmos aleatorizados de vanguardia actuales son más rápidos para un grado Δ máximo suficientemente grande que los algoritmos deterministas. Los algoritmos aleatorios más rápidos emplean la técnica de ensayos múltiples de Schneider et al. ^[14]

En un gráfico simétrico , un algoritmo determinista distribuido no puede encontrar un color de vértice adecuado. Se necesita cierta información auxiliar para romper la simetría. Una suposición estándar es que inicialmente cada nodo tiene un identificador único , por ejemplo, del conjunto {1, 2, ..., n }. Dicho de otra manera, asumimos que se nos da un n- color. El desafío es reducir el número de colores de n a, por ejemplo, Δ + 1. Cuantos más colores se empleen, por ejemplo, O (Δ) en lugar de Δ + 1, se requieren menos rondas de comunicación. ^[14]

Una versión distribuida directa del algoritmo codicioso para la coloración (Δ + 1) requiere rondas de comunicación Θ ( n ) en el peor de los casos; es posible que la información deba propagarse de un lado de la red a otro lado.

El caso más simple es un interesante n - ciclo . Richard Cole y Uzi Vishkin ^[15] muestran que existe un algoritmo distribuido que reduce el número de colores de n a O (log  n ) en un paso de comunicación síncrono. Al repetir el mismo procedimiento, es posible obtener un color 3 de un ciclo n en pasos de comunicación O ( log *  n ) (suponiendo que tengamos identificadores de nodo únicos).

La función log * , logaritmo iterado , es una función de crecimiento extremadamente lento, "casi constante". Por lo tanto, el resultado de Cole y Vishkin planteó la cuestión de si existe un algoritmo distribuido en tiempo constante para 3 colores de un ciclo n . Linial (1992) demostró que esto no es posible: cualquier algoritmo determinista distribuido requiere pasos de comunicación Ω ( log *  n ) para reducir un color n a un color 3 en un ciclo n .

La técnica de Cole y Vishkin también se puede aplicar en gráficos arbitrarios de grado acotado; el tiempo de ejecución es poli (Δ) + O ( log *  n ). ^[16] La técnica se extendió a los gráficos de unidades de disco por Schneider et al. ^[17] Los algoritmos deterministas más rápidos para la coloración (Δ + 1) para Δ pequeños se deben a Leonid Barenboim, Michael Elkin y Fabian Kuhn. ^[18] El algoritmo de Barenboim et al. se ejecuta en el tiempo O (Δ) +  log * ( n ) / 2, que es óptimo en términos de n ya que el factor constante 1/2 no puede mejorarse debido al límite inferior de Linial.Panconesi y Srinivasan (1996) usan descomposiciones de red para calcular una coloración Δ + 1 en el tiempo$${\ displaystyle 2 ^ {O \ left ({\ sqrt {\ log n}} \ right)}}.

El problema de la coloración del borde también se ha estudiado en el modelo distribuido. Panconesi y Rizzi (2001) logran una coloración (2Δ - 1) en el tiempo O (Δ +  log *  n ) en este modelo. El límite inferior para la coloración de vértices distribuidos debido a Linial (1992) se aplica también al problema de coloración de bordes distribuidos.

Algoritmos descentralizados [ editar ]

Los algoritmos descentralizados son aquellos en los que no se permite el paso de mensajes (en contraste con los algoritmos distribuidos donde tiene lugar el paso de mensajes locales), y existen algoritmos descentralizados eficientes que colorearán un gráfico si existe un color adecuado. Estos suponen que un vértice puede detectar si alguno de sus vecinos está usando el mismo color que el vértice, es decir, si existe un conflicto local. Esta es una suposición moderada en muchas aplicaciones, por ejemplo, en la asignación de canales inalámbricos, generalmente es razonable suponer que una estación podrá detectar si otros transmisores interferentes están usando el mismo canal (por ejemplo, midiendo el SINR). Esta información de detección es suficiente para permitir que los algoritmos basados ​​en autómatas de aprendizaje encuentren una coloración gráfica adecuada con probabilidad uno. ^[19]

Complejidad computacional [ editar ]

La coloración de gráficos es computacionalmente difícil. Es NP-complete decidir si un gráfico dado admite un color k para un k dado, excepto en los casos k ∈ {0,1,2}. En particular, es NP-difícil calcular el número cromático. ^[20] El problema de 3 colores sigue siendo NP completo incluso en gráficos planos 4 regulares . ^[21] Sin embargo, para cada k > 3, existe una coloración k de un gráfico plano por el teorema de los cuatro colores , y es posible encontrar dicha coloración en el tiempo polinómico.

El algoritmo de aproximación más conocido calcula una coloración de tamaño como máximo dentro de un factor O ( n (log log  n ) ² (log n) ⁻³ ) del número cromático. ^[22] Para todos ε  > 0, aproximar el número cromático dentro de n ^1− ε es NP-duro . ^[23]

También es NP-difícil colorear un gráfico de 3 colores con 4 colores ^[24] y un gráfico k- colorable con k ^{(log k  ) / 25} colores para una constante k suficientemente grande . ^[25]

Calcular los coeficientes del polinomio cromático es # P-duro . De hecho, incluso calcular el valor de$${\ displaystyle \ chi (G, k)}es # P-hard en cualquier punto racional k excepto para k  = 1 yk  = 2. ^[26] No hay FPRAS para evaluar el polinomio cromático en ningún punto racional k  ≥ 1.5 excepto para k  = 2 a menos que NP  =  RP . ^[27]

Para la coloración de bordes, la prueba del resultado de Vizing proporciona un algoritmo que utiliza como máximo colores Δ + 1. Sin embargo, decidir entre los dos valores candidatos para el número cromático de borde es NP-completo. ^[28] En términos de algoritmos de aproximación, el algoritmo de Vizing muestra que el número cromático de borde puede aproximarse a 4/3, y el resultado de la dureza muestra que no  existe ningún algoritmo (4/3 -  ε ) para cualquier ε> 0 a menos que P = NP . Estos son algunos de los resultados más antiguos en la literatura de algoritmos de aproximación, a pesar de que ninguno de los documentos hace un uso explícito de esa noción.