En la teoría de grafos geométricos , una rama de las matemáticas , un gráfico poliédrico es el gráfico no dirigido formado a partir de los vértices y aristas de un poliedro convexo . Alternativamente, en términos puramente teóricos de grafos, los gráficos poliédricos son los gráficos planos conectados con 3 vértices .
El diagrama de Schlegel de un poliedro convexo representa sus vértices y aristas como puntos y segmentos de recta 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 todo grafo poliédrico también es un grafo plano . Además, según el teorema de Balinski , es un gráfico conectado de 3 vértices .
Según el teorema de Steinitz , estas dos propiedades de la teoría de grafos son suficientes para caracterizar completamente los grafos poliédricos: son exactamente los grafos planos conectados por tres vértices. Es decir, siempre que un gráfico es plano y está conectado por 3 vértices, existe un poliedro cuyos vértices y aristas forman un gráfico isomorfo . [1] [2] Dado un gráfico de este tipo, 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]
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 de Tutte poliédrico pero no hamiltoniano. . Si se relaja el requisito de que la gráfica sea cúbica, hay gráficas poliédricas no hamiltonianas mucho más pequeñas. 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 (el exponente de brevedad ) y una familia infinita de gráficos poliédricos tal que la longitud del camino simple más largo de un gráfico de vértice en la familia es . [6] [7]
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
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
Las gráficas de los sólidos platónicos han sido denominadas gráficas platónicas . Además de tener todas las demás propiedades de los gráficos poliédricos, estos son gráficos simétricos y todos tienen ciclos hamiltonianos . [9] Hay cinco de estos gráficos:
Una gráfica poliédrica es la gráfica de un poliedro simple si es cúbico (cada vértice tiene tres aristas), y es la gráfica de un poliedro simplicial si es una gráfica plana máxima . Por ejemplo, las gráficas tetraédrica, cúbica y dodecaédrica son simples; las gráficas tetraédrica, octaédrica e icosaédrica son simples.
Los gráficos de Halin , gráficos formados a partir de un árbol incrustado plano agregando un ciclo externo que conecta todas las hojas del árbol, forman otra subclase importante de los gráficos poliédricos.
