En la teoría de grafos geométricos , una rama de las matemáticas , un grafo poliédrico es el grafo no dirigido formado a partir de los vértices y aristas de un poliedro convexo . Alternativamente, en términos puramente teóricos de gráficos, los gráficos poliédricos son los gráficos planos conectados por 3 vértices .
Caracterización
El diagrama de Schlegel de un poliedro convexo representa sus vértices y aristas como puntos y segmentos de línea en el plano euclidiano , formando una subdivisión de un polígono convexo exterior en polígonos convexos más pequeños (un dibujo convexo de la gráfica del poliedro). No tiene cruces, por lo que cada gráfico poliédrico también es un gráfico plano . Además, según el teorema de Balinski , es un gráfico conectado a 3 vértices .
Según el teorema de Steinitz , estas dos propiedades de la teoría de los gráficos son suficientes para caracterizar completamente los gráficos poliédricos: son exactamente los gráficos planos conectados por 3 vértices. Es decir, siempre que un gráfico es tanto plano como conectado por 3 vértices, existe un poliedro cuyos vértices y aristas forman un gráfico isomorfo . [1] [2] Dado tal gráfico, se puede encontrar una representación del mismo como una subdivisión de un polígono convexo en polígonos convexos más pequeños utilizando la incrustación de Tutte . [3]
Hamiltonicidad y brevedad
Tait conjeturó que todo gráfico poliédrico cúbico (es decir, un gráfico poliédrico en el que cada vértice incide exactamente en tres aristas) tiene un ciclo hamiltoniano , pero esta conjetura fue refutada por un contraejemplo de WT Tutte , el gráfico poliédrico pero no hamiltoniano de Tutte . Si uno relaja el requisito de que el gráfico sea cúbico, hay gráficos poliédricos no hamiltonianos mucho más pequeños. El gráfico con la menor cantidad de vértices y aristas es el gráfico de Herschel de 11 vértices y 18 aristas , [4] y también existe un gráfico poliédrico no hamiltoniano de 11 vértices en el que todas las caras son triángulos, el gráfico de Goldner-Harary . [5]
Más fuertemente, existe una constante α <1 (el exponente de brevedad ) y una familia infinita de gráficos poliédricos de manera que la longitud del camino simple más largo de un gráfico de n -vértices en la familia es O ( n α ). [6] [7]
Enumeración combinatoria
Duijvestijn proporciona un recuento de los gráficos poliédricos con hasta 26 aristas; [8] El número de estos gráficos con 6, 7, 8, ... aristas es
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (secuencia A002840 en la OEIS ).
También se pueden enumerar los gráficos poliédricos por su número de vértices: para gráficos con 4, 5, 6, ... vértices, el número de gráficos poliédricos es
Casos especiales
Un gráfico poliédrico es el gráfico de un poliedro simple si es cúbico (cada vértice tiene tres aristas) y es el gráfico de un poliedro simplicial si es un gráfico plano máximo . Los gráficos de Halin , gráficos formados a partir de un árbol incrustado plano al agregar un ciclo externo que conecta todas las hojas del árbol, forman otra subclase importante de los gráficos poliédricos.
Referencias
- ^ Conferencias sobre politopos , por Günter M. Ziegler (1995) ISBN 0-387-94365-X , capítulo 4 "Teorema de Steinitz para 3-politopos", p.103.
- ^ Grünbaum, Branko (2003), Politopos convexos , Textos de posgrado en matemáticas , 221 (2a ed.), Springer-Verlag, ISBN 978-0-387-40409-7 CS1 maint: parámetro desalentado ( enlace ).
- ^ Tutte, WT (1963), "Cómo dibujar un gráfico", Proceedings of the London Mathematical Society , 13 : 743–767, doi : 10.1112 / plms / s3-13.1.743 , MR 0158387 CS1 maint: parámetro desalentado ( enlace ).
- ^ Weisstein, Eric W. "Gráfico de Herschel" . MathWorld ..
- ^ Weisstein, Eric W. "Gráfico de Goldner-Harary" . MathWorld ..
- ^ Weisstein, Eric W. "Exponente de la brevedad" . MathWorld ..
- ^ Grünbaum, Branko ; Motzkin, TS (1962), "Rutas simples más largas en gráficos poliédricos", Revista de la Sociedad Matemática de Londres , s1-37 (1): 152-160, doi : 10.1112 / jlms / s1-37.1.152.
- ^ Duijvestijn, AJW (1996), "El número de gráficos poliédricos (planos conectados de 3)" (PDF) , Matemáticas de la computación , 65 : 1289-1293, doi : 10.1090 / S0025-5718-96-00749-1.
enlaces externos
- Weisstein, Eric W. "Gráfico poliédrico" . MathWorld .