Ebener Graph

Ein ebener Graph ist eine konkrete Darstellung eines Graphen als Teilmenge des {\mathbb  {R}}^{2} und damit ein Spezialfall eines euklidischen Graphen für q=2.

Definition

Ein Tupel (V,E) (wobei die Elemente aus V Ecken genannt werden und die Elemente aus  E Kanten) heißt ein ebener Graph, wenn gilt:

Teilweise wird in der Literatur auch noch folgende vierte Bedingung gestellt:

Diese Verschärfung wird oftmals gefordert, wenn man nur einfache Graphen auf Planarität untersuchen will. Die obigen drei Punkte lassen noch Multigraphen 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

Beispielgraphen G1 und G2

Bei ebenen Graphen besteht oftmals eine Verwechslungsgefahr zu den planaren Graphen: Planarität ist eine Eigenschaft von abstrakten Graphen, also Graphen, aufgefasst als eine Knotenmenge und je nach Definition unterschiedliche Kantenmenge. Ein ebener Graph jedoch ist eine Darstellung eines abstrakten Graphen als Teilmenge des {\mathbb  {R}}^{2}. So ist im obigen Bild G_{1} eben. Betrachtet man G_{2} als Teilmenge des {\mathbb  {R}}^{2}, so muss dieser erst anders gezeichnet werden, um einen ebenen Graphen zu erhalten. Der zugrunde liegende abstrakte Graph G_{2} 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

n-m+f=2, wobei n=|V|, m=|E| und f die Anzahl der Flächen des Graphen ist (die äußere Fläche mitgerechnet)

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 11.02. 2019