Ungerichteter Graph/Planar/Einführung/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Eine ebene nicht überschneidungsfreie Skizze
und eine ebene überschneidungsfreie Realisierung des vollständigen Graphen mit vier Punkten.
Eine ebene Realisierung des Würfelgraphen



Definition  

Ein Graph heißt planar, wenn er eine geometrische Realisierung im besitzt.

Unter einem Gebiet in der Ebene verstehen wir ein durch die Bilder von stetigen Wegen berandetes zusammenhängendes Flächenstück. Ein planar Graph bewirkt eine Einteilung der Ebene in Gebiete. Eine exakte Definition von Gebiet, Begrenzung, innen und außen gehört zur Topologie, wir fassen die für uns relevanten und intuitiv klaren Prinzipien kurz zusammen.

Bemerkung  

An einem (zu einer Kante des Graphen gehörenden) Weg liegen ein oder zwei Gebiete an.

Verschiedene Gebiete schneiden sich in einer Vereinigung von Wegen.

Jeder Punkt der Ebene ist entweder ein Bildpunkt eines Knotenpunktes oder gehört zu genau einem Weg (ohne Endpunkt) oder gehört zu genau einem Gebiet (ohne den Rand).

Zu einem Kreis des Graphen gehört ein geschlossener Weg, der die Ebene in ein Innen und Außen einteilt. Das Innere und das Äußere davon ist eine Vereinigung von Gebieten. Ein stetiger Weg von einem Punkt des Innern zu einem Punkt des Äußeren trifft den Begrenzungsweg.

An jedes geschlossene (endliche) Gebiet grenzen zumindest drei Weg an.

Es gibt ein äußeres unendliches Gebiet.