Algoritmo de color vertex

El algoritmo de color Vertex



Ashay Dharwadker



Instituto de Matemáticas

H-501 Palam Vihar

Distrito de Gurgaon

Haryana 122017

India



ashay@dharwadker.org~~V







Resumen



Presentamos un nuevo tiempo polinómico algoritmo para encontrar adecuadas m-colorantes de los vértices de una gráfica. Nos probar que todo grafo con n vértices y máximo vértice grado Δ debe tener χ númerocromático (G) menos que o igual a Δ +1 y que el algoritmo siempre encontrará un adecuado m-coloración de los vértices de G con m menos de o igual a Δ +1. Por otra parte, se demuestra que esta condición es la mejor posible en términos de n y Δ de manera explícita la construcción de gráficos para los que el número cromático es exactamente Δ 1. En el caso especial cuando G es un grafo simple conectado y no esni un ciclo extraño, ni un gráfico completo, nos muestran que el algoritmo siempre encontrará un buen m-coloración de los vértices de G con m menor o igual a Δ. En el proceso, se obtiene una nueva prueba constructiva de famoso teorema de Brooks de 1941. Para todos los ejemplos conocidos de gráficos, el algoritmo encuentra un adecuado m-coloración de los vértices del grafo G para igual a la χnúmero cromático (G) m. En vista de la importancia de la cuestión P versus NP, nos preguntamos: ¿existe un grafo G que este algoritmo no puede encontrar un buen m-coloración de los vértices de G, con igual al número cromático χ (G) m? El algoritmo se demuestra con varios ejemplos de gráficos de famosos, entre ellos un buen cuatro colores del mapa de la India y dos grandes gráficos de referencia conMycielski ocultos mínimos colorantes vértice. Ponemos en práctica el algoritmo en C + + y proporcionar un programa de demostración para Microsoft Windows [Descarga] .



Agradecimientos



Gracias a Klaus D. Witzel para sugerir los gráficos Mycielski de los ejemplos 7.19 y 7.20 que sirven como los principales puntos de referencia para comprobar si realmente este algoritmo encuentra un coloreado devértices como mínimo en los casos más difíciles conocidos. Este algoritmo también ha sido citado en Aplicaciones de la Teoría de Grafos publicados por la Sociedad Coreana para la Matemática Industrial y Aplicada. Nos complace anunciar que el algoritmo de color Vertex ha sido publicada por Amazon en 2011.







1. Introducción



En 1972, Karp [1] presentó una lista de veintiún NP-completosproblemas, uno de los cuales era el problema de tratar de encontrar un adecuado m-color de los vértices de un grafo, donde m es un entero fijo superior a 2 . Dado un grafo y un conjunto de colores m, uno debe averiguar si es posible asignar un color a cada vértice tal que no hay dos vértices adyacentes se les asigna el mismo color. Tal asignación se llama un buen m-color de los vértices de un grafo.Incluso si tal una coloración existe, que puede ser muy difícil de encontrar en general. Por ejemplo, tratar de encontrar una adecuada 3-coloración de los vértices de la gráfica Frucht [2] se muestra en la Figura 1.1.





Figura 1.1. Encontrar un buen 3-coloración de los vértices

Presentamos un nuevo tiempo polinómico algoritmo de color VERTEX adecuados para encontrar m-colorantes de los vértices deuna gráfica. En la sección 2, ofrecemos precisas DEFINICIONES de toda la terminología utilizada. En la sección 3, presentamos una descripción formal de la ALGORITMO seguido por un pequeño ejemplo para mostrar cómo funciona el algoritmo paso a paso. En la sección 4, se muestra que el algoritmo tiene tiempo polinómico COMPLEJIDAD . En la Sección 5, se establecen las condiciones de Suficiencia de ungráfico para tener un buen m-colorante. Nos probar que todo grafo con n vértices y máximo vértice grado Δ debe tener χ número cromático (G) menos que o igual a Δ +1 y que el algoritmo siempre encontrará un adecuado m-coloración de los vértices de G con m menos de o igual a Δ +1. Por otra parte, se demuestra que esta condición es la mejor posible en términos de n y Δ de manera explícita la...