LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

  (Redirigido desde el algoritmo de coloración )

Saltar a navegaciónSaltar a búsqueda

No debe confundirse con la coloración del borde .

Un color de vértice adecuado de la gráfica de Petersen con 3 colores, el número mínimo posible.

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

La coloración de vértices es el punto de partida de la coloración gráfica. Otros problemas de coloración pueden transformarse en una versión de vértice. Por ejemplo, una coloración de borde de un gráfico es solo una coloración de vértice de su gráfico de líneas , y una coloración de cara de un gráfico de plano es solo una coloración de vértice de su doble . Sin embargo, los problemas de coloración que no son vértices a menudo se establecen y se estudian tal como están . Eso es en parte para la perspectiva, y en parte porque algunos problemas se estudian mejor en forma no vértice, como por ejemplo 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 convirtió en colorear los vértices, y en esta forma se generaliza a todos los gráficos. En las representaciones matemáticas e informáticas, es típico usar los primeros números enteros positivos o no negativos como "colores". En general, se puede usar cualquier conjunto finito como el "conjunto de colores". La naturaleza del problema de la coloración depende de la cantidad de colores, pero no de lo que son.

La coloración de gráficos disfruta de muchas aplicaciones prácticas, así como de 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 número Sudoku . La coloración de grafos es todavía 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 Guthriepostuló 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 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 Society.en 1879. El mismo año, Alfred Kempe publicó un documento que pretendía establecer el resultado, y durante una década el problema de los cuatro colores se consideró resuelto. 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 artículo probó el teorema de los cinco colores , diciendo que cada mapa plano puede ser coloreado con no más de cincocolores, utilizando ideas de Kempe. En el siglo siguiente, se desarrolló una gran cantidad de trabajos y teorías para reducir el número de colores a cuatro, hasta que el teorema de los cuatro colores fue finalmente probado en 1976 por Kenneth Appel y Wolfgang Haken . La prueba se remonta a las ideas de Heawood y Kempe y descuidó en gran medida los desarrollos intermedios. ^[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 fue generalizado al polinomio de Tutte por Tutte , importantes estructuras 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 de los resultados de las generalizaciones de la coloración de los gráficos planos a superficies de orden superior se produjeron a principios del siglo XX.

En 1960, Claude Berge formuló otra conjetura acerca de la coloración de gráficos, la fuerte y perfecta conjetura de gráficos , originalmente motivada por un concepto de teoría de la información llamado capacidad de error cerode un gráfico introducido por Shannon . La conjetura permaneció sin resolver durante 40 años, hasta que fue establecida como el famoso teorema de grafos perfectos por Chudnovsky , Robertson , Seymour y Thomas en 2002.

La coloración de los 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 desde 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 ]

Esta gráfica puede ser de 3 colores en 12 formas diferentes.

Coloración vértice [ editar ]

Cuando se usa sin ninguna calificación, la coloración de una gráfica es casi siempre una coloración de vértice adecuada , es decir, una etiqueta de los vértices de la gráfica con colores tales que no hay dos vértices que compartan el mismo borde y tengan el mismo color. Dado que un vértice con un bucle (es decir, una conexión directamente a sí mismo) nunca se puede colorear correctamente, se entiende que los gráficos en este contexto no tienen bucles.

La terminología de usar colores para las etiquetas de vértices se remonta al coloreado 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 dibujan a partir de los números 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 denomina su número cromático , y a menudo se denota como χ ( G ). Algunas veces se usa γ ( G ), ya que χ ( G ) también se usa para denotar la característicade Euler de una gráfica. Una gráfica a la que se le puede asignar un color k (apropiado) es k -colorable , y k-cromática si su número cromático es exactamente k . Un subconjunto de vértices asignados al mismo color se denomina clase de color. , cada clase tal 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.

Cromática polinomio [ editar ]

Todos los gráficos no isomorfos en 3 vértices y sus polinomios cromáticos. El gráfico vacío E ₃(rojo) admite un colorante 1, los otros no admiten dichos colorantes. El gráfico verde admite 12 coloraciones 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 puede colorearse de 12 formas. Con solo dos colores, no puede ser coloreado en absoluto. Con cuatro colores, se puede colorear en 24 + 4⋅12 = 72 formas: usando los cuatro colores, ¡hay 4! = 24 coloraciones válidas ( cadaasignación de cuatro colores a cualquier gráfico de 4 vértices es una coloración adecuada); y para cada elección de tres de los cuatro colores, hay 12 colores válidos de 3 colores. Entonces, para la gráfica en el ejemplo, una tabla de la cantidad de colorantes válidos comenzaría así:

Colores disponibles	1	2	3	4	...
Número de colorantes	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 lo 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)}
Completa la gráfica 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 del borde [ editar ]

Artículo principal: Coloración de bordes.

Una coloración de borde de un gráfico es una coloración adecuada 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 bordes con k colores se denomina coloración con borde k 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 bordes de un gráfico G es el índice cromático , o número cromático de bordes , χ ′ ( 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 todos los gráficos cúbicos sin puentes cúbicos planos admiten 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 asume que una coloración total es adecuada en el sentido de que no se asigna el mismo color a ningún vértice adyacente, sin bordes adyacentes y sin borde y sus vértices finales. 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.

Colorear sin etiqueta [ editar ]

Un colorante sin etiqueta de un gráfico es una órbita de un colorante bajo la acción del grupo de automorfismodel gráfico. Si interpretamos una coloración de una gráfica 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 marcados de una gráfica de un conjunto de colores finitos dado.

Propiedades [ editar ]

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

La asignación de 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 los 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 m bordes 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 la 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 dos colores son exactamente los gráficos bipartitos , incluidos los árboles y los bosques. Por el teorema de los cuatro colores, cada gráfica plana puede ser de 4 colores.

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

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

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 lo mejor posible. En todos los demás casos, el límite puede ser ligeramente mejorado; El teorema de Brooks ^[4] establece que

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

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

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

Hoffman obligado: 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. Entonces:

$${\ 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)} para ser el menos k para el que tal matriz $${\ displaystyle W}existe Entonces

$${\ 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 fraccional : el número cromático fraccional de un gráfico también es 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 alto número cromático, pero lo contrario no es cierto. El gráfico de Grötzsch es un ejemplo de un gráfico de 4 cromos sin un triángulo, y el ejemplo se puede generalizar a los micielskianos .

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

Del teorema de Brooks, los gráficos con 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 alta circunferencia parece localmente 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 de líneas $${\ displaystyle L (G)}, y viceversa. Así,

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

Existe una fuerte relación entre la colorabilidad del borde y el grado máximo del gráfico. $${\ displaystyle \ Delta (G)}. Dado que todos los bordes que inciden en 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 incluso 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 un número cromático $${\ displaystyle \ Delta} o $${\ displaystyle \ Delta +1}.

Otras propiedades [ editar ]

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

Para las gráficas planas, los colorantes de vértices son esencialmente duales a los flujos de cero en ninguna parte .

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

• Si todos los subgrafos finitos de un grafo 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ős de de Bruijn & Erdős (1951) .
• Si una gráfica admite un color n completo para cada n ≥ n ₀ , admite una coloración infinita completa ( 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 .}$

El número cromático del plano , donde dos puntos son adyacentes si tienen una unidad de distancia, es desconocido, 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 todos los gráficos con el número cromático k tiene un gráfico completo en k vértices como un menor , la conjetura de Erdős-Faber-Lovász que delimita 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 -los gráficos cromáticos los gráficos completos son los que tienen los más pequeñosnúmero de cruce .

Cuando Birkhoff y Lewis introdujeron el polinomio cromático en su ataque al teorema de los cuatro colores, conjeturaron que para los gráficos planares G , el polinomio$${\ displaystyle P (G, t)} no tiene ceros en la region $${\ displaystyle [4, \ infty)}. Aunque se sabe que tal 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	Coloración gráfica, coloración de vértice, k-coloración.
Entrada	Gráfica G con n vértices.Entero k
Salida	¿ Admite G una coloración de vértice adecuada con kcolores?
Tiempo de ejecución	O (2 n n ) [6]
Complejidad	NP-completo
Reducción de	3-Satisfiabilidad
Garey – Johnson	GT4
Mejoramiento
Nombre	Número cromático
Entrada	Gráfica G con n vértices.
Salida	χ ( G )
Complejidad	NP-duro
Aproximabilidad	O ( n  (log n ) −3 (log log n )2 )
Inoproximabilidad	O ( n 1 − ε ) a menos que P = NP
Problema de conteo
Nombre	Polinomio cromático
Entrada	Gráfica G con n vértices.Entero k
Salida	El número P  ( G , k ) decoloraciones k adecuadas de G
Tiempo de ejecución	O (2 n n )
Complejidad	# P-completo
Aproximabilidad	FPRAS para casos restringidos
Inoproximabilidad	Sin PTAS a menos que P = NP

Tiempo polinomial [ editar ]

Determinar si una gráfica se puede colorear con 2 colores es equivalente a determinar si la gráfica es bipartita y, por lo tanto, computable en tiempo lineal utilizando la búsqueda en la primera amplitud o la búsqueda en la primera profundidad . Más generalmente, el número cromático y una coloración correspondiente de gráficos perfectos se pueden calcular en tiempo polinomial usando programación semidefinida . Se conocen fórmulas cerradas para polinomios cromáticos para muchas clases de gráficos, como bosques, gráficos de cuerdas, ciclos, ruedas y escalas, por lo que se pueden evaluar en tiempo polinomial.

Si la gráfica es plana y tiene un ancho de rama bajo (o no es plana pero tiene una descomposición de rama conocida), entonces se puede resolver en tiempo polinomial utilizando la programación dinámica. En general, el tiempo requerido es polinomial 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 color k considera cada uno de los$${\ displaystyle k ^ {n}}Asignaciones de k colores a n vértices y verifica 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, excepto los gráficos de entrada 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 color 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 transformada zeta rápida, la capacidad de color k se puede decidir a tiempo$${\ displaystyle O (2 ^ {n} n)}^[6] para cualquier k . Se conocen algoritmos más rápidos para la coloración 3 y 4, que se puede decidir a tiempo$${\ displaystyle O (1.3289 ^ {n})}^[8] y$${\ displaystyle O (1.7272 ^ {n})}, ^[9] respectivamente.

Contracción [ editar ]

La contracción $${\ displaystyle G / uv}de una gráfica G es la gráfica obtenida al identificar los vértices u y v , y eliminar cualquier borde entre ellos. Los bordes restantes originalmente incidentes en u o v ahora inciden en 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 la gráfica con el borde uv añadido. Varios algoritmos se basan en la evaluación de esta recurrencia y el árbol de cálculo resultante a veces se denomina árbol 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 la gráfica con el borde uv eliminado.$${\ displaystyle P (G-uv, k)}representa el número de posibles coloraciones adecuadas de la gráfica, donde los vértices pueden tener los mismos colores o diferentes. Entonces los colores adecuados surgen de dos gráficos diferentes. Para explicar, si los vértices u y v tienen colores diferentes, entonces podríamos considerar un gráfico donde u y v son adyacentes. Si u y vtienen los mismos colores, también podríamos considerar un gráfico en el que 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 en el tiempo dentro de un factor polinomial de$${\ displaystyle \ left ({\ tfrac {1 + {\ sqrt {5}}} {2}} \ right) ^ {n + m} = O (1.6180 ^ {n + m})}Para n vértices y maristas. ^[10] El análisis se puede mejorar dentro de un factor polinomial del número$${\ displaystyle t (G)}de árboles de expansiónde la gráfica de entrada. ^[11] En la práctica, las estrategias de ramificación y límite y el rechazo del isomorfismo gráfico se utilizan para evitar algunas llamadas recursivas. El tiempo de ejecución depende de la heurística utilizada para elegir el par de vértices.

Colorear codiciosos [ editar ]

Artículo principal: Coloración codiciosa.

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

El codicioso algoritmo 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}}, añadiendo un color fresco si es necesario. La calidad de la coloración resultante depende del orden elegido. Existe un orden que lleva a una coloración codiciosa con el número óptimo de$${\ displaystyle \ chi (G)}colores. Por otro lado, los colorantes 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 lleva a una coloración codiciosa con$${\ displaystyle n / 2} colores.

Para gráficos de cuerdas , y para casos especiales de gráficos de cuerdas como el grafo de intervalos y gráficos de indiferencia , el algoritmo del colorante de codiciosos puede ser usado para encontrar colorantes óptimas en tiempo polinómico, eligiendo el orden vértice a ser el reverso de una ordenación perfecta eliminación de la grafico. Los gráficos perfectamente ordenablesgeneralizan esta propiedad, pero es 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 se utiliza como máximo$${\ displaystyle {\ text {max}} _ {i} {\ text {min}} \ {d (x_ {i}) + 1, i \}}Colores, a lo sumo uno más que el grado máximo del gráfico. Esta heurística a veces se llama el algoritmo de Welsh-Powell. ^[12] Otra heurística debida a Brélaz establece el ordenamiento dinámicamente mientras el algoritmo avanza, eligiendo el siguiente 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 colorantes codiciosos para una estrategia estática o dinámica específica de ordenar los vértices, estos algoritmos a veces se denominan algoritmos de coloreado secuencial .

El número máximo (el peor) de colores que puede obtenerse mediante el algoritmo codicioso, al usar un orden de vértice elegido para maximizar este número, se denomina el número de Grundy de una gráfica.

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 la simetría . Los algoritmos aleatorios de vanguardia actuales son más rápidos para un grado máximo suficientemente grande large que los algoritmos determinísticos. Los algoritmos aleatorios más rápidos emplean la técnica de múltiples ensayos de Schneider et al. ^[14]

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

Una versión distribuida directa del algoritmo codicioso para el color (1 + 1) requiere r ( n ) rondas de comunicación en el peor de los casos: es posible que la información deba propagarse de un lado de la red al otro.

El caso más simple e interesante es un n - ciclo . Richard Cole y Uzi Vishkin ^[15] muestran que hay un algoritmo distribuido que reduce el número de colores de n a O (log  n ) en un paso de comunicación sincrónica. Al repetir el mismo procedimiento, es posible obtener un colorante 3 de una n- cycle en los pasos de comunicación O ( log *  n ) (suponiendo que tenemos identificadores de nodo únicos).

La función log * , logaritmo iterado , es una función que crece muy lentamente, "casi constante". Por lo tanto, el resultado de Cole y Vishkin planteó la cuestión de si existe un algoritmo distribuido de tiempo constante para colorear en tres una n . Linial (1992) demostró que esto no es posible: cualquier algoritmo distribuido determinista requiere communication ( log *  n ) pasos de comunicación para reducir la n -coloración a 3 colores en una n-cycle.

La técnica de Cole y Vishkin también se puede aplicar en gráficos de grados limitados arbitrarios; el tiempo de ejecución es poli (Δ) + O ( log *  n ). ^[16] La técnica se extendió a los gráficos de unidad de disco de Schneider et al. ^[17] Los algoritmos deterministas más rápidos para ((+ 1) -coloring para small Δ se deben a Leonid Barenboim, Michael Elkin y Fabian Kuhn. ^[18] El algoritmo de Barenboim et al. corre 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) utilizan descomposiciones de red para calcular una coloración de Δ + 1 en el tiempo$${\ displaystyle 2 ^ {O \ left ({\ sqrt {\ log n}} \ right)}}.

El problema de la coloración de bordes también se ha estudiado en el modelo distribuido. Panconesi y Rizzi (2001) logran una coloración (2Δ - 1) en O ( log  +  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 la 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 una gráfica si existe una coloración adecuada. Estos suponen que un vértice es capaz de 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 suave 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 utilizando el mismo canal (por ejemplo, midiendo la SINR). Esta información de detección es suficiente para permitir que los algoritmos basados ​​en el aprendizaje de autómatas encuentren un color de gráfico adecuado con probabilidad uno. ^[19]

Complejidad computacional [ editar ]

La coloración de los gráficos es computacionalmente difícil. Es NP-completo para 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 los 3 colores sigue siendo NP-completo incluso en gráficos planos de 4 regulares . ^[21] Sin embargo, para cada k > 3, existe un k coloreado de un gráfico planar según el teorema de los cuatro colores , y es posible encontrar dicho colorante en el tiempo polinomial.

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 toda ε  > 0, la aproximación del número cromático dentro de n ^1− ε es NP-dura . ^[23]

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

El cálculo de los coeficientes del polinomio cromático es # P-duro . De hecho, incluso calcular el valor de$${\ displaystyle \ chi (G, k)}es # P-duro en cualquier punto racional k excepto para k  = 1 y k  = 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]