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 regular de 3- . Los grafos cúbicos también se denominan grafos trivalentes .
Un gráfico bicúbico es un gráfico bipartito cúbico .
En 1932, Ronald M. Foster comenzó a recopilar ejemplos de grafos cúbicos simétricos , lo que dio origen al censo Foster . [1] Muchos grafos individuales bien conocidos son cúbicos y simétricos, incluidos 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 por el número entero más pequeño s de modo que cada dos caminos orientados de longitud s se puedan mapear entre sí por 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 de 1 a 5. [2]
Los grafos cúbicos semisimétricos incluyen el grafo de Gray (el grafo cúbico semisimétrico más pequeño), el grafo de Ljubljana y el grafo de Tutte de 12 jaulas .
El grafo de Frucht es uno de los cinco grafos cúbicos más pequeños sin ninguna simetría: [3] posee solo 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 4 tiene una coloración de vértices con tres colores como máximo. Por lo tanto, todo grafo cúbico conexo distinto de K 4 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 tiene al menos esta cantidad de vértices.
Según el teorema de Vizing, cada grafo cúbico necesita tres o cuatro colores para la coloración de las 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 coincidencias perfectas . Según el teorema de coloración de líneas de König, cada grafo bicúbico tiene una coloración de Tait.
Los grafos cúbicos sin puente que no tienen una coloración de Tait se conocen como snarks . 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 . Hay un número infinito de snarks distintos. [5]
Los grafos cúbicos surgen naturalmente en topología de varias maneras. Por ejemplo, los grafos cúbicos con 2g-2 vértices describen las diferentes maneras de cortar una superficie de género g ≥ 2 en pares de pantalones . Si se considera que un grafo es un complejo CW unidimensional , los grafos cúbicos son genéricos en el sentido de que la mayoría de los mapas de unión de 1 celda son disjuntos 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 con la propiedad de que tres caras se encuentran en cada vértice.
Una incrustación de un gráfico arbitrario en una superficie bidimensional puede representarse como una estructura de gráfico cúbico conocida como mapa codificado de gráfico . En esta estructura, cada vértice de un gráfico cúbico representa una bandera de la incrustación, un triple mutuamente incidente de un vértice, una arista y una cara de la superficie. Los tres vecinos de cada bandera son las tres banderas que pueden obtenerse 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 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 la conjetura de Tait y de Tutte, establece que todo grafo poliédrico bicúbico es hamiltoniano. Cuando un grafo cúbico es hamiltoniano, la notación MCF permite representarlo de forma concisa.
Si se elige un grafo cúbico de manera uniforme y aleatoria entre todos los grafos cúbicos de n vértices, entonces es muy probable que sea hamiltoniano: la proporción de los 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 n ) ciclos hamiltonianos distintos, y proporcionó ejemplos de grafos cúbicos con esa cantidad de ciclos. [11] La mejor estimación probada para el número de ciclos hamiltonianos distintos es . [12]
El ancho de ruta 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 ruta de los grafos cúbicos 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 desprende que todo grafo cúbico tiene un número par de vértices.
El teorema de Petersen establece que cada grafo cúbico sin puente tiene un emparejamiento perfecto . [14] Lovász y Plummer conjeturaron que cada grafo cúbico sin puente tiene un número exponencial de emparejamientos perfectos. La conjetura fue demostrada recientemente, mostrando que cada grafo cúbico sin puente con n vértices tiene al menos 2 n/3656 emparejamientos perfectos. [15]
Varios investigadores han estudiado la complejidad de los algoritmos de tiempo exponencial restringidos a grafos cúbicos. Por ejemplo, al aplicar programación dinámica a una descomposición de trayectorias del grafo, Fomin y Høie demostraron cómo encontrar sus conjuntos independientes máximos en el tiempo 2 n /6 + o( n ) . [13] El problema del viajante de comercio en grafos cúbicos se puede resolver en el tiempo O(1.2312 n ) y en el espacio polinomial. [16] [17]
Varios problemas importantes de optimización de grafos son APX-hard , 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 mínima de vértices , 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 de grafo ) de un grafo cúbico también es NP-hard para grafos cúbicos, pero se puede aproximar. [19] Se ha demostrado que el problema del viajante en grafos cúbicos es NP-hard de aproximar dentro de cualquier factor menor que 1153/1152. [20]
