El polinomio cromático es un polinomio de grafos estudiado en la teoría de grafos algebraicos , una rama de las matemáticas . Cuenta el número de coloraciones gráficas en función del número de colores y fue originalmente definido por George David Birkhoff para estudiar el problema de los cuatro colores . Hassler Whitney y WT Tutte lo generalizaron al polinomio de Tutte , vinculándolo al modelo de Potts de física estadística .
Historia
George David Birkhoff introdujo el polinomio cromático en 1912, definiéndolo solo para gráficos planos , en un intento de demostrar el teorema de los cuatro colores . Sidenota el número de coloraciones adecuadas de G con k colores, entonces se podría establecer el teorema de los cuatro colores mostrandopara todos planar gráficos de G . De esta manera esperaba aplicar las poderosas herramientas de análisis y álgebra para estudiar las raíces de polinomios al problema de coloración combinatoria.
Hassler Whitney generalizó el polinomio de Birkhoff del caso plano a gráficos generales en 1932. En 1968, Ronald C. Read preguntó qué polinomios son los polinomios cromáticos de algún gráfico, una pregunta que permanece abierta, e introdujo el concepto de gráficos cromáticamente equivalentes. [1] Hoy en día, los polinomios cromáticos son uno de los objetos centrales de la teoría de grafos algebraicos . [2]
Definición
Para un gráfico G ,cuenta el número de sus (apropiados) vértices k -colorings . Otras notaciones de uso común incluyen, , o . Hay un polinomio único que evaluado en cualquier entero k ≥ 0 coincide con; se llama el polinomio cromático de G .
Por ejemplo, para colorear el gráfico de ruta en 3 vértices con k colores, se puede elegir cualquiera de los k colores para el primer vértice, cualquiera de los colores restantes para el segundo vértice, y por último para el tercer vértice, cualquiera de los colores que son diferentes de la elección del segundo vértice. Por lo tanto,es el número de k- coloraciones de. Para una variable x (no necesariamente un número entero), tenemos. (Los colorantes que difieren solo por permutar colores o por automorfismos de G todavía se cuentan como diferentes).
Deleción-contracción
El hecho de que el número de k- coloraciones sea un polinomio en k se deriva de una relación de recurrencia llamada recurrencia de deleción-contracción o Teorema de reducción fundamental . [3] Se basa en la contracción del borde : para un par de vértices y la gráfica se obtiene fusionando los dos vértices y eliminando los bordes entre ellos. Si y son adyacentes en G , sea denotar el gráfico obtenido al eliminar el borde . Entonces el número de k colores de estos gráficos satisface:
De manera equivalente, si y no son adyacentes en G y es el gráfico con el borde agregado, entonces
Esto se sigue de la observación de que cada k- coloración de G da diferentes colores a y , o los mismos colores. En el primer caso, esto da una coloración k (adecuada) de, mientras que en el segundo caso da una coloración de . Por el contrario, cada k- coloración de G se puede obtener de forma única a partir de una k- coloración de o (Si y no son adyacentes en G ).
Por tanto, el polinomio cromático puede definirse de forma recursiva como
- para el gráfico sin aristas en n vértices, y
- para un gráfico G con una arista (elegido arbitrariamente).
Dado que el número de k- colores del gráfico sin bordes es de hecho, se sigue por inducción sobre el número de aristas que para todo G , el polinomiocoincide con el número de k colores en cada punto entero x = k . En particular, el polinomio cromático es el polinomio de interpolación único de grado como máximo n a través de los puntos
La curiosidad de Tutte acerca de qué otros invariantes gráficos satisfacían tales recurrencias lo llevó a descubrir una generalización bivariada del polinomio cromático, el polinomio de Tutte. .
Ejemplos de
Triángulo | |
Gráfico completo | |
Gráfico sin bordes | |
Gráfico de ruta | |
Cualquier árbol en n vértices | |
Ciclo | |
Gráfico de Petersen |
Propiedades
Para G fijo en n vértices, el polinomio cromáticoes un mónico polinomio de grado exactamente n , con coeficientes enteros.
El polinomio cromático incluye al menos tanta información sobre la colorabilidad de G como el número cromático. De hecho, el número cromático es el entero positivo más pequeño que no es cero del polinomio cromático,
El polinomio evaluado en , es decir , rinde veces el número de orientaciones acíclicos de G . [4]
La derivada evaluada en 1, es igual al invariante cromático hasta firmar.
Si G tiene n vértices yc componentes , luego
- Los coeficientes de son ceros.
- Los coeficientes de son todos distintos de cero y de signos alternos.
- El coeficiente de es 1 (el polinomio es monico ).
- El coeficiente de es .
Demostramos esto mediante inducción en el número de aristas en un gráfico simple G con vértices y bordes. Cuándo, G es un gráfico vacío. Por lo tanto, por definición. Entonces el coeficiente de es , lo que implica que la afirmación es verdadera para un gráfico vacío. Cuándo, como en G tiene un solo borde,. Así coeficiente de es . Entonces, el enunciado se cumple para k = 1. Usando una inducción fuerte, suponga que el enunciado es verdadero para. Deja que G tengabordes. Por el principio de contracción-supresión ,
,
Dejar , y .
Por eso.
Desdese obtiene de G mediante la eliminación de un solo borde e ,, entonces y, por tanto, el enunciado es verdadero para k .
- El coeficiente de es multiplicado por el número de orientaciones acíclicas que tienen un sumidero único, en un vértice específico elegido arbitrariamente. [5]
- Los valores absolutos de los coeficientes de cada polinomio cromático forman una secuencia log-cóncava . [6]
La última propiedad se generaliza por el hecho de que si G es una k -clique-suma de y (es decir, un gráfico obtenido pegando los dos en un clique en k vértices), luego
Un gráfico G con n vértices es un árbol si y solo si
Equivalencia cromática
Se dice que dos gráficos son cromáticamente equivalentes si tienen el mismo polinomio cromático. Los gráficos isomórficos tienen el mismo polinomio cromático, pero los gráficos no isomórficos pueden ser cromáticamente equivalentes. Por ejemplo, todos los árboles en n vértices tienen el mismo polinomio cromático. En particular,es el polinomio cromático tanto del gráfico de garra como del gráfico de trayectoria en 4 vértices.
Un gráfico es cromáticamente único si está determinado por su polinomio cromático, hasta el isomorfismo. En otras palabras, G es cromáticamente único, entoncesimplicaría que G y H son isomorfos. Todos los gráficos de ciclo son cromáticamente únicos. [7]
Raíces cromáticas
Una raíz (o cero ) de un polinomio cromático, llamada "raíz cromática", es un valor x donde. Las raíces cromáticas han sido muy bien estudiadas, de hecho, la motivación original de Birkhoff para definir el polinomio cromático fue mostrar que para gráficos planos,para x ≥ 4. Esto habría establecido el teorema de los cuatro colores .
Ningún gráfico puede ser de color 0, por lo que 0 es siempre una raíz cromática. Solo los gráficos sin bordes pueden ser de 1 color, por lo que 1 es una raíz cromática de cada gráfico con al menos un borde. Por otro lado, a excepción de estos dos puntos, ningún gráfico puede tener una raíz cromática en un número real menor o igual a 32/27. [8] Un resultado de Tutte conecta la proporción áurea con el estudio de las raíces cromáticas, mostrando que las raíces cromáticas existen muy cerca de : Si es una triangulación plana de una esfera, entonces
Si bien la línea real tiene partes grandes que no contienen raíces cromáticas para ningún gráfico, cada punto en el plano complejo está arbitrariamente cerca de una raíz cromática en el sentido de que existe una familia infinita de gráficos cuyas raíces cromáticas son densas en el plano complejo. . [9]
Colorantes usando todos los colores.
Para un gráfico G en n vértices, seadenotar el número de colorantes usando exactamente k colores hasta cambiar el nombre de los colores (por lo que los colorantes que se pueden obtener entre sí permutando colores se cuentan como uno; los colorantes obtenidos por automorfismos de G aún se cuentan por separado). En otras palabras,cuenta el número de particiones del conjunto de vértices en k conjuntos independientes (no vacíos) . Luegocuenta el número de colorantes utilizando exactamente k colores (con colores distinguibles). Para un número entero x , todos los colores x de G pueden obtenerse de forma única eligiendo un número entero k ≤ x , eligiendo k colores que se usarán de entre los x disponibles, y un colorante que use exactamente esos k colores (distinguibles). Por lo tanto:
- ,
dónde denota el factorial descendente . Así los números son los coeficientes del polinomio en la base de la caída de factoriales.
Dejar ser el k -ésimo coeficiente de en la base estándar , es decir:
Los números de Stirling dan un cambio de base entre la base estándar y la base de factoriales descendentes. Esto implica:
- y .
Categorización
El polinomio cromático está categorizado por una teoría de homología estrechamente relacionada con la homología de Khovanov . [10]
Algoritmos
Polinomio cromático | |
---|---|
Aporte | Grafica G con n vértices. |
Producción | Coeficientes de |
Tiempo de ejecución | por alguna constante |
Complejidad | #P -duro |
Reducción de | # 3SAT |
# k-colorantes | |
---|---|
Aporte | Grafica G con n vértices. |
Producción | |
Tiempo de ejecución | En P para. por . De lo contrario por alguna constante |
Complejidad | #P -duro a menos que |
Aproximabilidad | Sin FPRAS para |
Los problemas computacionales asociados con el polinomio cromático incluyen
- encontrar el polinomio cromático de un gráfico G dado ;
- evaluando en un punto fijo x para G dado .
El primer problema es más general porque si supiéramos los coeficientes de podríamos evaluarlo en cualquier punto del tiempo polinomial porque el grado es n . La dificultad del segundo tipo de problema depende en gran medida del valor de x y se ha estudiado intensamente en complejidad computacional . Cuando x es un número natural, este problema normalmente se ve como el cálculo del número de colores x de una gráfica dada. Por ejemplo, esto incluye el problema # 3: colorear de contar el número de 3 colores, un problema canónico en el estudio de la complejidad del conteo, completo para la clase de conteo #P .
Algoritmos eficientes
Para algunas clases de gráficos básicos, se conocen fórmulas cerradas para el polinomio cromático. Por ejemplo, esto es cierto para los árboles y las camarillas, como se enumera en la tabla anterior.
Los algoritmos de tiempo polinómico son conocidos por calcular el polinomio cromático para clases más amplias de gráficos, incluidos los gráficos cordales [11] y los gráficos de ancho de camarilla acotado . [12] La última clase incluye cografías y gráficos de ancho de árbol delimitado , como los gráficos del plano exterior .
Deleción-contracción
La recurrencia de deleción-contracción proporciona una forma de calcular el polinomio cromático, llamado algoritmo de deleción-contracción . En la primera forma (con un signo menos), la recurrencia termina en una colección de gráficos vacíos. En la segunda forma (con un signo más), termina en una colección de gráficos completos. Esto forma la base de muchos algoritmos para colorear gráficos. La función ChromaticPolynomial en el paquete Combinatorica del sistema de álgebra computacional Mathematica usa la segunda recurrencia si la gráfica es densa, y la primera recurrencia si la gráfica es escasa. [13] El peor tiempo de ejecución de cualquiera de las fórmulas 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
en un gráfico con n vértices y m aristas. [14] El análisis se puede mejorar dentro de un factor polinomial del númerode árboles de expansión del gráfico de entrada. [15] En la práctica, se emplean estrategias de ramificación y límite y rechazo de isomorfismos de grafos para evitar algunas llamadas recursivas; el tiempo de ejecución depende de la heurística utilizada para elegir el par de vértices.
Método del cubo
Existe una perspectiva geométrica natural sobre los colores de los gráficos al observar que, como una asignación de números naturales a cada vértice, el color de un gráfico es un vector en el entramado de números enteros. Dado que dos vértices y recibir el mismo color es equivalente a la 'th y Siendo igual la coordenada en el vector de coloración, cada borde se puede asociar con un hiperplano de la forma . La colección de tales hiperplanos para un gráfico dado se denomina disposición gráfica . Los colores adecuados de un gráfico son los puntos de celosía que evitan los hiperplanos prohibidos. Restringiendo a un conjunto de colores, los puntos de celosía están contenidos en el cubo . En este contexto, el polinomio cromático cuenta el número de puntos de la red en el-cubo que evita la disposición gráfica.
Complejidad computacional
El problema de calcular el número de 3 colores de un gráfico dado es un ejemplo canónico de un problema #P -completo, por lo que el problema de calcular los coeficientes del polinomio cromático es # P-difícil. Del mismo modo, evaluardado que G es # P-completo. Por otro lado, para es fácil de calcular , por lo que los problemas correspondientes son calculables en tiempo polinómico. Para enteros el problema es # P-hard, que se establece de manera similar al caso . De hecho, se sabe quees # P-difícil para todo x (incluidos los números enteros negativos e incluso todos los números complejos) excepto para los tres "puntos fáciles". [16] Por lo tanto, desde la perspectiva de la dureza # P, se comprende completamente la complejidad de calcular el polinomio cromático.
En la expansión
el coeficiente es siempre igual a 1, y se conocen varias otras propiedades de los coeficientes. Esto plantea la cuestión de si algunos de los coeficientes son fáciles de calcular. Sin embargo, el problema computacional de calcular a r para una r fija ≥ 1 y una gráfica dada G es # P-difícil, incluso para gráficas planas bipartitas. [17]
Sin algoritmos de aproximación para la computaciónse conocen por cualquier x excepto por los tres puntos fáciles. En los puntos enteros, el problema de decisión correspondiente de decidir si una gráfica dada puede ser de color k es NP-difícil . Tales problemas no se pueden aproximar a ningún factor multiplicativo mediante un algoritmo probabilístico de error acotado a menos que NP = RP, porque cualquier aproximación multiplicativa distinguiría los valores 0 y 1, resolviendo efectivamente la versión de decisión en tiempo polinomial probabilístico de error acotado. En particular, bajo el mismo supuesto, esto descarta la posibilidad de un esquema de aproximación aleatoria en tiempo completamente polinomial (FPRAS) . Para otros puntos, se necesitan argumentos más complicados, y la pregunta es el foco de una investigación activa. A partir de 2008[actualizar], se sabe que no existe un FPRAS para computarpara cualquier x > 2, a menos que se cumpla NP = RP . [18]
Notas
- ^ Leer (1968)
- ^ Varios capítulos Biggs (1993)
- ^ Dong, Koh y Teo (2005)
- ↑ Stanley (1973)
- ^ Ellis-Monaghan y Merino (2011)
- ↑ Huh (2012)
- ^ Chao y Whitehead (1978)
- ↑ Jackson (1993)
- ^ Sokal (2004)
- ^ Helme-Guizon y Rong (2005)
- ^ Naor, Naor y Schaffer (1987) .
- ^ Giménez, Hliněný y Noy (2005) ; Makowsky y col. (2006) .
- ^ Pemmaraju y Skiena (2003)
- ↑ Wilf (1986)
- ^ Sekine, Imai y Tani (1995)
- ^ Jaeger, Vertigan & Welsh (1990) , basado en una reducción en ( Linial 1986 ).
- ^ Oxley y Welsh (2002)
- ^ Goldberg y Jerrum (2008)
Referencias
- Biggs, N. (1993), Teoría de grafos algebraicos , Cambridge University Press, ISBN 978-0-521-45897-9
- Chao, C.-Y .; Whitehead, EG (1978), "Sobre la equivalencia cromática de los gráficos", Teoría y aplicaciones de los gráficos , Lecture Notes in Mathematics, 642 , Springer, pp. 121-131, ISBN 978-3-540-08666-6
- Dong, FM; Koh, KM; Teo, KL (2005), Polinomios cromáticos y cromaticidad de gráficos , World Scientific Publishing Company, ISBN 978-981-256-317-0
- Giménez, O .; Hliněný, P .; Noy, M. (2005), "Calcular el polinomio de Tutte en gráficos de ancho de camarilla acotado", Proc. 31a Int. Worksh. Conceptos teóricos de gráficos en informática (WG 2005) , Lecture Notes in Computer Science, 3787 , Springer-Verlag, págs. 59–68, CiteSeerX 10.1.1.353.6385 , doi : 10.1007 / 11604686_6 , ISBN 978-3-540-31000-6
- Goldberg, LA ; Jerrum, M. (2008), "Inapproximability of the Tutte polynomial", Information and Computation , 206 (7): 908, arXiv : cs / 0605140 , doi : 10.1016 / j.ic.2008.04.003
- Helme-Guizon, Laure; Rong, Yongwu (2005), "Una categorización del polinomio cromático", Topología algebraica y geométrica , 5 (4): 1365-1388, arXiv : math / 0412264 , doi : 10.2140 / agt.2005.5.1365
- Huh, J. (2012), "Números de Milnor de hipersuperficies proyectivas y el polinomio cromático de gráficos", arXiv : 1008.4749v3 [ math.AG ]
- Jackson, B. (1993), "A Zero-Free Interval for Chromatic Polinomials of Graphs", Combinatoria, Probabilidad y Computación , 2 (3): 325–336, doi : 10.1017 / S0963548300000705
- Jaeger, F .; Vertigan, DL; Welsh, DJA (1990), "Sobre la complejidad computacional de los polinomios de Jones y Tutte", Procedimientos matemáticos de la Sociedad Filosófica de Cambridge , 108 (1): 35–53, Bibcode : 1990MPCPS.108 ... 35J , doi : 10.1017 / S0305004100068936
- Linial, N. (1986), "Problemas difíciles de enumeración en geometría y combinatoria", SIAM J. Algebr. Métodos discretos , 7 (2): 331–335, doi : 10.1137 / 0607036 CS1 maint: parámetro desalentado ( enlace )
- Makowsky, JA; Rotics, U .; Averbouch, I .; Godlin, B. (2006), "Calcular polinomios de gráficos en gráficos de ancho de camarilla acotado", Proc. 32a Int. Worksh. Conceptos teóricos de gráficos en ciencias de la computación (WG 2006) , Lecture Notes in Computer Science, 4271 , Springer-Verlag, págs. 191–204, CiteSeerX 10.1.1.76.2320 , doi : 10.1007 / 11917496_18 , ISBN 978-3-540-48381-6
- Naor, J .; Naor, M .; Schaffer, A. (1987), "Algoritmos paralelos rápidos para grafos cordales", Proc. 19º ACM Symp. Teoría de la Computación (STOC '87) , págs. 355–364, doi : 10.1145 / 28395.28433 , ISBN 978-0897912211.
- Oxley, JG; Welsh, DJA (2002), "Polinomios cromáticos, de flujo y confiabilidad: la complejidad de sus coeficientes", Combinatoria, Probabilidad y Computación , 11 (4): 403–426, doi : 10.1017 / S0963548302005175
- Pemmaraju, S .; Skiena, S. (2003), Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica , Cambridge University Press, sección 7.4.2, ISBN 978-0-521-80686-2
- Read, RC (1968), "Una introducción a los polinomios cromáticos" (PDF) , Journal of Combinatorial Theory , 4 : 52–71, doi : 10.1016 / S0021-9800 (68) 80087-0
- Sekine, K .; Imai, H .; Tani, S. (1995), "Computación del polinomio de Tutte de un gráfico de tamaño moderado", Algoritmos y Computación, 6to Simposio Internacional, Lecture Notes in Computer Science 1004 , Cairns, Australia, 4 al 6 de diciembre de 1995: Springer, págs. . 224–233Mantenimiento de CS1: ubicación ( enlace )
- Sokal, AD (2004), "Las raíces cromáticas son densas en todo el plano complejo", Combinatoria, probabilidad y computación , 13 (2): 221-261, arXiv : cond-mat / 0012369 , doi : 10.1017 / S0963548303006023
- Stanley, RP (1973), "Orientaciones acíclicas de gráficos", Matemáticas discretas. , 5 (2): 171–178, doi : 10.1016 / 0012-365X (73) 90108-8
- Voloshin, Vitaly I. (2002), Coloración de hipergráficos mixtos: teoría, algoritmos y aplicaciones. , Sociedad Matemática Estadounidense, ISBN 978-0-8218-2812-0
- Wilf, HS (1986), Algoritmos y complejidad , Prentice-Hall, ISBN 978-0-13-021973-2
- Ellis-Monaghan, Joanna A .; Merino, Criel (2011). "Grafica polinomios y sus aplicaciones I: El polinomio de Tutte". En Dehmer, Matthias (ed.). Análisis estructural de redes complejas . arXiv : 0803.3079 . doi : 10.1007 / 978-0-8176-4789-6 . ISBN 978-0-8176-4789-6.
enlaces externos
- Weisstein, Eric W. "Polinomio cromático" . MathWorld .
- Polinomio cromático PlanetMath
- Código para calcular polinomios de flujo, cromáticos y de Tutte por Gary Haggard, David J. Pearce y Gordon Royle: [1]