Gráfico poliédrico

Un gráfico poliédrico  es un gráfico no dirigido formado por los vértices y las aristas de un poliedro convexo o, en el contexto de la teoría de gráficos, un gráfico plano conectado por 3 vértices .

Descripció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 partición del polígono convexo exterior en polígonos convexos más pequeños. El diagrama no tiene autointersecciones, por lo que cualquier gráfico poliédrico también es plano . Además, por el teorema de Balinsky , este grafo está conectado por 3 vértices .

De acuerdo con el teorema de Steinitz, estas dos propiedades son suficientes para describir completamente los gráficos poliédricos: son exactamente gráficos planos conectados por 3 vértices. Así, si el grafo es tanto plano como conectado por 3 vértices, existe un poliedro cuyos vértices y aristas forman un grafo isomorfo al original [1] [2] . Dado un gráfico de este tipo, se puede encontrar una representación del mismo como una partición de un polígono convexo en polígonos convexos más pequeños utilizando la incrustación de Tutta [3] .

Exponente de hamiltonianidad y brevedad

Tate conjeturó que cualquier 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 William Tutt , quien construyó un contraejemplo: un gráfico poliédrico no hamiltoniano. ( Gráfico Tatta ). Si relajamos la condición de que el gráfico debe ser cúbico, aparecerán muchos otros gráficos poliédricos no hamiltonianos más pequeños, uno de ellos con 11 vértices y 18 aristas es el gráfico de Herschel [4] , también hay un gráfico poliédrico no hamiltoniano con 11 vértices, en los que todas las caras son triangulares - Gráfico de Goldner - Harari [5] .

Estrictamente hablando, existe una constante ( exponente de brevedad[ refinar ] ) y una familia infinita de gráficos poliédricos tal que la longitud del camino simple más largo de un gráfico con vértices en la familia es [6] [7] .

Enumeración combinatoria

En 1996, se determinó el número de grafos poliédricos con hasta 26 aristas [8] , en particular, el número de dichos grafos con 6, 7, ..., 21 aristas es:

1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810 [9] .

También puede enumerar gráficos poliédricos por el número de sus vértices, el número de dichos gráficos es:

1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, … [10] .

Ocasiones especiales

Un grafo poliédrico es un grafo politópico simple si es cúbico (tres aristas convergen en cada vértice), y es un grafo politópico simplicial si es un grafo plano maximal . Los gráficos de Halin , formados a partir de árboles planos al agregar un bucle externo a través de todas las hojas del árbol, forman otra subclase importante de gráficos poliédricos.

Notas

  1. ↑ Günter M. Ziegler. Conferencias sobre politopos. - 1995. - Pág. 103, Capítulo 4 "Teorema de Steinitz para 3-Poliotopos". — ISBN 0-387-94365-X .
  2. ↑ Branko Grünbaum. Politopos convexos. - Springer-Verlag, 2003. - Vol. 221. - (Textos de Grado en Matemáticas). - ISBN 978-0-387-40409-7 .
  3. ↑ WT Tutte. Cómo dibujar un gráfico // Actas de la London Mathematical Society. - 1963. - T. 13 . — S. 743–767 . -doi : 10.1112 / plms/s3-13.1.743 .
  4. ↑ Weisstein, Eric W. Herschel Graph  en el sitio web de Wolfram MathWorld .
  5. ↑ Weisstein, Eric W. Goldner-Harary Gráfico  en el sitio web Wolfram MathWorld .
  6. ↑ Weisstein, Eric W. Shortness Exponent  en el sitio web de Wolfram MathWorld .
  7. ↑ Branko Grünbaum, TS Motzkin. Caminos simples más largos en gráficos poliédricos // Revista de la Sociedad Matemática de Londres. - 1962. - T. s1-37 , núm. 1 . — S. 152–160 . -doi : 10.1112 / jlms/s1-37.1.152 .
  8. ↑ AJW Duijvestijn. El número de gráficos poliédricos (planares de 3 conexiones)  // Matemáticas de computación. - 1996. - T. 65 . - S. 1289-1293 . -doi : 10.1090/ S0025-5718-96-00749-1 . Archivado desde el original el 17 de febrero de 2019.
  9. ↑ Secuencia OEIS A002840 _
  10. ↑ Secuencia OEIS A000944 _

Enlaces