Polyedrischer Graph - Polyhedral graph
In der geometrischen Graphentheorie , einem Zweig der Mathematik , ist ein polyedrischer Graph der ungerichtete Graph , der aus den Eckpunkten und Kanten eines konvexen Polyeders gebildet wird . In rein graphentheoretischen Begriffen sind die polyedrischen Graphen alternativ die mit 3 Scheitelpunkten verbundenen planaren Graphen .
Charakterisierung
Das Schlegel-Diagramm eines konvexen Polyeders stellt seine Eckpunkte und Kanten als Punkte und Liniensegmente in der euklidischen Ebene dar und bildet eine Unterteilung eines äußeren konvexen Polygons in kleinere konvexe Polygone (eine konvexe Zeichnung des Graphen des Polyeders). Es hat keine Kreuzungen, daher ist jeder polyedrische Graph auch ein planarer Graph . Nach Balinskis Theorem handelt es sich außerdem um einen mit drei Scheitelpunkten verbundenen Graphen .
Nach dem Satz von Steinitz reichen diese beiden graphentheoretischen Eigenschaften aus, um die polyedrischen Graphen vollständig zu charakterisieren : Sie sind genau die mit drei Scheitelpunkten verbundenen planaren Graphen. Das heißt, wenn ein Graph sowohl planar als auch mit 3 Scheitelpunkten verbunden ist, existiert ein Polyeder, dessen Scheitelpunkte und Kanten einen isomorphen Graphen bilden. Bei einem solchen Graphen kann eine Darstellung als Unterteilung eines konvexen Polygons in kleinere konvexe Polygone unter Verwendung der Tutte-Einbettung gefunden werden .
Hamiltonizität und Kürze
Tait vermutete, dass jeder kubische polyedrische Graph (dh ein polyedrischer Graph, bei dem jeder Scheitelpunkt auf genau drei Kanten fällt) einen Hamilton-Zyklus hat , aber diese Vermutung wurde durch ein Gegenbeispiel von WT Tutte , dem polyedrischen, aber nicht-Hamiltonschen Tutte-Graphen, widerlegt . Wenn man die Anforderung lockert, dass der Graph kubisch sein muss, gibt es viel kleinere nicht-Hamiltonsche polyedrische Graphen. Der Graph mit den wenigsten Scheitelpunkten und Kanten ist der Herschel-Graph mit 11 und 18 Scheitelpunkten , und es gibt auch einen nicht-Hamiltonschen polyedrischen Graphen mit 11 Scheitelpunkten, in dem alle Flächen Dreiecke sind, den Goldner-Harary-Graphen .
Stärker existiert eine Konstante α <1 (der Kurzheitsexponent ) und eine unendliche Familie polyedrischer Graphen, so dass die Länge des längsten einfachen Pfades eines n- Vertex-Graphen in der Familie O ( n α ) beträgt .
Kombinatorische Aufzählung
Duijvestijn liefert eine Zählung der polyedrischen Graphen mit bis zu 26 Kanten; Die Anzahl dieser Diagramme mit 6, 7, 8, ... Kanten beträgt
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (Sequenz A002840 im OEIS ).
Man kann die polyedrischen Graphen auch nach ihrer Anzahl von Eckpunkten aufzählen : Für Graphen mit 4, 5, 6, ... Eckpunkten ist die Anzahl der polyedrischen Graphen
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... (Sequenz A000944 im OEIS ).
Sonderfälle
Ein polyedrischer Graph ist der Graph eines einfachen Polyeders, wenn er kubisch ist (jeder Scheitelpunkt hat drei Kanten), und er ist der Graph eines einfachen Polyeders, wenn es sich um einen maximalen planaren Graphen handelt . Die Halin-Graphen , Graphen, die aus einem planar eingebetteten Baum durch Hinzufügen eines äußeren Zyklus gebildet werden, der alle Blätter des Baums verbindet, bilden eine weitere wichtige Unterklasse der polyedrischen Graphen.
