| | | Planare Graphen |
Definition. Ein Multigraph G=(V,E) heißt planar, wenn er eine planare Einbettung hat, d.i. eine Abbildung p:V -> R2 sowie eine Abbildung l:E -> J, wobei J die Menge aller offenen Jordanbögen (das sind doppelpunktfreie Kurven in der Ebene ohne ihre Randpunkte) ist, so dass für jede Kante e=(u,v) der topologische Rand von l(e) gerade p(u) und p(v) sind und für je zwei Kanten e,f l(e) und l(f) einen leeren Durchschnitt haben, m.a.W. man kann den Graphen kreuzungsfrei in die Ebene zeichnen.
Bei zusammenhängenden, ebenen Multigraphen besteht folgende Beziehung zwischen der Anzahl der Knoten V, Kanten E und Gebiete F. Dabei sind die Gebiete die zusammenh"angenden Komponenten von R2 \ L(E) \ p(V)).
Lemma.
[Eulersche Polyederformel]
|V|-|E|+|F|=2.
Sei also nun G(V,E) ein zusammenhängender, ebener Multigraph mit |V|>1 Knoten und e in E eine Kante, die keine Schleife ist. Kontrahieren wir e, so erhalten wir einen zusammenhängenden, planaren Multigraphen, der ebensoviele Gebiete, aber genau einen Knoten und genau eine Kante weniger hat als G. Für diesen gilt nach Induktionsvoraussetzung |V|-1-(|E|-1)+|F|=2, woraus die Behauptung folgt. qed
Bemerkung.
Wenn wir die Formel lesen als
-1 +|V|-|E|+|F|-1=0,
wobei die erste -1 die leere Menge und die
letzte den ganzen Graphen zählt, können wir sie auf beliebig
dimensionale Polyeder (eckige, konvexe Körper) verallgemeinern zu
Zählt man die Seitenflächen eines Polyeders nach Dimension
geordnet mit alternierendem Vorzeichen, so erhält man stets Null.
| | | Planare Graphen |