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 gráfico cúbico es un gráfico regular 3 . Las gráficas cúbicas también se denominan gráficas trivalentes .
Un gráfico bicúbico es un gráfico bipartito cúbico .
Simetría
En 1932, Ronald M. Foster comenzó a recopilar ejemplos de gráficos simétricos cúbicos , formando el inicio del censo de Foster . [1] Muchos gráficos individuales conocidos son cúbicos y simétricos, incluidos 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 El gráfico de Tutte-Coxeter , el gráfico de Dyck , el gráfico de Foster y el 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 trayectorias orientadas de longitud s pueden mapearse entre sí mediante exactamente una simetría de la gráfica. Mostró que s es como máximo 5 y proporcionó ejemplos de gráficos con cada valor posible de s de 1 a 5. [2]
Los gráficos cúbicos semi-simétricos incluyen el gráfico de Gray (el gráfico cúbico semi-simétrico más pequeño), el gráfico de Ljubljana y el Tutte de 12 jaulas .
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 gráfico , el automorfismo de identidad. [4]
Conjuntos para colorear e independientes
De acuerdo con el teorema de Brooks, cada gráfico cúbico conectado que no sea el gráfico completo K 4 puede colorearse con un máximo de tres colores. Por lo tanto, cada grafo cúbico conectado que no sea 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 una coloración 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 combinaciones perfectas . Según el teorema de coloración de líneas de Kőnig, cada gráfico bicúbico tiene una coloración de Tait.
Los gráficos cúbicos sin puentes que no tienen un color Tait se conocen como snarks . Estos incluyen el gráfico de Petersen , el gráfico de Tietze , los snarks Blanuša , el snark flor , el Snark-estrella doble , los Szekeres Snark y los Watkins Snark . Hay un número infinito de snarks distintos. [5]
Topología y geometría
Los gráficos cúbicos surgen naturalmente en la topología de varias formas. Por ejemplo, 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 los 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áficos . En esta estructura, cada vértice de un gráfico cúbico representa una bandera de la incrustación, una triple incidencia mutua de un vértice, borde y cara de la superficie. Los tres vecinos de cada bandera son las tres banderas que se pueden obtener de ella cambiando uno de los miembros de este triple incidente mutuo y dejando los otros dos miembros sin cambios. [6]
Hamiltonicidad
Ha habido mucha investigación sobre la hamiltonicidad de los gráficos cúbicos. En 1880, PG Tait conjeturó que cada grafo poliédrico cúbico tiene un circuito hamiltoniano . William Thomas Tutte proporcionó un contraejemplo de 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 en 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 cada grafo poliédrico bicúbico es hamiltoniano. Cuando un gráfico cúbico es hamiltoniano, la notación LCF permite representarlo de forma concisa.
Si un gráfico cúbico se elige uniformemente al azar entre todos los gráficos cúbicos de n -vértices, entonces es muy probable que sea hamiltoniano: la proporción de los gráficos cúbicos de n -vértices que son hamiltonianos tiende a uno en el límite cuando n va 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 mejor estimación probada del número de ciclos hamiltonianos distintos es. [12]
Otras propiedades
¿Cuál es el ancho de ruta más grande posible de un-Gráfico cúbico de vértice?
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 en el ancho de ruta de los gráficos 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]
Se deduce del lema del apretón de manos , probado por Leonhard Euler en 1736 como parte del primer artículo sobre teoría de grafos, que cada grafo cúbico tiene un número par de vértices.
El teorema de Petersen establece que cada grafo cúbico sin puentes tiene una correspondencia perfecta . [14] Lovász y Plummer conjeturaron que cada gráfico cúbico sin puentes tiene un número exponencial de emparejamientos perfectos. La conjetura fue probada recientemente, mostrando que cada grafo cúbico sin puentes con n vértices tiene al menos 2 n / 3656 emparejamientos perfectos. [15]
Algoritmos y complejidad
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 ruta 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 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 polinomial 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 bordes que se cruzan en cualquier dibujo de gráfico ) de un gráfico cúbico también es NP-difícil para gráficos cúbicos, pero puede ser aproximado. [19] El vendedor ambulante Problema en gráficos cúbicos se ha demostrado ser NP-duro a la aproximación a dentro de cualquier factor de menos de 1153/1152. [20]
Ver también
- Tabla de gráficos cúbicos simples
Referencias
- ^ Foster, RM (1932), "Circuitos geométricos de redes eléctricas", Transacciones del Instituto Americano de Ingenieros Eléctricos , 51 (2): 309–317, doi : 10.1109 / T-AIEE.1932.5056068 , S2CID 51638449.
- ^ Tutte, WT (1959), "Sobre la simetría de grafos cúbicos" , Can. J. Math. , 11 : 621–624, doi : 10.4153 / CJM-1959-057-2.
- ^ Bussemaker, FC; Cobeljic, S .; Cvetkovic, DM; Seidel, JJ (1976), Investigación informática de gráficos cúbicos , informe EUT, 76-WSK-01, Departamento de Matemáticas y Ciencias de la Computación, Universidad Tecnológica de Eindhoven
- ^ Frucht, R. (1949), "Gráficos de grado tres con un grupo de resumen dado", Canadian Journal of Mathematics , 1 (4): 365–378, doi : 10.4153 / CJM-1949-033-6 , ISSN 0008-414X , MR 0032987.
- ^ Isaacs, R. (1975), "Familias infinitas de grafos trivalentes no triviales que no se pueden colorear con Tait", American Mathematical Monthly , 82 (3): 221-239, doi : 10.2307 / 2319844 , JSTOR 2319844.
- ^ Bonnington, C. Paul; Little, Charles HC (1995), Los fundamentos de la teoría de grafos topológicos , Springer-Verlag.
- ^ Bondy, JA y Murty, teoría de gráficos USR con aplicaciones. Nueva York: Holanda Septentrional, pág. 240, 1976.
- ^ Ellingham, MN "Gráficos de partitos cúbicos conectados 3 no hamiltonianos". Informe de investigación No. 28, Departamento de Matemáticas, Univ. Melbourne, Melbourne, 1981.
- ^ Ellingham, MN; Horton, JD (1983), "Gráficos bipartitos cúbicos conectados en 3 no hamiltonianos", Journal of Combinatorial Theory , Serie B, 34 (3): 350–353, doi : 10.1016 / 0095-8956 (83) 90046-1.
- ^ Robinson, RW; Wormald, NC (1994), "Casi todos los gráficos regulares son hamiltonianos", Estructuras y algoritmos aleatorios , 5 (2): 363–374, doi : 10.1002 / rsa.3240050209.
- ^ Eppstein, David (2007), "El problema del viajante de ventas para gráficas cúbicas" (PDF) , Journal of Graph Algorithms and Applications , 11 (1): 61–81, arXiv : cs.DS / 0302030 , doi : 10.7155 / jgaa. 00137.
- ^ Gebauer, H. (2008), "Sobre el número de ciclos de Hamilton en gráficos de grados acotados", Proc. 4o Taller de Algoritmia Analítica y Combinatoria (ANALCO '08) , doi : 10.1137 / 1.9781611972986.8.
- ^ a b Fomin, Fedor V .; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algoritmos", Information Processing Letters , 97 (5): 191-196, doi : 10.1016 / j.ipl.2005.10.012.
- ^ Petersen, Julius Peter Christian (1891), "Die Theorie der regulären Graphs (La teoría de los gráficos regulares)" , Acta Mathematica , 15 (15): 193–220, doi : 10.1007 / BF02392606 , S2CID 123779343.
- ^ Esperet, Louis; Kardoš, František; King, Andrew D .; Kráľ, Daniel ; Norine, Serguei (2011), "Exponencialmente muchos emparejamientos perfectos en gráficas cúbicas", Advances in Mathematics , 227 (4): 1646–1664, arXiv : 1012.2878 , doi : 10.1016 / j.aim.2011.03.015 , S2CID 4401537.
- ^ Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Un algoritmo exacto para TSP en gráficos de grado 3 mediante procedimiento de circuito y amortización en la estructura de conectividad", Teoría y aplicaciones de modelos de computación , Lecture Notes in Computer Science, 7876 , Springer-Verlag, págs. 96-107, arXiv : 1212.6831 , doi : 10.1007 / 978-3-642-38236-9_10 , ISBN 978-3-642-38236-9.
- ^ Xiao, Mingyu; Nagamochi, Hiroshi (2012), "Un algoritmo exacto para TSP en gráficos de grado 3 a través del procedimiento de circuito y amortización en la estructura de conectividad", Algorithmica , 74 (2): 713–741, arXiv : 1212.6831 , Bibcode : 2012arXiv1212.6831X , doi : 10.1007 / s00453-015-9970-4 , S2CID 7654681.
- ^ Alimonti, Paola; Kann, Viggo (2000), "Some APX-completeness results for cubic graphs", Theoretical Computer Science , 237 (1-2): 123-134, doi : 10.1016 / S0304-3975 (98) 00158-3.
- ^ Hliněný, Petr (2006), "El número de cruce es difícil para las gráficas cúbicas", Journal of Combinatorial Theory , Serie B, 96 (4): 455–471, doi : 10.1016 / j.jctb.2005.09.009.
- ^ Karpinski, Marek; Schmied, Richard (2013), Dureza aproximada del TSP gráfico en gráficos cúbicos , arXiv : 1304.6800 , Bibcode : 2013arXiv1304.6800K.
enlaces externos
- Royle, Gordon. "Gráficos simétricos cúbicos (el censo de Foster)" . Archivado desde el original el 23 de octubre de 2011.
- Weisstein, Eric W. "Gráfico bicúbico" . MathWorld .
- Weisstein, Eric W. "Gráfico cúbico" . MathWorld .