En el campo matemático de la teoría de grafos , una gráfica cúbica es una gráfica en la que todos los vértices tienen grado tres. En otras palabras, una gráfica cúbica es una gráfica de 3 regulares . Las gráficas cúbicas también se llaman gráficas trivalentes .
Una gráfica bicúbica es una gráfica bipartita cúbica .
En 1932, Ronald M. Foster comenzó a recopilar ejemplos de gráficas simétricas cúbicas , lo que marcó el inicio del censo de Foster . [1] Muchos gráficos individuales conocidos son cúbicos y simétricos, incluido el gráfico de utilidad , el gráfico de Petersen , el gráfico de Heawood , el gráfico de Möbius-Kantor , el gráfico de Pappus , el gráfico de Desargues , el gráfico de Nauru , el gráfico de Coxeter , el Gráfico de Tutte-Coxeter , gráfico de Dyck , gráfico de Foster y gráfico de Biggs-Smith . WT Tutte clasificó las gráficas cúbicas simétricas por el número entero más pequeño s , de modo que cada dos caminos orientados de longitud s puedan asignarse entre sí mediante exactamente una simetría de la gráfica. Demostró que s es como máximo 5 y proporcionó ejemplos de gráficas con cada valor posible de s de 1 a 5. [2]
Los gráficos cúbicos semisimétricos incluyen el gráfico de Gray (el gráfico cúbico semisimétrico más pequeño), el gráfico de Liubliana y el gráfico de 12 jaulas de Tutte .
El gráfico de Frucht es uno de los cinco gráficos cúbicos más pequeños sin simetrías: [3] posee un solo automorfismo de gráfico , el automorfismo de identidad. [4]
Según el teorema de Brooks, todo gráfico cúbico conexo que no sea el gráfico completo K 4 tiene una coloración de vértice con como máximo tres colores. Por lo tanto, cada gráfico cúbico conectado distinto de K 4 tiene un conjunto independiente de al menos n /3 vértices, donde n es el número de vértices en el gráfico: por ejemplo, la clase de color más grande en un color de 3 tiene al menos esta cantidad vértices.
Según el teorema de Vizing, cada gráfico cúbico necesita tres o cuatro colores para colorear los bordes . Una coloración de 3 bordes se conoce como coloración Tait y forma una partición de los bordes del gráfico en tres coincidencias perfectas . Según el teorema de coloración de líneas de Kőnig, cada gráfico bicúbico tiene una coloración Tait.
Los gráficos cúbicos sin puente que no tienen coloración Tait se conocen como snarks . Incluyen el gráfico de Petersen , el gráfico de Tietze , los snarks de Blanuša , el snark de flores , el snark de doble estrella , el snark de Szekeres y el snark de Watkins . Hay un número infinito de snarks distintos. [5]
Los gráficos cúbicos surgen naturalmente en la topología de varias maneras. Por ejemplo, las gráficas cúbicas con vértices 2g-2 describen las diferentes formas de cortar una superficie de género g ≥ 2 en pares de pantalones . Si se considera que un gráfico es un complejo CW unidimensional , los gráficos cúbicos son genéricos en el sentido de que la mayoría de los mapas adjuntos de 1 celda están separados del esqueleto 0 del gráfico. Los gráficos cúbicos también se forman como gráficos de poliedros simples en tres dimensiones, poliedros como el dodecaedro regular con la propiedad de que tres caras se encuentran en cada vértice.
Un gráfico arbitrario incrustado en una superficie bidimensional se puede representar como una estructura de gráfico cúbico conocida como mapa codificado por gráfico . En esta estructura, cada vértice de un gráfico cúbico representa una bandera de la incrustación, una tripleta mutuamente incidente de un vértice, una arista y una cara de la superficie. Las tres vecinas de cada bandera son las tres banderas que se pueden obtener de ella cambiando uno de los miembros de este triple mutuamente incidente y dejando los otros dos miembros sin cambios. [6]
Se han realizado muchas investigaciones sobre la hamiltonicidad de las gráficas cúbicas. 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 gráfico de Tutte de 46 vértices , en 1946. En 1971, Tutte conjeturó que todos los gráficos bicúbicos son hamiltonianos. Sin embargo, Joseph Horton proporcionó un contraejemplo sobre 96 vértices, el gráfico de Horton . [7] Más tarde, Mark Ellingham construyó dos contraejemplos más: los gráficos de Ellingham-Horton . [8] [9] La conjetura de Barnette , una combinación aún abierta de la conjetura de Tait y Tutte, establece que todo gráfico poliédrico bicúbico es hamiltoniano. Cuando un gráfico cúbico es hamiltoniano, la notación LCF permite representarlo de manera concisa.
Si se elige uniformemente al azar una gráfica cúbica entre todas las gráficas cúbicas de n -vértices, entonces es muy probable que sea hamiltoniana: la proporción de las gráficas cúbicas de n -vértices que son hamiltonianas tiende a uno en el límite cuando n tiende al infinito. [10]
David Eppstein conjeturó que cada gráfico cúbico de n -vértices tiene como máximo 2 n /3 (aproximadamente 1,260 n ) ciclos hamiltonianos distintos, y proporcionó ejemplos de gráficos cúbicos con esa cantidad de ciclos. [11] La estimación mejor probada para el número de ciclos hamiltonianos distintos es . [12]
¿ Cuál es el mayor ancho de ruta posible de un gráfico cúbico de vértices?
El ancho de ruta de cualquier gráfico cúbico de n -vértices es como máximo n /6. El límite inferior más conocido del ancho de ruta de las gráficas cúbicas es 0,082 n . No se sabe cómo reducir esta brecha entre este límite inferior y el límite superior 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 establece que todo grafo cúbico sin puente tiene una coincidencia perfecta . [14] Lovász y Plummer conjeturaron que cada gráfico cúbico sin puentes tiene un número exponencial de coincidencias perfectas. La conjetura se demostró recientemente y muestra que cada gráfico cúbico sin puentes con n vértices tiene al menos 2 n/3656 coincidencias perfectas. [15]
Varios investigadores han estudiado la complejidad de los algoritmos de tiempo exponencial restringidos a gráficos cúbicos. Por ejemplo, al aplicar programación dinámica a una descomposición de trayectorias del gráfico, Fomin y Høie mostraron cómo encontrar sus conjuntos independientes máximos en el tiempo 2 n /6 + o( n ) . [13] El problema del viajante en gráficas cúbicas se puede resolver en el tiempo O(1.2312 n ) y en el espacio polinomial. [16] [17]
Varios problemas importantes de optimización de gráficos son APX difíciles , lo que significa que, aunque tienen algoritmos de aproximación cuya relación de aproximación está limitada por una constante, no tienen esquemas de aproximación de tiempo polinómico cuya relación de aproximación tiende a 1 a menos que P=NP . Estos incluyen los problemas de encontrar una cobertura de vértice mínima , un conjunto independiente máximo , un conjunto dominante mínimo y un corte máximo . [18] El número de cruce (el número mínimo de aristas que se cruzan en cualquier dibujo de gráfico ) de un gráfico cúbico también es NP-duro para gráficos cúbicos, pero puede ser aproximado. [19] Se ha demostrado que el problema del viajante en gráficas cúbicas es NP-difícil de aproximar dentro de cualquier factor menor que 1153/1152. [20]
