imported>Biggerj1 am 30. März 2025 um 18:29 Uhr

2025-03-30T18:29:08Z

Neue Seite

{|class="wikitable" align="right" style="margin-left: 1em;"
!colspan="2"|Beispiele
|-
! Planar
! Nicht planar
|-
| align="center" | [[Image:Butterfly graph.svg|100px]] [[Schmetterlingsgraph]]
| align="center" | [[Image:Complete graph K5.svg|100px]] [[Vollständiger Graph]] ''K''5
|-
| align="center" | [[File:CGK4PLN.svg|100x100px]] [[Vollständiger Graph]] ''K''4
| align="center" | [[Image:Biclique K 3 3.svg|100px]] [[K3,3|''K''3,3]], vollständiger [[bipartiter Graph]] mit 3 Knoten pro Teilmenge
|}
Ein '''planarer''' oder '''plättbarer Graph''' ist in der [[Graphentheorie]] ein [[Graph (Graphentheorie)|Graph]], der auf einer Ebene, mit Punkten für die [[Knoten (Graphentheorie)|Knoten]] und Linien für die [[Kante (Graphentheorie)|Kanten]], so dargestellt werden kann, dass sich keine Kanten schneiden.

== Definition ==
Ein Graph <math> G=(V,E) </math> heißt '''planar''' oder '''plättbar''', wenn er eine Einbettung in die [[Euklidische Ebene|Ebene]] besitzt; das heißt, er kann in der Ebene ''gezeichnet'' werden, so dass seine Kanten durch [[Jordan-Kurve]]n 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 '''Flächen''' geteilt (auch ''Gebiete'' oder ''Facetten'' genannt), die von den Kanten des Graphen begrenzt werden. Die begrenzenden Kanten einer Fläche bilden ihren Rand. Die unbeschränkte Fläche um den Graphen herum wird ''äußere Fläche'' genannt. Zwei Einbettungen heißen ''äquivalent'', wenn es eine [[Isomorphie von Graphen|isomorphe Abbildung]] zwischen den Rändern ihrer Flächen gibt.

== Verwandte Begriffsbildungen ==
[[Datei:kreisartigplaettbar.svg|mini|Beispiel eines außerplanaren Graphen; links planare Einbettung, rechts planare Einbettung, in der alle Knoten auf der äußeren Fläche liegen]]

Ein Graph heißt '''maximal planar''' oder [[Dreiecksgraph]], wenn er planar ist und ihm keine [[Kante (Graphentheorie)|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: [[Vollständiger Graph|K5]] ist fast planar.

Ein Graph heißt '''außerplanar''' (oft auch '''außenplanar''' oder '''kreisartig planar'''), wenn er sich so in die [[Ebene (Mathematik)|Ebene]] einbetten lässt, dass alle seine [[Knoten (Graphentheorie)|Knoten]] auf dem Rand ein und desselben Gebiets liegen.

== Eigenschaften ==
* [[Datei:Kuratowski.gif|mini|[[Animation]]: Der [[Petersen-Graph]] enthält den vollständig [[Bipartiter Graph|bipartiten Graphen]] <math> K_{3,3} </math> als [[Minor (Graphentheorie)|Minor]] und ist deshalb nicht planar.]]Der [[Satz von Kuratowski]] gibt eine nicht-geometrische Charakterisierung von planaren Graphen. Er besagt, dass ein [[Graph (Graphentheorie)|Graph]] genau dann planar ist, wenn er keinen [[Teilgraph]]en besitzt, der ein [[Unterteilungsgraph]] des [[Vollständiger Graph|vollständigen Graphen]] <math> K_5 </math> oder des vollständig [[Bipartiter Graph|bipartiten Graphen]] <math> K_{3,3} </math> ist. Einen Unterteilungsgraph erhält man, indem man wiederholt eine [[Kante (Graphentheorie)|Kante]] durch ein [[Inzidenz (Graphentheorie)|inzidentes]] Kantenpaar ersetzt. Alternativ kann man formulieren, dass ein Graph genau dann planar ist, wenn er weder den <math> K_5 </math> noch den <math> K_{3,3} </math> als [[Minor (Graphentheorie)|Minor]] enthält.
* Aus dem [[Eulerscher Polyedersatz|Eulerschen Polyedersatz]] ergibt sich, dass die Flächenzahl jeder Einbettung dieselbe ist.
* Für einen planaren Graphen ohne Schleifen und Mehrfachkanten ergibt sich aus dem Polyedersatz die Abschätzung <math> |E| \leq 3 \cdot |V| - 6</math>. Dies lässt sich für dreiecksfreie Graphen mit mindestens 3 Knoten noch auf die folgende Ungleichung verbessern: <math> |E| \leq 2 \cdot |V| - 4 </math>
* Ist ein planarer Graph [[k-Zusammenhang|3-fach zusammenhängend]], so sind alle seine Einbettungen (bis auf eine globale Umorientierung) äquivalent.
* Ein planarer Graph mit <math> n \geq 3 </math> Knoten ist genau dann maximal planar, wenn er <math> 3 \cdot n - 6 </math> Kanten hat.
* Ein planarer Graph kann höchstens [[k-Zusammenhang|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.

Die Planarität eines [[Graph (Graphentheorie)|Graphen]] lässt sich mit verschiedenen [[Algorithmus|Algorithmen]] in linearer [[Laufzeit (Informatik)|Laufzeit]] testen.

=== Der Eulerscher Polyedersatz ===
Der [[Eulerscher Polyedersatz|Eulersche Polyedersatz]] besagt, dass jeder endliche [[Zusammenhängender Graph|zusammenhängende]] planare [[Graph (Graphentheorie)|Graph]] mit <math> |V| </math> [[Knoten (Graphentheorie)|Knoten]], <math> |E| </math> [[Kante (Graphentheorie)|Kanten]] und <math> |F| </math> Flächen folgende [[Gleichung]] erfüllt:
:<math> |V| - |E| + |F| = 2 </math>

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:
:<math> |E| \leq 3 \cdot |V| - 6 </math>

Der Polyedersatz gilt auch für konvexe [[Polyeder]]. Dies ist kein Zufall: Jedes konvexe Polyeder kann mithilfe des [[Schlegeldiagramm]]s des Polyeders, einer [[Zentralprojektion]] des Polyeders auf eine [[Ebene (Mathematik)|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 [[Baum (Graphentheorie)|Bäume]] zum Beispiel nicht.

Der [[Satz von Steinitz]] besagt, dass die aus konvexen [[Polyeder]]n gebildeten [[Graph (Graphentheorie)|Graphen]] genau die endlichen [[k-Zusammenhang|3-fach zusammenhängenden]] einfachen planaren Graphen sind. Im Allgemeinen gilt der Polyedersatz für jedes Polyeder, dessen Flächen einfache [[Polygon]]e sind, die unabhängig von ihrer Konvexität eine Oberfläche bilden, die [[Topologie (Mathematik)|topologisch]] äquivalent zu einer [[Kugel]] sind.

=== Durchschnittlicher Knotengrad ===
[[Zusammenhängender Graph|Zusammenhängende]] planare [[Graph (Graphentheorie)|Graphen]] mit mehr als einer [[Kante (Graphentheorie)|Kante]] erfüllen die [[Ungleichung]] <math> 2 \cdot |E| \geq 3 \cdot |F|</math>, weil jede Fläche benachbart zu mindestens drei Kanten und jede Kante genau zwei Flächen begrenzt. Aus der Ungleichung <math> |E| \leq 3 \cdot |V| - 6</math> folgt für den durchschnittlichen [[Knotengrad]]

:<math> \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|} < 6</math>

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 Graphendichte ===
Die Dichte <math> D</math> eines planaren [[Graph (Graphentheorie)|Graphen]] oder Netzwerks ist definiert als ein Verhältnis der Anzahl der [[Kante (Graphentheorie)|Kanten]] <math> |E|</math> zur Anzahl der maximal möglichen Kanten in einem Netzwerk mit <math> |V|</math> [[Knoten (Graphentheorie)|Knoten]], gegeben durch einen planaren Graphen mit <math> |E| = 3 \cdot |V| - 6</math>:
:<math> D = \frac{|E| - |V| + 1}{2 \cdot |V| - 5}</math>

Ein [[Zusammenhängender Graph|zusammenhängender]] planarer [[Graph (Graphentheorie)|Graph]] mit minimaler Anzahl von [[Kante (Graphentheorie)|Kanten]], also ein [[Baum]], hat eine Kante weniger als Knoten, also ist <math> |E| = |V| - 1</math> und <math> D = 0</math>. Für einen zusammenhängenden planaren Graphen mit maximaler Anzahl von Kanten ist <math> D = 1</math>.

== Kombinatorik ==
Die Anzahl der [[Einfacher Graph|einfachen]] planaren [[Graph (Graphentheorie)|Graphen]] ohne nummerierte [[Knoten (Graphentheorie)|Knoten]] steigt schneller als [[Exponentialfunktion|exponentiell]] mit der Anzahl <math> n</math> der [[Knoten (Graphentheorie)|Knoten]]. Die folgende [[Tabelle]] zeigt die mit Hilfe eines [[Computer]]s bestimmten Anzahlen für <math> n \leq 12</math>:<ref>{{OEIS|A033995}}</ref><ref>{{OEIS|A003094}}</ref>
{| class="wikitable" style="text-align:right"
! colspan="3"|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 Graphen ==
[[Datei:Noniso dual graphs.svg|mini|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.]]
[[Datei:DodecahedralGraphDuals.png|mini|Dodekaedergraph mit [[Dualität (Mathematik)|dualem]] Ikosaedergraph]]
Jeder planare Graph hat einen [[Dualität (Mathematik)|dualen Graphen]]. Das ist ein [[Graph (Graphentheorie)|Graph]], wo jeder Fläche des Graphen ein [[Knoten (Graphentheorie)|Knoten]] zugeordnet ist, der innerhalb dieser Fläche liegt, und umgekehrt, und jeder [[Kante (Graphentheorie)|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 [[Zusammenhang von Graphen|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 Abbildung|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 <math>G</math> ein dualer Graph von <math>G'</math> ist, wenn <math>G'</math> ein dualer Graph eines [[Zusammenhängender Graph|zusammenhängenden Graphen]] <math>G</math> ist. Zu planaren Graphen kann es im Allgemeinen mehrere duale Graphen geben, abhängig von der Wahl der planaren Einbettung des Graphen.<ref>{{Literatur |Autor=L. R. Foulds |Titel=Graph Theory Applications |Sammelwerk=Springer |Datum=2012 |Seiten=66–67 |Online={{Google Buch |BuchID=5G4QBwAAQBAJ |Seite=66}}}}</ref>

== Verwendung ==
Die Untersuchung der Planarität von [[Graph (Graphentheorie)|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ärbung (Graphentheorie)|färben]] lassen. Dreiecksfreie planare Graphen sind [[Dreifarbenproblem|3-färbbar]].

== Literatur ==
* {{Literatur
|Autor=[[Reinhard Diestel]]
|Titel=Graphentheorie
|Auflage=4.
|Verlag=Springer
|Ort=Berlin
|Datum=2010
|ISBN=978-3-642-14911-5
|Online=https://diestel-graph-theory.com/
|Umfang=354}}
* {{Literatur
|Autor=Lutz Volkmann
|Titel=Fundamente der Graphentheorie
|Verlag=Springer
|Ort=Wien
|Datum=1996
|ISBN=3-211-82774-9
|Online=[https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf "Graphen an allen Ecken und Kanten"]
|Format=PDF
|KBytes=3700}}

== Weblinks ==
* [https://www.spektrum.de/lexikon/mathematik/planarer-graph/9468 ''Planarer Graph.''] In: ''Springer Lexikon der Mathematik.''

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4174783-5}}
[[Kategorie:Planarer Graph| ]]
[[Kategorie:Topologische Graphentheorie]]

Planarer Graph - Versionsgeschichte

imported>Biggerj1 am 30. März 2025 um 18:29 Uhr