Planarer Graph Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph der auf einer Ebene mit Punkten fü
Planarer Graph
Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph, der auf einer Ebene, mit Punkten für die Knoten und Linien für die Kanten, dargestellt werden kann, sodass sich keine Kanten schneiden.
Planare Zeichnung des
DefinitionBearbeiten
Ein Graph heißt planar oder plättbar, wenn er eine Einbettung in die Ebene besitzt; das heißt, er kann in der Ebene gezeichnet werden, so dass seine Kanten durch Jordan-Kurven repräsentiert werden, welche sich nur in gemeinsamen Endpunkten schneiden. Die Einbettung (auch Zeichnung) des Graphen ist ein ebener Graph. Nach dem Satz von Wagner und Fáry existiert für jeden planaren Graphen auch eine Einbettung, in welcher seine Kanten als Strecken dargestellt sind.
Durch die Einbettung wird die Ebene in zusammenhängende Gebiete oder Flächen geteilt, die von den Kanten des Graphen begrenzt werden. Die begrenzenden Kanten eines Gebietes bilden seinen Rand. Das unbeschränkte Gebiet um den Graphen herum wird äußeres Gebiet oder äußere Fläche genannt. Zwei Einbettungen heißen äquivalent, wenn es eine isomorphe Abbildung zwischen den Rändern ihrer Gebiete gibt.
Verwandte BegriffsbildungenBearbeiten
Beispiel eines außerplanaren Graphen; links planare Einbettung, rechts planare Einbettung, in der alle Knoten auf dem äußeren Gebiet liegen
Ein Graph heißt maximal planar oder Dreiecksgraph, wenn er planar ist und ihm keine Kante hinzugefügt werden kann, ohne dass dadurch seine Planarität verloren geht.
Ein Graph heißt fast planar oder kritisch planar, wenn der Graph durch Entfernen eines beliebigen Knotens planar wird. Beispiel: K5 ist fast planar.
Ein Graph heißt außerplanar (oft auch außenplanar oder kreisartig planar), wenn er sich so in die Ebene einbetten lässt, dass alle seine Knoten auf dem Rand ein und desselben Gebiets liegen.
Aus dem Eulerschen Polyedersatz ergibt sich, dass die Gebietsanzahl jeder Einbettung dieselbe ist.
Für einen planaren Graphen ohne Schleifen und Mehrfachkanten ergibt sich aus dem Polyedersatz die Abschätzung . Dies lässt sich für dreiecksfreie Graphen mit mindestens 3 Knoten noch auf die folgende Ungleichung verbessern:
Ist ein planarer Graph 3-fach zusammenhängend, so sind alle seine Einbettungen (bis auf eine globale Umorientierung) äquivalent.
Ein planarer Graph mit Knoten ist genau dann maximal planar, wenn er Kanten hat.
Ein planarer Graph kann höchstens 5-fach zusammenhängend sein und es gibt immer einen Knoten mit Knotengrad höchstens 5.
Nach dem Koebe-Andreev-Thurston-Theorem existiert für jeden planaren Graphen eine assoziierte Kreispackung, deren Kontaktgraph isomorph zum Ursprungsgraph ist.
In einem endlichen zusammenhängenden einfachen planaren Graphen wird jede Fläche von mindestens drei Kanten begrenzt, und jede Kante berührt höchstens zwei Flächen. Mit dem Polyedersatz kann man zeigen, dass für diese Graphen gilt:
Der Polyedersatz gilt auch für konvexe Polyeder. Dies ist kein Zufall: Jedes konvexe Polyeder kann mithilfe des Schlegeldiagramms des Polyeders, einer Zentralprojektion des Polyeders auf eine Ebene, deren Projektionszentrum nahe dem Zentrum einer Seitenfläche des Polyeders liegt, in einen zusammenhängenden einfachen planaren Graphen umgewandelt werden. Nicht jeder planare Graph entspricht auf diese Weise einem konvexen Polyeder: Die Bäume zum Beispiel nicht.
Der Satz von Steinitz besagt, dass die aus konvexen Polyedern gebildeten Graphen genau die endlichen 3-fach zusammenhängenden einfachen planaren Graphen sind. Im Allgemeinen gilt der Polyedersatz für jedes Polyeder, dessen Flächen einfache Polygone sind, die unabhängig von ihrer Konvexität eine Oberfläche bilden, die topologisch äquivalent zu einer Kugel sind.
Durchschnittlicher KnotengradBearbeiten
Zusammenhängende planare Graphen mit mehr als einer Kante erfüllen die Ungleichung, weil jede Fläche benachbart zu mindestens drei Kanten und jede Kante genau zwei Flächen begrenzt. Aus der Ungleichung folgt für den durchschnittlichen Knotengrad
Das heißt, dass für endliche planare Graphen der durchschnittliche Knotengrad kleiner als 6 ist. Graphen mit höherem durchschnittlichen Knotengrad können nicht planar sein.
Planare GraphendichteBearbeiten
Die Dichte eines planaren Graphen oder Netzwerks ist definiert als ein Verhältnis der Anzahl der Kanten zur Anzahl der maximal möglichen Kanten in einem Netzwerk mit Knoten, gegeben durch einen planaren Graphen mit :
Ein zusammenhängender planarer Graph mit minimaler Anzahl von Kanten, also ein Baum, hat eine Kante weniger als Knoten, also ist und . Für einen zusammenhängenden planaren Graphen mit maximaler Anzahl von Kanten ist .
Anzahl der planaren Graphen ohne nummerierte Knoten
n
alle
zusammenhängend
1
1
1
2
2
1
3
4
2
4
11
6
5
33
20
6
142
99
7
822
646
8
6966
5974
9
79853
71885
10
1140916
1052805
11
18681008
17449299
12
333312451
313372298
Duale GraphenBearbeiten
Die roten Graphen sind jeweils dual zu den zueinander isomorphen blauen Graphen, aber selbst nicht isomorph zueinander. Die blauen Graphen sind verschiedene Einbettungen von isomorphen Graphen.Dodekaedergraph mit dualem Ikosaedergraph
Jeder planare Graph hat einen dualen Graphen. Das ist ein Graph, wo jeder Fläche des Graphen ein Knoten zugeordnet ist, der innerhalb dieser Fläche liegt, und umgekehrt, und jeder Kante eine Kante zugeordnet ist, die die beiden Flächen trennt, die den Endknoten der Kante des ursprünglichen Graphen zugeordnet sind, und die beiden Knoten verbindet, die den benachbarten Flächen der Kante des ursprünglichen Graphen zugeordnet sind. Die dualen Kanten schneiden also jeweils die ursprünglichen Kanten. In den Abbildungen sind die ursprünglichen Graphen blau und die dualen Graphen rot gefärbt.
Ist der Graph nicht nur planar, sondern auch zusammenhängend, so gilt, dass die Anzahl der Knoten des dualen Graphen der Anzahl der Flächen des ursprünglichen Graphen entspricht und umgekehrt, und die Anzahl der Kanten bleibt konstant. Im zusammenhängenden Fall gibt es damit bijektive Abbildungen zwischen den Kantenmengen der beiden Graphen und jeweils der Mengen der Knoten und der Menge der Flächen.
Der Begriff dual wird verwendet, weil die Eigenschaft, ein dualer Graph zu sein, gegenseitig ist, was bedeutet, dass ein dualer Graph von ist, wenn ein dualer Graph eines zusammenhängenden Graphen ist. Zu planaren Graphen kann es im Allgemeinen mehrere duale Graphen geben, abhängig von der Wahl der planaren Einbettung des Graphen.
VerwendungBearbeiten
Die Untersuchung der Planarität von Graphen gehört zu den klassischen Themengebieten der Graphentheorie und wird auch oftmals als starke Voraussetzung für Sätze verwendet. So besagt der Vier-Farben-Satz, dass sich planare Graphen mit 4 Farben färben lassen. Dreiecksfreie planare Graphen sind 3-färbbar.
Ein planarer oder plattbarer Graph ist in der Graphentheorie ein Graph der auf einer Ebene mit Punkten fur die Knoten und Linien fur die Kanten dargestellt werden kann sodass sich keine Kanten schneiden Planare Zeichnung des K 4 displaystyle K 4 Inhaltsverzeichnis 1 Definition 2 Verwandte Begriffsbildungen 3 Eigenschaften 3 1 Der Eulerscher Polyedersatz 3 2 Durchschnittlicher Knotengrad 3 3 Planare Graphendichte 4 Kombinatorik 5 Duale Graphen 6 Verwendung 7 Literatur 8 EinzelnachweiseDefinition BearbeitenEin Graph G V E displaystyle G V E nbsp heisst planar oder plattbar wenn er eine Einbettung in die Ebene besitzt das heisst er kann in der Ebene gezeichnet werden so dass seine Kanten durch Jordan Kurven reprasentiert werden welche sich nur in gemeinsamen Endpunkten schneiden Die Einbettung auch Zeichnung des Graphen ist ein ebener Graph Nach dem Satz von Wagner und Fary existiert fur jeden planaren Graphen auch eine Einbettung in welcher seine Kanten als Strecken dargestellt sind Durch die Einbettung wird die Ebene in zusammenhangende Gebiete oder Flachen geteilt die von den Kanten des Graphen begrenzt werden Die begrenzenden Kanten eines Gebietes bilden seinen Rand Das unbeschrankte Gebiet um den Graphen herum wird ausseres Gebiet oder aussere Flache genannt Zwei Einbettungen heissen aquivalent wenn es eine isomorphe Abbildung zwischen den Randern ihrer Gebiete gibt Verwandte Begriffsbildungen Bearbeiten nbsp Beispiel eines ausserplanaren Graphen links planare Einbettung rechts planare Einbettung in der alle Knoten auf dem ausseren Gebiet liegenEin Graph heisst maximal planar oder Dreiecksgraph wenn er planar ist und ihm keine Kante hinzugefugt werden kann ohne dass dadurch seine Planaritat verloren geht Ein Graph heisst fast planar oder kritisch planar wenn der Graph durch Entfernen eines beliebigen Knotens planar wird Beispiel K5 ist fast planar Ein Graph heisst ausserplanar oft auch aussenplanar oder kreisartig planar wenn er sich so in die Ebene einbetten lasst dass alle seine Knoten auf dem Rand ein und desselben Gebiets liegen Eigenschaften Bearbeiten nbsp Animation Der Petersen Graph enthalt den vollstandig bipartiten Graphen K 3 3 displaystyle K 3 3 nbsp als Minor und ist deshalb nicht planar Der Satz von Kuratowski gibt eine nicht geometrische Charakterisierung von planaren Graphen Er besagt dass ein Graph genau dann planar ist wenn er keinen Teilgraphen besitzt der ein Unterteilungsgraph des vollstandigen Graphen K 5 displaystyle K 5 nbsp oder des vollstandig bipartiten Graphen K 3 3 displaystyle K 3 3 nbsp ist Einen Unterteilungsgraph erhalt man indem man wiederholt eine Kante durch ein inzidentes Kantenpaar ersetzt Alternativ kann man formulieren dass ein Graph genau dann planar ist wenn er weder den K 5 displaystyle K 5 nbsp noch den K 3 3 displaystyle K 3 3 nbsp als Minor enthalt Aus dem Eulerschen Polyedersatz ergibt sich dass die Gebietsanzahl jeder Einbettung dieselbe ist Fur einen planaren Graphen ohne Schleifen und Mehrfachkanten ergibt sich aus dem Polyedersatz die Abschatzung E 3 V 6 displaystyle E leq 3 cdot V 6 nbsp Dies lasst sich fur dreiecksfreie Graphen mit mindestens 3 Knoten noch auf die folgende Ungleichung verbessern E 2 V 4 displaystyle E leq 2 cdot V 4 nbsp Ist ein planarer Graph 3 fach zusammenhangend so sind alle seine Einbettungen bis auf eine globale Umorientierung aquivalent Ein planarer Graph mit n 3 displaystyle n geq 3 nbsp Knoten ist genau dann maximal planar wenn er 3 n 6 displaystyle 3 cdot n 6 nbsp Kanten hat Ein planarer Graph kann hochstens 5 fach zusammenhangend sein und es gibt immer einen Knoten mit Knotengrad hochstens 5 Nach dem Koebe Andreev Thurston Theorem existiert fur jeden planaren Graphen eine assoziierte Kreispackung deren Kontaktgraph isomorph zum Ursprungsgraph ist Die Planaritat eines Graphen lasst sich mit verschiedenen Algorithmen in linearer Laufzeit testen Der Eulerscher Polyedersatz Bearbeiten Der Eulersche Polyedersatz besagt dass jeder endliche zusammenhangende planare Graph mit V displaystyle V nbsp Knoten E displaystyle E nbsp Kanten und F displaystyle F nbsp Flachen folgende Gleichung erfullt V E F 2 displaystyle V E F 2 nbsp In einem endlichen zusammenhangenden einfachen planaren Graphen wird jede Flache von mindestens drei Kanten begrenzt und jede Kante beruhrt hochstens zwei Flachen Mit dem Polyedersatz kann man zeigen dass fur diese Graphen gilt E 3 V 6 displaystyle E leq 3 cdot V 6 nbsp Der Polyedersatz gilt auch fur konvexe Polyeder Dies ist kein Zufall Jedes konvexe Polyeder kann mithilfe des Schlegeldiagramms des Polyeders einer Zentralprojektion des Polyeders auf eine Ebene deren Projektionszentrum nahe dem Zentrum einer Seitenflache des Polyeders liegt in einen zusammenhangenden einfachen planaren Graphen umgewandelt werden Nicht jeder planare Graph entspricht auf diese Weise einem konvexen Polyeder Die Baume zum Beispiel nicht Der Satz von Steinitz besagt dass die aus konvexen Polyedern gebildeten Graphen genau die endlichen 3 fach zusammenhangenden einfachen planaren Graphen sind Im Allgemeinen gilt der Polyedersatz fur jedes Polyeder dessen Flachen einfache Polygone sind die unabhangig von ihrer Konvexitat eine Oberflache bilden die topologisch aquivalent zu einer Kugel sind Durchschnittlicher Knotengrad Bearbeiten Zusammenhangende planare Graphen mit mehr als einer Kante erfullen die Ungleichung 2 E 3 F displaystyle 2 cdot E geq 3 cdot F nbsp weil jede Flache benachbart zu mindestens drei Kanten und jede Kante genau zwei Flachen begrenzt Aus der Ungleichung E 3 V 6 displaystyle E leq 3 cdot V 6 nbsp folgt fur den durchschnittlichen Knotengrad v V d G v V 2 E V 2 3 V 6 V 6 V 12 V lt 6 displaystyle frac sum v in V d G v V frac 2 cdot E V leq frac 2 cdot 3 cdot V 6 V frac 6 cdot V 12 V lt 6 nbsp Das heisst dass fur endliche planare Graphen der durchschnittliche Knotengrad kleiner als 6 ist Graphen mit hoherem durchschnittlichen Knotengrad konnen nicht planar sein Planare Graphendichte Bearbeiten Die Dichte D displaystyle D nbsp eines planaren Graphen oder Netzwerks ist definiert als ein Verhaltnis der Anzahl der Kanten E displaystyle E nbsp zur Anzahl der maximal moglichen Kanten in einem Netzwerk mit V displaystyle V nbsp Knoten gegeben durch einen planaren Graphen mit E 3 V 6 displaystyle E 3 cdot V 6 nbsp D E V 1 2 V 5 displaystyle D frac E V 1 2 cdot V 5 nbsp Ein zusammenhangender planarer Graph mit minimaler Anzahl von Kanten also ein Baum hat eine Kante weniger als Knoten also ist E V 1 displaystyle E V 1 nbsp und D 0 displaystyle D 0 nbsp Fur einen zusammenhangenden planaren Graphen mit maximaler Anzahl von Kanten ist D 1 displaystyle D 1 nbsp Kombinatorik BearbeitenDie Anzahl der einfachen planaren Graphen ohne nummerierte Knoten steigt schneller als exponentiell mit der Anzahl n displaystyle n nbsp der Knoten Die folgende Tabelle zeigt die mit Hilfe eines Computers bestimmten Anzahlen fur n 12 displaystyle n leq 12 nbsp 1 2 Anzahl der planaren Graphen ohne nummerierte Knotenn alle zusammenhangend1 1 12 2 13 4 24 11 65 33 206 142 997 822 6468 6966 59749 79853 7188510 1140916 105280511 18681008 1744929912 333312451 313372298Duale Graphen Bearbeiten nbsp Die roten Graphen sind jeweils dual zu den zueinander isomorphen blauen Graphen aber selbst nicht isomorph zueinander Die blauen Graphen sind verschiedene Einbettungen von isomorphen Graphen nbsp Dodekaedergraph mit dualem IkosaedergraphJeder planare Graph hat einen dualen Graphen Das ist ein Graph wo jeder Flache des Graphen ein Knoten zugeordnet ist der innerhalb dieser Flache liegt und umgekehrt und jeder Kante eine Kante zugeordnet ist die die beiden Flachen trennt die den Endknoten der Kante des ursprunglichen Graphen zugeordnet sind und die beiden Knoten verbindet die den benachbarten Flachen der Kante des ursprunglichen Graphen zugeordnet sind Die dualen Kanten schneiden also jeweils die ursprunglichen Kanten In den Abbildungen sind die ursprunglichen Graphen blau und die dualen Graphen rot gefarbt Ist der Graph nicht nur planar sondern auch zusammenhangend so gilt dass die Anzahl der Knoten des dualen Graphen der Anzahl der Flachen des ursprunglichen Graphen entspricht und umgekehrt und die Anzahl der Kanten bleibt konstant Im zusammenhangenden Fall gibt es damit bijektive Abbildungen zwischen den Kantenmengen der beiden Graphen und jeweils der Mengen der Knoten und der Menge der Flachen Der Begriff dual wird verwendet weil die Eigenschaft ein dualer Graph zu sein gegenseitig ist was bedeutet dass G displaystyle G nbsp ein dualer Graph von G displaystyle G nbsp ist wenn G displaystyle G nbsp ein dualer Graph eines zusammenhangenden Graphen G displaystyle G nbsp ist Zu planaren Graphen kann es im Allgemeinen mehrere duale Graphen geben abhangig von der Wahl der planaren Einbettung des Graphen 3 Verwendung BearbeitenDie Untersuchung der Planaritat von Graphen gehort zu den klassischen Themengebieten der Graphentheorie und wird auch oftmals als starke Voraussetzung fur Satze verwendet So besagt der Vier Farben Satz dass sich planare Graphen mit 4 Farben farben lassen Dreiecksfreie planare Graphen sind 3 farbbar Literatur BearbeitenReinhard Diestel Graphentheorie 4 Auflage Springer Berlin 2010 ISBN 978 3 642 14911 5 354 S diestel graph theory com Lutz Volkmann Fundamente der Graphentheorie Springer Wien 1996 ISBN 3 211 82774 9 Graphen an allen Ecken und Kanten PDF 3 7 MB Einzelnachweise Bearbeiten Folge A033995 in OEIS Folge A003094 in OEIS L R Foulds Graph Theory Applications In Springer 2012 S 66 67 eingeschrankte Vorschau in der Google Buchsuche Abgerufen von https de wikipedia org w index php title Planarer Graph amp oldid 237815789
