Gráficas equivalentes de acuerdo con sus polinomios cromáticos
13/12/2025 | https://doi.org/10.63083/lamec.2025.79.grs
Resumen
A una gráfica G = (V, A) se le puede asociar un polinomio P (G, λ), denominado el polinomio cromático de G que cuenta el número de λ-coloraciones propias distintas de G. Sea n el orden de G, n = |V|. Se define una relación de equivalencia Rc sobre las gráficas conexas de un cierto orden n, de tal manera que dos gráficas son cromáticamente equivalentes si y sólo si tienen el mismo polinomio cromático. Las soluciones que aquí se muestran fueron obtenidas por alumnos de la UAM Azcapotzalco, en la fase final de su formación en la licenciatura de Ingeniería en Computación, durante diferentes periodos de tiempo, que van desde 2013 hasta 2024.
Introducción
Se considera una gráfica o grafo como un par (V, E) en donde V es un conjunto finito no vacío y E un subconjunto de V × V. Se denota como G = (V, E) y se dice que V es el conjunto de vértices y E el conjunto de aristas de G.
Se consideran gráficas G sin lazos, si además G no tiene aristas múltiples, se dice que G es simple. Se dice que una asignación de colores a los vértices de G es propia si ningún par de vértices adyacentes tienen el mismo color. Sea λ ∈ N, una λ-coloración propia de G es una asignación propia de λcolores a los vértices de G. Al mínimo λ para el cuál G tienen una λ-coloración propia se la llama el número cromático de G y se denota por χ(G).
Ejemplo 1.1. En la figura 1, se muestra a la izquierda, una gráfica con 10 vértices; a la derecha una coloración propia del ciclo C5 .
Figura 1: Una gráfica G y una coloración propia de C5
A una gráfica simple G, se le puede asociar un polinomio P(G, λ). Este polinomio tiene como antecedente una función cromática P(M, λ), con λ ∈ N, propuesta por Birkhoff en 1912, para colorear propiamente los países que forman un mapa M. Esta función fue generalizada para colorear los vértices de gráficas arbitrarias por Whitney en 1932, dando lugar al polinomio cromático P (G, λ).
Sean G una gráfica sin lazos y λ ∈ N. Se dice que dos λ-coloraciones c1 y c2 de G son distintas (c1 ≠ c2) si existe un vértice v en G tal que tiene asignados colores diferentes en c1 y c2. Así, P(G, λ) para λ ∈ N y proporciona el número de λ-coloraciones propias distintas de una gráfica simple G.
Por convención P (G, 0) = 0. Por definición P(G, λ) ≥ 1 si y sólo si G tiene una λ-coloración, así, P (G, χ(G)) ≥ 1. El número cromático de G puede definirse en términos de la función P(G, λ) como χ(G) = mín {λ ∈ N: P(G, λ) ≥ 1}.
Ejemplo 1.2. En la figura 2, se muestra el ciclo C3, P (C3, λ) = λ3− 3λ2 +2λ, y su evaluación en 3, que corresponde a las seis distintas coloraciones propias de C3.
Si G = (V, E) tal que |V | = n y E = ∅, entonces G consta de n vértices aislados y P(G; λ) = λn. Si GA denota un árbol de orden n, se puede demostrar por inducción sobre n = |V | que P (GA, λ) = λ (λ−1)(n−1), ver en el libro de Harari1 . Para las gráficas completas Kn y λ ≥ n, hay λ colores disponibles para el primer vértice, λ−1 para el segundo vértice, y continuando de esa manera se llega a que P(Kn, λ) = λ (λ−1) (λ−2) · · · (λ−n+1).
Dada una gráfica no conexa, con k componentes conexas G1, G2, . . . , Gk, se cumple que P(G, λ) =P(G1, λ) P(G2, λ) . . . P(Gk, λ).
Ejemplo 1.3. En la figura 3, en la izquierda se muestra un árbol GA con las asignaciones posibles de colores para sus vértices. En la derecha K4 y su polinomio, P(K4, λ) = λ (λ−1) (λ − 2) (λ − 3).
En general, para obtener P(G, λ) para una gráfica simple G se consideran dos teoremas que proporcionan métodos recursivos de cálculo. El primero permite la obtención de P(G, λ) como la suma de funciones cromáticas de gráficas completas y dado que P (Kn, λ) es un polinomio en λ para toda n ∈ N, se puede concluir que P(G, λ) es un polinomio.
Teorema 1.1. Sean G una gráfica simple, u y v dos vértices no adyacentes en G. Si se define G+uv como G aumentada por la arista (u,v) y G·uv como la gráfica obtenida de G identificando los vértices u y v, e identificando las correspondientes aristas múltiples si es el caso. Entonces:
P(G, λ) = P(G+uv, λ) + P(G·uv, λ).
Una demostración del teorema 1.1, puede verse en Wilson2 . El segundo teorema permite obtener una forma recursiva para calcular P (G, λ) como la diferencia de los polinomios de los menores de G respecto a una arista e de G. Este último teorema se puede demostrar por inducción sobre el número de aristas de G.
Teorema 1.2. Sea G una gráfica simple y e cualquier arista de G. Se denotan los menores de G respecto a e como G\e y G/e, las gráficas obtenida por el borrado de la arista e y la contracción de la arista e, respectivamente. Se cumple que
P(G, λ) = P(G\e, λ) − P(G/e, λ)
El polinomio cromático P(G, λ) es un invariante de G, así dos gráficas isomorfas tienen el mismo polinomio cromático. Si G es una gráfica con n vértices y m aristas, se cumple para P(G, λ) que su grado es n, el coeficiente de λn es uno, su segundo término es (−m)λn−1, no tiene un término constante y los coeficientes del polinomio alternan en signo. Además, (−1)nP (G, −1) cuenta las orientaciones acíclicas de G, [Li, Whitehead, 1992].
Los teoremas 1.1 y 1.2 proveen de fórmulas recursivas para calcular el polinomio cromático P(G, λ) para G una gráfica simple. Se desconoce algún algoritmo capaz de calcular P(G, λ) en tiempo polinomial.
Problemas resueltos
3.1 Problema de Akiyama y Harary para n ≤ 8
Los resultados de esta sección fueron obtenidos por Adán Mateos Hernández
Sean G una gráfica y Gc su gráfica complementaria. Una gráfica G es auto-complementaria si G es isomorfa a Gc. En 1980, Akiyama y Harary plantearon la pregunta si existirían gráficas G y Gc no autocomplementarias tales que P (G, λ) = P (Gc, λ). En 1995, J. Xu y Z. Liu, mostraron que dicho problema tiene solución positiva [Xu, Zhenhong, 1995] .
Definición 2.1. Se dice que las gráficas G y y Gc cumplen la condición de Akiyama-Harari (A-H), si para G no isomorfa a Gc se cumple que P (G, λ) = P (Gc, λ).
Sea una gráfica conexa tal que V (G) = {v1, v2, . . . , vn} y di es el grado de vi, para i = 1, 2, . . . , n. Al vector d(G) = (d1, d2, …, dn) se la llamará la huella de G. Dadas dos gráficas G1 y G2 se dice que son coincidentes en huellas (c-h) si existe un etiquetamiento de sus vértices tal que d(G1) = d(G2).
Lema 2.1. Dadas dos gráficas G y Gc que son c-h, se cumple que n ≡ 0, 1(mod 4).
Demostración. Si d(G) = d(Gc), entonces |E(G)| = |E(Gc)| =1/4 n (n − 1), por lo que n ≡ 0, 1 (mód 4), pues |E(G)| ∈ Z+.
Proposición 2.1. [Xu, Zhenhong, 1995] No existe una gráfica G de orden n ≡ 2, 3 (mod 4) que cumpla que P (G, λ) = P (Gc, λ).
Demostración. Supóngase que existe una gráfica G tal que P(G, λ) = P (Gc, λ) y n ≡ 2, 3 (mod 4), entonces |E(G)| = |E (Gc)|, así |E(G)|+|E(Gc)| debe ser par, pero 1/2(4k+2) (4k+1) y 1/2(4k+3) (4k+2) son impares, si k ∈ Z+, lo cual es una contradicción.
Proposición 2.2. No existe una gráfica G de orden n < 8 que cumpla la condición de A-H.
Demostración. Si n < 8, por la proposición 2.1, solo es necesario analizar los casos n = 4, 5. Las gráficas de orden n=4 con el mismo polinomio cromático son las trayectorias con cuatro vértices P4, estas gráficas son autocomplementarias. Luego, para n=4 no hay parejas G y Gc que cumplan la condición de A-H. Para las gráficas de orden n=5, hay seis gráficas que tienen cinco vértices y cinco aristas, dos son autocomplementarias, las otras no satisfacen la condición de A-H, ver la figura 4.
Ejemplo 2.1. En la figura 4, se observan dos gráficas autocomplementarias de orden cinco y que no cumplen la condición de A-H.
Lema 2.2. [Xu, Zhenhong, 1995] No existen G y Gc, no ambas conexas, que cumplan la condición de A-H.
Proposición 2.3. [A. Mateos] Hay 50 parejas de gráficas conexas de orden n=8, que cumplen la condición de A-H.
Demostración. Sea m el número de aristas de una gráfica G. Se consideran las gráficas K8; G y Gc subgráficas de K8 tales que G y Gc no son autocomplementarias, pero coinciden en sus números de vértices y de aristas dado que P (G, λ) = P (Gc, λ).
La búsqueda de dichas gráficas con n=8 y m=14 se efectuó computacionalmente. La generación de las parejas G y Gc se hizo mediante el uso del paquete COS. Se construyó un programa en lenguaje C++ que permitió exportar los resultados generados por COS al paquete MAPLE, con este programa se realizó una prueba de conexidad, para satisfacer el lema 2.2. Así para n =8 y m=14 se obtuvieron 50 parejas de gráficas conexas que cumplen la condición de A-H.
Ejemplo 2.3. Como ejemplo de la validez de la proposición 2.3, en la figura 5 se muestran dos gráficas con n=8 y m=14, que cumplen la condición de A-H.
Ejemplo 2.4. En la figura 6 se muestran dos gráficas G y su complemento Gc de orden nueve que cumplen la propiedad de A-H. Sus huellas son d(G) = {2, 3, 4, 4, 4, 4, 5, 5, 5} y d(Gc) = {3, 3, 3, 4, 4, 4, 4, 5, 6}. Su polinomio es P(G, λ) = P (Gc, λ) = λ (λ − 1) (λ − 2) (λ − 3)2(λ4 − 9λ3 + 35λ2 − 69λ + 57).
3.2 Equivalencia cromática. Particiones de las gráficas de orden n
Los resultados de esta sección fueron obtenidos por Ángel David Téllez Macías.
Definición 2.2. Sean G y H dos gráficas de orden n. Se dice que G y H son χ-equivalentes o cromáticamente equivalentes si y solo si tienen el mismo polinomio cromático. A esta relación se le denotará por ∼χ . Así,
G ∼χ H si y solo si P (G, λ) = P (H, λ).
Se tiene que ∼χ es una relación de equivalencia definida en el conjunto de las gráficas de un orden dado n. Esta relación ∼χ parte el conjunto de todas las gráficas de orden n, en clases de equivalencia.
Ejemplos de gráficas χ-equivalentes son los bosques del mismo orden y mismo número de componentes, en particular los árboles del mismo orden, así como los q-árboles del mismo orden.
Sea G una gráfica de orden n, se denota como [G] a la clase de equivalencia formada por las gráficas χ-equivalentes a G, es decir [G] = {H ∈ G : H ∼χ G}. En la figura 7, se muestran dos gráficas de orden seis que son χ-equivalentes.
Definición 2.3. Se dice que una gráfica es χ- única o cromáticamente única si [G] = {G}.
Son ejemplos de gráficas χ- únicas, la gráfica vacía On , los ciclos Cm, con m ≥ 3, las gráficas completas Kn con n ≥ 1, las gráficas completas bipartitas Kn,n con n ≥ 1 y las ruedas Wn si n es par, ver el libro de Biggs3.
En la figura 8 se puede observar una gráfica χ- única y su polinomio cromático. En este trabajo, se presentan las particiones de todas las gráficas de orden n, para 1 ≤ n ≤ 5.
Para n=1 solo se tiene la gráfica que consta de un único vértice y cuyo polinomio cromático es P(λ) = λ. Para n=2, hay dos gráficas no isomorfas, la primera es la gráfica formada por dos vértices no adyacentes cuyo polinomio es P(λ) = λ2 y la segunda gráfica consta de dos vértices adyacentes con polinomio P(λ)= λ2 − λ. Para n=3, hay cuatro clases, las cuales se muestran en la figura 9.
Hasta n=3 cada clase tiene solo una gráfica χ- única. Para n=4 se tienen nueve clases, dos de ellas de cardinalidad dos y las siete clases restantes están formadas cada una por una gráfica χ- única.
Ejemplo 2.5. En la figura 9 se muestra la partición para las gráficas de orden n=3. Sus polinomios cromáticos son: (1) P(G, λ) = λ3, (2) P(G, λ) = λ3 − λ2, (3) P(G, λ) = λ3 − 2λ2 + λ y (4) P(G, λ) = λ3 − 3λ2 + 2λ.
Proposición 2.4. [Téllez] Para n=5, hay 23 clases cromáticas, de las cuales 16 están formadas por gráficas χ- únicas. Las particiones se muestran en la figura 10.
Para calcular la partición de las gráficas simples de orden cinco en clases cromáticas, se usaron los paquetes Nauty y Maple. El primero permitió obtener todas las gráficas simples no isomorfas expresadas mediante sus matrices de adyacencia. Con auxilio de Maple y mediante el uso de interfases en lenguaje C, se calcularon los polinomios correspondientes a las 32 clases cromáticas.
En la figura 10 se muestra la partición de las gráficas simples de orden cinco. En la parte izquierda se pueden ver las clases de cardinalidad mayor o igual a dos. En la derecha se pueden observar las gráficas que son χ- únicas.
3.3 Programa Calculadora Cromática
El programa fue elaborado por Luis Daniel Ramos López
Dada una gráfica G y su polinomio cromático P(G, λ). La cromaticidad de una clase cromática [G] es el número de gráficas no isomorfas que la conforman.
En esta sección se reporta la elaboración de un programa, que se denominó “Calculadora Cromática”, el cual tiene dos funciones:
3.3.1 Realizar el cálculo de P(G, λ) para una gráfica simple G.
3.3.2 Hallar la clase cromática de la gráfica G, dentro del universo de las gráficas del orden de G.
Dada una gráfica simple G y su matriz de adyacencia o bien su lista de parejas de vértices que forman sus aristas, se calcula el polinomio cromático de la gráfica G, como una aplicación del teorema 1.1, el cual permite construir una función recursiva para determinar el polinomio P (G, λ), de la siguiente manera:
Algoritmo de borrado – contracción f(Gráfica G)
si G no tiene aristas
regresa λ|V | si no Arista e (Una arista de A)
regresa f (G \ e) − f (G · e).
Sea n el orden de G. Se usó el lenguaje C++ para programar el algoritmo, además del paquete Nauty and Frames para calcular las gráficas no isomorfas de orden n. El programa para el cálculo de las clases cromáticas de orden n, toma como entrada un archivo de texto con cada una de las gráficas previamente calculadas por Nauty and Frames y codificadas en matrices de adyacencia, el programa calcula el polinomio cromático con una función que toma como entrada una matriz de booleanos y regresa una cadena, que es una forma codificada del polinomio cromático.
Por otro lado, el cálculo de P(G, λ) se basó en el algoritmo de borrado – contracción, programado en Java, el uso de los dos lenguajes de programación parecidos en ciertas sintaxis, permitió disminuir las líneas de código en el lenguaje Java, teniendo como base el código escrito en C++.
El problema de calcular el polinomio cromático de una gráfica G es NP -completo, respecto al orden de G. La complejidad en cuanto a tiempo de ejecución del algoritmo de borrado–contracción es exponencial.
Ejemplo 2.6. Algoritmo de borrado – contracción para la gráfica C3:
Se obtiene P (C3 , λ) = λ3 − λ2 − (λ2 − λ) − (λ2 − λ). Simplificando el polinomio, se obtiene P (λ) = λ (λ − 1) (λ − 2).
Ejemplo 2.7. En la figura 10, en la primera clase de izquierda a derecha, se muestra una clase cromática con cromaticidad 2. En la figura 12, se observa una captura de pantalla de la Calculadora Cromática, en la que recibe la matriz de adyacencia de la gráfica superior, izquierda en la figura 12, el programa arroja como resultado a la misma gráfica, más otra que pertenece a su misma clase cromática, ventana derecha de la figura 12.
- Harari F., Graph Theory, Addison-Wesley Publishing Company Inc., (1972) ↩︎
- Wilson R,. Introducción a la Teoría de Grafos, Alianza Editorial, (1983) ↩︎
- Biggs N., Algebraic graph theory, Cambridge University Press, (1993) ↩︎
La Mecedora Divulga is licensed under CC BY-NC-ND 4.0
