imported>Aka: /* Definition */ Tippfehler entfernt

2025-05-12T20:12:32Z

Neue Seite

Ein '''ebener Graph''' ist eine konkrete Darstellung eines [[Graph (Graphentheorie)|Graphen]] als Teilmenge des <math> \mathbb{R}^2</math> und damit ein Spezialfall eines [[Euklidischer Graph|euklidischen Graphen]] für <math> q=2</math>.

== Definition ==
Ein [[Tupel]] <math> (V,E)</math> (wobei die Elemente aus <math> V</math> Ecken genannt werden und die Elemente aus <math> E</math> Kanten) heißt ein ebener Graph, wenn gilt:
* <math> V </math> besteht aus paarweise disjunkten Punkten des <math> \mathbb{R}^2</math>.
* Jede Kante ist eine [[einfache Jordankurve]], die zwei Ecken miteinander verbindet.
* Die Kanten schneiden sich nie und berühren sich bloß in den Ecken.

Teilweise wird in der Literatur auch noch folgende vierte Bedingung gestellt:
* Verschiedene Ecken werden durch verschiedene Kanten verbunden.

Diese Verschärfung wird oftmals gefordert, wenn man nur [[Einfacher Graph|einfache Graphen]] auf [[Planarer Graph|Planarität]] untersuchen will. Die obigen drei Punkte lassen noch [[Multigraph]]en als betrachteten Gegenstand zu.

Ein ebener Graph heißt '''maximal eben''', wenn er eben ist, aber nach dem Hinzufügen einer beliebigen Kante nicht mehr eben ist.

== Abgrenzung zu planaren Graphen ==
[[Datei:Forbys planar graphs example.png|gerahmt|ohne|Beispielgraphen G1 und G2]]
Der Begriff ebener Graphen kann leicht mit dem [[Planarer Graph|planarer Graphen]] verwechselt werden: Planarität ist eine Eigenschaft von ''abstrakten Graphen'', also Graphen, aufgefasst als eine Knotenmenge und eine Kantenmenge, d. h. eine Teilmenge aller Mengen aus zwei verschiedenen Knoten bzw. eine [[Relation (Mathematik) |Relation]] zwischen zwei verschiedenen Knoten. Ein ebener Graph jedoch ist eine ''Darstellung'' eines abstrakten Graphen als Teilmenge des <math> \mathbb{R}^2</math>. So ist im obigen Bild <math> G_1 </math> eben. Betrachtet man <math> G_2</math> als Teilmenge des <math> \mathbb{R}^2</math>, so muss dieser erst anders gezeichnet werden, um einen ebenen Graphen zu erhalten. Der zugrunde liegende abstrakte Graph <math> G_2</math> ist aber planar unabhängig davon, wie man ihn im konkreten Fall zeichnet. Definitionsgemäß sind die planaren Graphen genau diejenigen Graphen, die zu einem ebenen Graphen isomorph sind.

== Eigenschaften ==
* Für zusammenhängende ebene Graphen gilt nach dem [[Eulerscher Polyedersatz|eulerschen Polyedersatz]]:
: <math> n-m + f= 2 </math>, wobei <math> n=|V|</math>, <math> m= |E|</math> und <math> f</math> die Anzahl der Flächen des Graphen ist (die äußere Fläche mitgerechnet)
* Jeder maximal ebene Graph ist [[Planarer Graph#Verwandte Begriffsbildungen|maximal planar]]

== 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/ Online-Version] |Umfang=354}}
* Lutz Volkmann: ''Fundamente der Graphentheorie'', Springer (Wien) 1996, ISBN 3-211-82774-9 ([https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf neuere, Online-Version "Graphen an allen Ecken und Kanten"]; PDF; 3,7 MB)

== Weblinks ==
* [https://www.spektrum.de/lexikon/mathematik/ebener-graph/2192 ''Ebener Graph.''] In: ''Springer Lexikon der Mathematik.''

{{Normdaten|TYP=s|GND=4725393-9}}
[[Kategorie:Topologische Graphentheorie]]
[[Kategorie:Graphenklasse]]

Ebener Graph - Versionsgeschichte

imported>Aka: /* Definition */ Tippfehler entfernt