Polyedrisk graf
I geometrisk grafteori , en gren av matematiken , är en polyedrisk graf den oriktade grafen som bildas av hörn och kanter av en konvex polyeder . Alternativt, i rent grafteoretiska termer, är de polyedriska graferna de 3-vertex-anslutna , plana graferna .
Karakterisering
Schlegel- diagrammet av en konvex polyeder representerar dess hörn och kanter som pekar och linjesegment i det euklidiska planet och bildar en underavdelning av en yttre konvex polygon i mindre konvexa polygoner (en konvex teckning av polyederns graf). Den har inga korsningar, så varje polyedrisk graf är också en plan graf . Dessutom, enligt Balinskis sats , är det en 3-vertex-kopplad graf .
Enligt Steinitzs sats räcker dessa två grafteoretiska egenskaper för att helt karakterisera de polyedriska graferna: de är exakt de plana graferna som är sammankopplade med 3 vertex. Det vill säga, närhelst en graf är både plan och 3-vertex-kopplad, finns det en polyeder vars hörn och kanter bildar en isomorf graf. Med tanke på en sådan graf kan en representation av den som en underavdelning av en konvex polygon i mindre konvexa polygoner hittas med hjälp av Tutte-inbäddningen .
Hamiltonicitet och korthet
Tait antog 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 motbevisades av ett motexempel på WT Tutte , den polyedriska men icke- hamiltonska Tutte-grafen . Om man lättar på kravet att grafen ska vara kubisk, finns det mycket mindre icke-hamiltonska polyedriska grafer. Grafen med minst hörn och kanter är Herschel-grafen med 11 och 18 kanter , och det finns också en icke-Hamiltonisk polyedrisk graf med 11 hörn där alla ytor är trianglar, Goldner -Harary-grafen .
Mer starkt, det finns en konstant ( korthetsexponenten ) och en oändlig familj av polyedriska grafer så att längden på den längsta enkla vägen för en -vertexgraf i familjen är .
Kombinatorisk uppräkning
Duijvestijn ger en räkning av de polyedriska graferna med upp till 26 kanter; Antalet av dessa grafer med 6, 7, 8, ... kanter är
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (sekvens A002840 i OEIS ) .
Man kan också räkna upp de polyedriska graferna efter deras antal hörn: för grafer med 4, 5, 6, ... hörn är antalet polyedriska grafer
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... (sekvens A000944 i OEIS ).
Speciella fall
En polyedergraf är grafen för en enkel polyeder om den är kubisk (varje vertex har tre kanter), och det är grafen för en enkel polyeder om det är en maximal plan graf . Halin -graferna , grafer bildade från ett plant inbäddat träd genom att lägga till en yttre cykel som förbinder alla trädets löv, bildar en annan viktig underklass av de polyedriska graferna.