stringtranslate.com

Gráfica cúbica

El gráfico de Petersen es un gráfico cúbico.
El gráfico bipartito completo es un ejemplo de gráfico bicú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 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 .

Simetría

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]

Coloración y conjuntos independientes

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]

Topología y geometría

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.

Representación de una incrustación planar como un mapa codificado en gráficos

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]

Hamiltonicidad

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]

Otras propiedades

Problema sin resolver en matemáticas :
¿Cuál es el ancho de ruta más grande posible de un gráfico cúbico de vértices?

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 todo grafo cúbico sin puente tiene un emparejamiento perfecto . [14] Lovász y Plummer conjeturaron que todo grafo cúbico sin puente tiene un número exponencial de emparejamientos perfectos. La conjetura fue demostrada recientemente, mostrando que todo grafo cúbico sin puente 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 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]

Véase también

Referencias

  1. ^ 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.
  2. ^ Tutte, WT (1959), "Sobre la simetría de los grafos cúbicos", Can. J. Math. , 11 : 621–624, doi : 10.4153/CJM-1959-057-2 , S2CID  124273238, archivado desde el original el 2011-07-16 , consultado el 2010-07-21.
  3. ^ Bussemaker, FC; Cobeljic, S.; Cvetkovic, DM; Seidel, JJ (1976), Investigación informática de gráficos cúbicos, informe EUT, vol. 76-WSK-01, Departamento de Matemáticas y Ciencias de la Computación, Universidad Tecnológica de Eindhoven
  4. ^ Frucht, R. (1949), "Gráficos de grado tres con un grupo abstracto dado", Revista canadiense de matemáticas , 1 (4): 365–378, doi : 10.4153/CJM-1949-033-6 , ISSN  0008-414X, MR  0032987, S2CID  124723321.
  5. ^ Isaacs, R. (1975), "Familias infinitas de grafos trivalentes no triviales que no son coloreables por Tait", American Mathematical Monthly , 82 (3): 221–239, doi :10.2307/2319844, JSTOR  2319844.
  6. ^ Bonnington, C. Paul; Little, Charles HC (1995), Los fundamentos de la teoría de grafos topológicos , Springer-Verlag.
  7. ^ Bondy, JA y Murty, Teoría de grafos USR con aplicaciones. Nueva York: North Holland, pág. 240, 1976.
  8. ^ Ellingham, MN "Gráficos de partículas cúbicas 3-conectadas no hamiltonianas". Informe de investigación n.º 28, Departamento de Matemáticas, Universidad de Melbourne, Melbourne, 1981.
  9. ^ Ellingham, MN; Horton, JD (1983), "Gráficos bipartitos cúbicos 3-conexos no hamiltonianos", Journal of Combinatorial Theory , Serie B, 34 (3): 350–353, doi : 10.1016/0095-8956(83)90046-1.
  10. ^ Robinson, RW; Wormald, NC (1994), "Casi todos los gráficos regulares son hamiltonianos", Random Structures and Algorithms , 5 (2): 363–374, doi :10.1002/rsa.3240050209.
  11. ^ Eppstein, David (2007), "El problema del viajante de comercio para grafos cúbicos" (PDF) , Journal of Graph Algorithms and Applications , 11 (1): 61–81, arXiv : cs.DS/0302030 , doi :10.7155/jgaa.00137.
  12. ^ Gebauer, H. (2008), "Sobre el número de ciclos de Hamilton en grafos de grado acotado", Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), pp. 241–248, doi :10.1137/1.9781611972986.8, ISBN 9781611972986.
  13. ^ ab Fomin, Fedor V.; Høie, Kjartan (2006), "Ancho de ruta de gráficos cúbicos y algoritmos exactos", Information Processing Letters , 97 (5): 191–196, doi :10.1016/j.ipl.2005.10.012.
  14. ^ Petersen, Julius Peter Christian (1891), "Die Theorie der regulären Graphs (La teoría de los grafos regulares)", Acta Mathematica , 15 (15): 193–220, doi : 10.1007/BF02392606 , S2CID  123779343.
  15. ^ Esperet, Louis; Kardoš, František; Rey, Andrés D.; Kráľ, Daniel ; Norine, Serguei (2011), "Muchas coincidencias perfectas exponencialmente en gráficas cúbicas", Avances en Matemáticas , 227 (4): 1646–1664, arXiv : 1012.2878 , doi :10.1016/j.aim.2011.03.015, S2CID  4401537.
  16. ^ 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, vol. 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.
  17. ^ Xiao, Mingyu; Nagamochi, Hiroshi (2012), "Un algoritmo exacto para TSP en gráficos de grado 3 mediante 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.
  18. ^ Alimonti, Paola; Kann, Viggo (2000), "Algunos resultados de completitud APX para gráficos cúbicos", Theoretical Computer Science , 237 (1–2): 123–134, doi : 10.1016/S0304-3975(98)00158-3.
  19. ^ Hliněný, Petr (2006), "El cruce de números es difícil para los gráficos cúbicos", Journal of Combinatorial Theory , Serie B, 96 (4): 455–471, doi : 10.1016/j.jctb.2005.09.009.
  20. ^ Karpinski, Marek; Schmied, Richard (2013), Dureza de aproximación de TSP gráfico en gráficos cúbicos , arXiv : 1304.6800 , Bibcode :2013arXiv1304.6800K.

Enlaces externos