Polyedrisk graf

En polyedrisk graf  är en oriktad graf som bildas av hörn och kanter av en konvex polyeder , eller, i samband med grafteori, en 3-vertex-ansluten plan graf .

Beskrivning

Schlegel-diagrammet av en konvex polyeder representerar dess hörn och kanter som pekar och linjesegment på det euklidiska planet och bildar en uppdelning av den yttre konvexa polygonen till mindre konvexa polygoner. Diagrammet har inga självskärningar, så alla polyedriska grafer är också plana . Dessutom, genom Balinskys sats , är denna graf vertex-3-ansluten .

Enligt Steinitz sats är dessa två egenskaper tillräckliga för att fullständigt beskriva polyedriska grafer – de är exakt 3-vertex-kopplade plana grafer. Således, om grafen är både plan och 3-vertex-kopplad, finns det en polyeder vars hörn och kanter bildar en graf som är isomorf till den ursprungliga [1] [2] . Givet en sådan graf kan en representation av den som en partition av en konvex polygon i mindre konvexa polygoner hittas med hjälp av Tuttas inbäddning [3] .

Hamiltonianitet och korthetsexponent

Tate förmodade att varje kubisk polyedrisk graf (det vill säga en polyedrisk graf där varje vertex faller in mot exakt tre kanter) har en Hamiltonsk cykel , men denna gissning vederlagdes av William Tutt , som konstruerade ett motexempel - en icke-Hamiltonsk polyedrisk graf ( Tatta graf ). Om vi ​​släpper på villkoret att grafen måste vara kubisk kommer många andra mindre icke-Hamiltonska polyedriska grafer att dyka upp, en av dem med 11 hörn och 18 kanter är Herschel-grafen [4] , det finns även en icke-Hamiltonsk polyedrisk graf med 11 hörn, där alla ansikten triangulära - Goldner graf - Harari [5] .

Strängt taget finns det en konstant ( korthetsexponent[ förfina ] ) och en oändlig familj av polyedriska grafer så att längden på den längsta enkla vägen för en graf med hörn i familjen är [6] [7] .

Kombinatorisk uppräkning

1996 bestämdes antalet polyedriska grafer med upp till 26 kanter [8] , i synnerhet är antalet sådana grafer med 6, 7, ..., 21 kanter:

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

Du kan också räkna upp polyedriska grafer efter antalet hörn, antalet sådana grafer är:

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

Särskilda tillfällen

En polyedrisk graf är en enkel polytopgraf om den är kubisk (tre kanter konvergerar vid varje vertex), och det är en enkel polytopgraf om det är en maximal plan graf . Halin-grafer , bildade av plana träd genom att lägga till en yttre slinga genom alla trädets löv, bildar en annan viktig underklass av polyedriska grafer.

Anteckningar

  1. ↑ Günter M. Ziegler. Föreläsningar om polytoper. - 1995. - S. 103, kapitel 4 "Steinitz' sats för 3-polytoper". — ISBN 0-387-94365-X .
  2. ↑ Branko Grünbaum. Konvexa polytoper. - Springer-Verlag, 2003. - Vol. 221. - (Examinerade texter i matematik). - ISBN 978-0-387-40409-7 .
  3. ↑ WT Tutte. Hur man ritar en 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 Graf  på Wolfram MathWorld- webbplatsen .
  5. ↑ Weisstein, Eric W. Goldner-Harary Graph  på Wolfram MathWorld -webbplatsen .
  6. ↑ Weisstein, Eric W. Shortness Exponent  på Wolfram MathWorld- webbplatsen .
  7. ↑ Branko Grünbaum, TS Motzkin. Längsta enkla vägar i polyedriska grafer // Journal of the London Mathematical Society. - 1962. - T. s1-37 , nr. 1 . — S. 152–160 . - doi : 10.1112/jlms/s1-37.1.152 .
  8. ↑ AJW Duijvestijn. Antalet polyedriska (3-kopplade plana) grafer  // Mathematics of Computation. - 1996. - T. 65 . - S. 1289-1293 . - doi : 10.1090/S0025-5718-96-00749-1 . Arkiverad från originalet den 17 februari 2019.
  9. ↑ OEIS - sekvens A002840 _
  10. ↑ OEIS - sekvens A000944 _

Länkar