Gráfico cúbico

En el campo matemático de la teoría de grafos , un grafo cúbico es un grafo en el que todos los vértices tienen grado tres. En otras palabras, un grafo cúbico es un grafo 3-regular . Los grafos cúbicos también se denominan grafos trivalentes .

Un grafo bicúbico es un grafo bipartito cúbico .

En 1932, Ronald M. Foster comenzó a recopilar ejemplos de grafos cúbicos simétricos , dando inicio al censo de Foster . ^{[ 1 ]} Muchos grafos individuales bien conocidos son cúbicos y simétricos, incluyendo el grafo de utilidad , el grafo de Petersen , el grafo de Heawood , el grafo de Möbius-Kantor , el grafo de Pappus , el grafo de Desargues , el grafo de Nauru , el grafo de Coxeter , el grafo de Tutte-Coxeter , el grafo de Dyck , el grafo de Foster y el grafo de Biggs-Smith . WT Tutte clasificó los grafos cúbicos simétricos según el número entero más pequeño s tal que cada par de caminos orientados de longitud s pueden mapearse entre sí mediante exactamente una simetría del grafo. Demostró que s es como máximo 5 y proporcionó ejemplos de grafos con cada valor posible de s desde 1 hasta 5. ^{[ 2 ]}

Entre los grafos cúbicos semisimétricos se incluyen el grafo de Gray (el grafo cúbico semisimétrico más pequeño), el grafo de Ljubljana y la jaula de Tutte de 12 elementos .

El grafo de Frucht es uno de los cinco grafos cúbicos más pequeños sin simetrías: ^{[ 3 ]} posee un único automorfismo de grafo , el automorfismo identidad. ^{[ 4 ]}

Según el teorema de Brooks, _todo grafo cúbico conexo distinto del grafo completo K₄ tiene una coloración de vértices con como máximo tres colores. Por lo tanto, todo grafo cúbico conexo distinto de K₄ tiene un conjunto independiente de al menos n /3 vértices, donde n es el número de vértices del grafo: por ejemplo, la clase de color más grande en una coloración _de 3 colores tiene al menos esta cantidad de vértices.

Según el teorema de Vizing, todo grafo cúbico requiere tres o cuatro colores para colorear sus aristas . Una coloración de tres aristas se conoce como coloración de Tait y forma una partición de las aristas del grafo en tres emparejamientos perfectos . Según el teorema de coloración de líneas de Kőnig, todo grafo bicúbico tiene una coloración de Tait.

Los grafos cúbicos sin puentes que no poseen una coloración de Tait se conocen como snarks . Entre ellos se incluyen el grafo de Petersen , el grafo de Tietze , los snarks de Blanuša , el snark de flor , el snark de doble estrella , el snark de Szekeres y el snark de Watkins . Existe un número infinito de snarks distintos. ^{[ 5 ]}

Los grafos cúbicos surgen de forma natural en topología de diversas maneras. Por ejemplo, los grafos cúbicos con 2g-2 vértices describen las diferentes formas de dividir una superficie de género g ≥ 2 en pares de pantalones . Si se considera un grafo como un complejo CW unidimensional , los grafos cúbicos son genéricos, ya que la mayoría de las aplicaciones de conexión de 1 celda son disjuntas del esqueleto 0 del grafo. Los grafos cúbicos también se forman como los grafos de poliedros simples en tres dimensiones, poliedros como el dodecaedro regular , cuya propiedad es que tres caras se encuentran en cada vértice.

Una incrustación de grafo arbitraria en una superficie bidimensional puede representarse como una estructura de grafo cúbico conocida como mapa codificado en grafo . En esta estructura, cada vértice de un grafo cúbico representa una bandera de la incrustación, una tripleta mutuamente incidente formada por un vértice, una arista y una cara de la superficie. Los tres vecinos de cada bandera son las tres banderas que se pueden obtener a partir de ella cambiando uno de los miembros de esta tripleta mutuamente incidente y dejando los otros dos miembros sin cambios. ^{[ 6 ]}

Se ha investigado mucho sobre la hamiltonicidad de los grafos cúbicos. En 1880, PG Tait conjeturó que todo grafo poliédrico cúbico tiene un circuito hamiltoniano . William Thomas Tutte proporcionó un contraejemplo a la conjetura de Tait , el grafo de Tutte de 46 vértices , en 1946. En 1971, Tutte conjeturó que todos los grafos bicúbicos son hamiltonianos. Sin embargo, Joseph Horton proporcionó un contraejemplo en 96 vértices, el grafo de Horton . ^{[ 7 ]} Más tarde, Mark Ellingham construyó dos contraejemplos más: los grafos de Ellingham-Horton . ^{[ 8 ] [ 9 ]} La conjetura de Barnette , una combinación aún abierta de las conjeturas de Tait y Tutte, afirma que todo grafo poliédrico bicúbico es hamiltoniano. Cuando un grafo cúbico es hamiltoniano, la notación LCF permite representarlo de forma concisa.

Si se elige un grafo cúbico uniformemente al azar entre todos los grafos cúbicos de n vértices, entonces es muy probable que sea hamiltoniano: la proporción de grafos cúbicos de n vértices que son hamiltonianos tiende a uno en el límite cuando n tiende a infinito. ^{[ 10 ]}

David Eppstein conjeturó que cada grafo cúbico de n vértices tiene como máximo 2 ^{n /3} (aproximadamente 1,260 ⁿ ) ciclos hamiltonianos distintos, y proporcionó ejemplos de grafos cúbicos con esa cantidad de ciclos. ^{[ 11 ]} La mejor estimación demostrada para el número de ciclos hamiltonianos distintos es${\displaystyle O({1.276}^{n})}$. ^{[ 12 ]}

Problema sin resolver en matemáticas

¿Cuál es el mayor ancho de camino posible de un${\displaystyle n}$-¿grafo cúbico de vértices?

Más problemas sin resolver en matemáticas

El ancho de camino de cualquier grafo cúbico de n vértices es como máximo n /6. El límite inferior más conocido para el ancho de camino de los grafos cúbicos es 0,082 n . Se desconoce cómo reducir esta diferencia entre este límite inferior y el límite superior de n /6. ^{[ 13 ]}

Del lema del apretón de manos , demostrado por Leonhard Euler en 1736 como parte del primer artículo sobre teoría de grafos, se deduce que todo grafo cúbico tiene un número par de vértices.

El teorema de Petersen afirma que todo grafo cúbico sin puentes tiene un emparejamiento perfecto . ^{[ 14 ]} Lovász y Plummer conjeturaron que todo grafo cúbico sin puentes tiene un número exponencial de emparejamientos perfectos. La conjetura fue demostrada recientemente, mostrando que todo grafo cúbico sin puentes con n vértices tiene al menos 2 ^n/3656 emparejamientos perfectos. ^{[ 15 ]}

Varios investigadores han estudiado la complejidad de algoritmos de tiempo exponencial restringidos a grafos cúbicos. Por ejemplo, al aplicar programación dinámica a una descomposición de caminos del grafo, Fomin y Høie demostraron cómo encontrar sus conjuntos independientes máximos en tiempo 2 ^{n /6  +  o( n )} . ^{[ 13 ]} El problema del viajante en grafos cúbicos se puede resolver en tiempo O(1,2312 ⁿ ) y espacio polinomial. ^{[ 16 ] [ 17 ]}

Varios problemas importantes de optimización de grafos son APX difíciles , lo que significa que, aunque tienen algoritmos de aproximación cuya razón de aproximación está limitada por una constante, no tienen esquemas de aproximación de tiempo polinomial cuya razón de aproximación tiende a 1 a menos que P=NP . Estos incluyen los problemas de encontrar una cobertura de vértices mínima , un conjunto independiente máximo , un conjunto dominante mínimo y un corte máximo . ^{[ 18 ]} El número de cruces (el número mínimo de aristas que se cruzan en cualquier dibujo del grafo ) de un grafo cúbico también es NP-difícil para grafos cúbicos pero puede aproximarse. ^{[ 19 ]} Se ha demostrado que el problema del viajante de comercio en grafos cúbicos es NP-difícil de aproximar con cualquier factor menor que 1153/1152. ^{[ 20 ]}

• Tabla de gráficas cúbicas simples

• Royle, Gordon. "Gráficos cúbicos simétricos (El censo de Foster)" . Archivado del original el 23 de octubre de 2011.
• Weisstein, Eric W. "Grafo bicúbico" . MathWorld .
• Weisstein, Eric W. "Grafo cúbico" . MathWorld .
• Brinkmann, Gunnar; Goedgebeur, enero; Van Cleemput, Nico (2013). «La historia de la generación de gráficas cúbicas» (PDF) . Int. J. química. Modelado . 5 ( 2-3 ). Ciencia nueva: 67– 89. ISSN 1941-3955 .