Polyedrický graf

Polyhedrální graf  je neorientovaný graf vytvořený z vrcholů a hran konvexního mnohostěnu nebo, v kontextu teorie grafů, rovinného grafu se 3 vrcholy .

Popis

Schlegelův diagram konvexního mnohostěnu představuje jeho vrcholy a hrany jako body a úsečky na euklidovské rovině , tvořící rozdělení vnějšího konvexního mnohoúhelníku na menší konvexní mnohoúhelníky. Diagram nemá žádné průsečíky, takže jakýkoli polyedrický graf je také rovinný . Také podle Balinského teorému je tento graf spojen s vrcholem 3 .

Podle Steinitzovy věty tyto dvě vlastnosti postačují ke kompletnímu popisu polyedrických grafů – jsou to přesně 3-vrcholově spojené rovinné grafy. Pokud je tedy graf rovinný i 3-vrcholově spojený, existuje mnohostěn, jehož vrcholy a hrany tvoří graf izomorfní k původnímu [1] [2] . Vzhledem k takovému grafu lze jeho znázornění jako rozdělení konvexního mnohoúhelníku na menší konvexní mnohoúhelníky nalézt pomocí Tuttova vložení [3] .

Hamiltonianity a shortness exponent

Tate se domníval , že jakýkoli kubický polyedrický graf (tj. polyedrický graf, ve kterém každý vrchol dopadá přesně na tři hrany) má hamiltonovský cyklus , ale tuto domněnku vyvrátil William Tutt , který zkonstruoval protipříklad – nehamiltonovský polyedrický graf. ( graf Tatta ). Povolíme-li podmínku, že graf musí být kubický, objeví se mnoho dalších menších nehamiltonských polyedrických grafů, jedním z nich s 11 vrcholy a 18 hranami je Herschelův graf [4] , existuje i nehamiltonovský polyedrický graf s 11 vrcholů, ve kterých jsou všechny plochy trojúhelníkové - Goldnerův graf - Harari [5] .

Přísně vzato, existuje konstanta ( exponent krátkosti[ upřesnit ] ) a nekonečnou rodinu polyedrických grafů takovou, že délka nejdelší jednoduché cesty grafu s vrcholy v rodině je [6] [7] .

Kombinační výčet

V roce 1996 byl stanoven počet polyedrických grafů do 26 hran [8] , konkrétně počet takových grafů s 6, 7, ..., 21 hranami je:

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

Polyedrické grafy můžete také vyčíslit počtem jejich vrcholů, počet takových grafů je:

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

Zvláštní příležitosti

Polyhedrální graf je jednoduchý polytopový graf, pokud je kubický (tři hrany se sbíhají v každém vrcholu), a je to jednoduchý polytopový graf, pokud je maximální rovinný graf . Halinovy ​​grafy , vytvořené z rovinných stromů přidáním vnější smyčky přes všechny listy stromu, tvoří další důležitou podtřídu polyhedrálních grafů.

Poznámky

  1. ↑ Günter M. Ziegler. Přednášky o Polytopech. - 1995. - S. 103, Kapitola 4 "Steinitzova věta pro 3-polytopy". — ISBN 0-387-94365-X .
  2. ↑ Branko Grünbaum. Konvexní polytopy. - Springer-Verlag, 2003. - Vol. 221. - (Absolventské texty z matematiky). - ISBN 978-0-387-40409-7 .
  3. ↑ WT Tutte. Jak nakreslit graf // Proceedings of the London Mathematical Society. - 1963. - T. 13 . — S. 743–767 . - doi : 10.1112/plms/s3-13.1.743 .
  4. ↑ Weisstein, Eric W. Herschel Graph  na webu Wolfram MathWorld .
  5. ↑ Weisstein, Eric W. Goldner-Harary Graph  na webu Wolfram MathWorld .
  6. ↑ Weisstein, Eric W. Shortness Exponent  na webu Wolfram MathWorld .
  7. ↑ Branko Grünbaum, TS Motzkin. Nejdelší jednoduché cesty v polyhedrálních grafech // Journal of the London Mathematical Society. - 1962. - T. s1-37 , čís. 1 . — S. 152–160 . - doi : 10.1112/jlms/s1-37.1.152 .
  8. ↑ AJW Duijvestijn. Počet polyedrických (3-spojených rovinných) grafů  // Matematika počítání. - 1996. - T. 65 . - S. 1289-1293 . - doi : 10.1090/S0025-5718-96-00749-1 . Archivováno z originálu 17. února 2019.
  9. ↑ OEIS sekvence A002840 _
  10. ↑ OEIS sekvence A000944 _

Odkazy