Die Eulersche Polyederformel und Anwendungen

SE Mathematisches Seminar II, SS 2010,

LV-Leiter: Bernhard Schratzberger,

Fachbereich Mathematik

Universität Salzburg,

Thomas Kellner,

Gerhard Mitterlechner

Seminararbeit für das Mathematische Seminar II

Die Eulersche Polyederformel und Anwendungen

Zusammenfassung

In dieser Arbeit werden die Eulersche Polyederformel und ihre inner- und auÿermathematischen

Anwendungen behandelt. Dazu wird zunächst eine Einleitung in die Graphentheorie gegeben,

inklusive einer Charakterisierung verschiedener Typen von Graphen und historischer Notizen.

Die Euler'sche Polyederformel wird dann über das Konzept der Dualisierung bewiesen, und zur

mathematischen Beschreibung platonischer bzw. archimedischer Körper verwendet. Im Anschluss

daran bewiesen wir die Nicht-Planarität spezieller vollständiger Graphen, sowie grundlegende Be-

ziehungen zwischen Anzahlen von Ecken und Kanten planarer Graphen.

Am Beispiel des Voronoi-Diagramms sowie der Delaunay-Triangulierung wird gezeigt, dass Kon-

zepte der Graphentheorie in der Informatik von groÿer Bedeutung sind. Den Abschluss bildet der

Satz von Pick, welcher die Fläche eines Polygons mit ganzzahligen Ecken angibt. Für den Beweis

werden Begri�e der Linearen Algebra verwendet, welche im einführenden Kapitel kurz wiederholt

werden.

1

Inhaltsverzeichnis

1 Einleitung: Wiederholung Lineare Algebra 3

2 Einleitung: Graphentheorie 42.1 Grundlegende De�nitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Charakterisierung von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2.1 Planare Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.2 Vollständige Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.3 Bipartite Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2.4 Gewichtete Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2.5 Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 Dualisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4 Eckengrad, durchschnittlicher Eckengrad, durchschnittliche Kantenzahl . . . . . . . . . 112.5 Historische Entwicklung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5.1 Leonhard Euler und das Königsberger Brückenproblem . . . . . . . . . . . . . . 122.5.2 Der Vier-Farben Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Euler'sche Polyederformel 16

4 Platonische Körper 174.1 Geschichtliches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.2 Wiederholung: Polyeder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.3 Zwei Beweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.4 Anwendung: Fuÿball . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5 Weitere Beweise mithilfe der Polyederformel 215.1 K5 ist nicht planar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.2 K3,3 ist nicht planar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.3 Maximaler Eckengrad, maximale Kantenzahl . . . . . . . . . . . . . . . . . . . . . . . 22

6 Anwendungen in der Informatik 236.1 Voronoi-Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.1.1 Nearest Neighbor Probleme: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276.1.2 Andere Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

6.2 Delaunay-Triangulierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286.2.1 Landschafts-Modellierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286.2.2 Konstruktion aus dem Voronoi-Diagramm . . . . . . . . . . . . . . . . . . . . . 306.2.3 Eigenschaften der Delaunay-Triangulation . . . . . . . . . . . . . . . . . . . . . 316.2.4 Weitere Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

7 Satz von Pick 31

Literatur 34

2

Mathematisches Seminar II Eulersche Polyederformel T. Kellner, G. Mitterlechner

1 Einleitung: Wiederholung Lineare Algebra

In diesem Abschnitt werden einige Aussagen der linearen Algebra wiederholt, welche später für einenTeil des Beweises des Satzes von Pick in Abschnitt 7 benötigt werden (vgl. [8], S.103-109, S.164, sowieS.364-368).

1. Die (n× n)-Einheitsmatrix In besitzt die Determinante 1, also det(In) = 1.

2. Für eine (n× n)-Matrix M und ihre transponierte Matrix MT gilt: det(M) = det(MT ). Insbe-sondere gilt: sind die Vektoren linear abhängig, so ist det(M) = 0.

3. Eine (n× n)-Matrix M ist genau dann invertierbar, wenn det(M) 6= 0 ist.

4. Für eine invertierbare (n× n)-Matrix M mit zugehöriger inversen Matrix M−1 gilt:

det(M−1) =1

det(M).

5. Für zwei (n× n)-Matrizen M und N gilt der Determinantenmultiplikationssatz :

det(M ·N) = det(M) · det(N)

6. Sei M eine invertierbare (n×n)-Matrix, M−1 ihre Inverse, sowie In die (n×n)-Einheitsmatrix.Dann gilt:

det(M) · det(M−1) = det(M ·M−1) = det(In) = 1.

7. Seien ~v und ~u zwei Vektoren ∈ R2. Sei M eine (2× 2)-Matrix, welche ~v und ~u als Spalten- oderZeilenvektoren besitzt. Sei A der Flächeninhalt des zwischen ~u und ~v aufgespannte Parallelo-gramms. Dann gilt:

A = |det(M)|.

8. Die Determinante einer ganzzahligen (n× n)-Matrix M ist wiederum ganzzahlig, also

M ∈ Zn×n ⇒ det(M) ∈ Z.

9. Für eine (n× n)-Matrix M sind folgende Aussagen äquivalent:

(a) Das Gleichungssystem M~x = ~0 besitzt nur die triviale Lösung.

(b) Das Gleichungssystem M~x = ~b besitzt für jeden n-dimensionalen Vektor ~b genau eineLösung.

(c) M ist invertierbar.

(d) det(M) 6= 0.

10. Koordinaten und Basiswechsel:

(a) Sei B = {~b1,~b2, . . . ,~bn} eine Basis eines Vektorraumes V über R. Dann gilt:

• Jeder Vektor ~v aus V lässt sich eindeutig als Linearkombination

~v = k1~b1 + k2

~b2 + . . . + kn~bn

darstellen, wobei ki ∈ R für i ∈ {1, . . . , n}.

3


• Die Skalare k1, k2, . . . , kn bilden den Koordinatenvektor [~v]B von ~v ∈ V bezüglich Bmit

[~v]B =

k1

k2...

kn

.

(b) Sind B = {~b1, . . . ,~bn} und C = {~c1, . . . ,~cn} zwei Basen eines Vektorraums V , dann gilt:

• Sind [~v]B und [~v]C die Koordinatenvektoren eines Vektors ~v aus V bezüglich B bzw.C, dann gilt:

[~v]C = P [~v]B,

wobei die (n× n)-Matrix P aus den Spalten

[~b1]C , [~b2]C , . . . , [~bn]C

besteht und Übergangsmatrix von B nach C heiÿt. Diese Matrix wandelt also einenKoordinatenvektor eines Vektors v bezüglich der Basis B in einen Koordinatenvektorbezüglich Basis C um.

• P ist invertierbar.

• P−1 ist die Übergangsmatrix von C nach B, und es gilt

[~v]B = P−1[~v]C .

(P−1 führt also den Koordinatenvektor von ~v bezüglich Basis C in einen Koordinaten-vektor bezüglich Basis C über.)

2 Einleitung: Graphentheorie

2.1 Grundlegende De�nitionen

Ein Graph eine Struktur, in welcher Ecken (bzw. Knoten) durch Kanten verbunden werden (Abb.1). Anfangs- und Endpunkt einer Kante ist immer eine Ecke. Eine Kante verbindet zwei verschiedeneEcken, es sei denn es handelt sich um eine Schlinge (loop, ([13], S.25): in diesem Fall wird eine Eckemit sich selbst verbunden (Abb. 1, zweite Ecke von rechts). Ecken werden in der Zeichenebene alskleine Kreise oder Punkte visualisiert, eine Kante hingegen wird graphisch durch eine gerade Linie(Strecke) oder eine gekrümmte Linie bzw. Kurve dargestellt.

Abbildung 1: Ein Graph: Ecken werden durch Kanten verbunden.

Eine graphische Darstellung eines Graphen in der Zeichenebene nennt man Einbettung.

4


Ein Graph G wird formal repräsentiert durch seine (nichtleere) Eckenmenge V sowie die Kan-tenmenge E. Also (vgl. [23], S.52):

De�nition 2.1 Ein Graph G ist ein Tupel G = (V,E), mit der nichtleeren Eckenmenge V = {v1, v2, . . . , vn}sowie der Kantenmenge E = {e1, e2, . . . , ee}. Dabei ist n = |V | die Gesamtanzahl der Ecken, unde = |E| die Gesamtanzahl der Kanten.Die Buchstabenwahl ergibt sich aus den englischen Bezeichnungen vertex für Ecke und edge für Kante.Im Englischen ist auch noch die Bezeichnung arc für eine Kante anzutre�en. Der Graph aus Abb. 1beispielsweise besitzt n = 8 Ecken sowie e = 8 Kanten, welche in Abb. 3 beschriftet dargestellt sind.

Für die mathematische Darstellung einer Kante gibt es verschiedene Möglichkeiten. Wir betrachtenhauptsächlich sogenannte einfache Graphen, in welchen keine Schlingen, sowie zwischen zwei Eckenkeine Kanten mehrfach vorkommen dürfen. Für solche einfache Graphen ist es bequem Kanten alseine zwei-elementige Menge von miteinander verbundenen Ecken zu de�nieren:

De�nition 2.2 Sei G ein einfacher Graph. Dann ist die Kantenmenge E de�niert durch:

E := {{vi, vj} : vi, vj ∈ V, vi 6= vj , vi und vj sind verbunden, i, j ∈ {1, . . . , n}}.Eine Kante welche vi und vj verbindet, wird weiters bezeichnet mit eij, also eij := {vi, vj}.Dabei gilt aufgrund der Einfachheit des Graphen eij = eji. Auÿerdem ist eii (Schlinge) gemäÿ De�ni-tion ausgeschlossen. Alternativ könnte E auch als Menge von geordneten Paaren dargestellt werden,also E = {(vi, vj) ∈ V × V : vi und vj sind verbunden, mit i < j}.

Abbildung 2: Ein einfacher Graph.

Bemerkung: Sind Schlingen erlaubt, so kann man eine Kante als ungeordnetes Paar (vgl. [9], S.4)oder eine zwei-elementigeMultimenge de�nieren, sodass auch {ei, ei} in E enthalten sein kann . DürfenKanten zwischen zwei Ecken mehrfach vorkommen (Mehrfachkanten bzw. parallel edges [13], S.17), soist E selbst eine Multimenge von zweielementigen Mengen bzw. Multimengen. Ein solcher Graph heiÿt- als Gegensatz zu einem einfachen Graphen - auch Multigraph ([13], S.26). Diese Terminologie istin der Literatur - wie in ([13], S.26) erwähnt - uneinheitlich. In vielen Büchern wird nämlich unterGraph automatisch ein einfacher Graph verstanden. Siehe Abb. 3 für einen Multigraphen, und Abb.2 für einen einfachen Graphen.

Gerichtete/ungerichtete Graphen: Durch die Darstellung einer Kante als zwei-elementige Men-ge (bzw. zwei-elementige Multimenge) wird nur ausgedückt, dass eine Ecke vi mit einer anderen (nichtnotwendigerweise von vi verschiedenen) Ecke verbunden ist. Solche Graphen, in denen Kanten keineRichtung, bzw. keine Start- bzw. Endecke besitzen, heiÿen ungerichtete Graphen. Eine weitere Varia-tion, welche für zahlreiche Anwendungen von Bedeutung ist, sind gerichtete Graphen, wo eine Kanteausgezeichnete Start- bzw. Endecken besitzt, also die Kante eij von der Kante eji zu unterscheidenist. In gerichteten Graphen wird analog zu oben die Kantenmenge als eine Menge von ungeordnetenPaaren repräsentiert: E = {(vi, vj) ∈ V ×V : es führt eine Kante von vi nach vj }. Die Richtung einerKante wird in der Einbettung durch einen Pfeil symbolisiert.

5


v1

v2

v3

v4

v5

v6

v7v8

e1

e2e3

e4

e5

e6

e7

e8

Abbildung 3: Ein nicht einfacher Graph: e3 ist eine Schlinge, e1 und e6 verbinden dieselben zwei Ecken(Doppelkante). Der Graph ist also ein Multigraph.

Untergraph: Ein Graph G′ = (V ′, E′) ist ein Untergraph eines Graphen G = (V,E), wenn V ′ ⊆ Vund E′ ⊆ ist, und wenn jede Kante e ∈ E′ dieselben Ecken in G′ verbindet wie in G ([7], S.60).

Im Weiteren beschäftigen wir uns nur mehr mit ungerichteten, einfachen Graphen.

Weg und Pfad: Ein Weg ist eine Abfolge von sukzessive durch Kanten miteinander verbundenenEcken, wobei jede Ecke mit der nachfolgenden Ecke durch eine Kante verbunden ist (vgl. [23], S.55,und siehe Abb. 4). Ein Pfad ist ein Weg, welcher nur verschiedene Ecken enthält:

De�nition 2.3 Sei G = (V,E) mit V = {v1, . . . , vn} ein einfacher Graph. Ein Weg (Kantenzug,walk) der Länge m in G ist eine endliche Folge von m + 1 Ecken (vi0 , vi2 , . . . , vim) mit eik,ik+1

∈ Efür alle k ∈ {0, . . . ,m− 1}, sowie ij ∈ {1, . . . , n} mit j ∈ {0, . . . ,m}.Ein Pfad in G ist ein Weg in dem alle Ecken paarweise verschieden sind, also vij 6= vik für alle k 6= j,k, j ∈ {0, . . . ,m}.

Bemerkung 1: Die De�nition in [23] verwendet keine Doppelindices, da schon die Elemente vonV von der Autorin nicht indiziert werden. In ([13], S.6) wird unter Anpassung der Buchstabenwahlan unsere Notation ein Pfad als eigenständiger Graph (V,E) de�niert mit V = {v0, . . . , vm} undE = {{v0, v1}, {v1, v2}, . . . , {vm−1, vm}}, wobei alle vi verschieden sind.

Bemerkung 2: Die Menge der Kanten welche einen Weg bzw. Pfad bilden ist gemäÿ obiger De�ni-tion nur bei einfachen Graphen eindeutig.

Kreis/Zyklus: Ein Kreis oder Zyklus ist ein Pfad, dessen letzte Ecke durch eine Kante mit derersten Ecke verbunden ist (vgl. [23], S.55). Ein Kreis der Länge m besteht im Unterschied zum Pfadnur aus m Ecken (Abb. 4).

De�nition 2.4 Ein Kreis der Länge m ist eine Folge (vi1 , vi2 , . . . , vim), für die gilt:

ei1,im ∈ E und eik,ik+1∈ E,

für alle k ∈ {1, . . . ,m− 1}, sowie ij ∈ {1, . . . , n} mit j ∈ {1, . . . ,m}.

Zusammenhängende Graphen: Ein Graph heiÿt zusammenhängend, wenn zwischen zwei belie-bigen Ecken vi 6= vj , i, j ∈ {1, . . . , n}, ein Pfad existiert. Der Graph in Abb. 1 ist beispielsweise nichtzusammenhängend (es gibt keinen Pfad, um z.B. von v1 aus zu v6 oder v8 zu gelangen), der Graph inAbb. 2 hingegen schon.

6


v1

v2

v3

v4v5

v6

v7

v8

Abbildung 4: Ein Graph mit einem (roten) Pfad der Länge 4: (v1, v2, v5, v8, v4). Weiters enthält ereinen (blauen) Kreis der Länge 4: (v4, v6, v2, v3).

2.2 Charakterisierung von Graphen

2.2.1 Planare Graphen

Graphen, welche so in der Ebene R2 gezeichnet werden können, dass sich keine zwei Kanten überkreu-zen, der Graph also überschneidungsfrei gezeichnet werden kann, nennt man planar. Einen planarenGraphen zusammen mit seiner Einbettung in die Ebene nennt man ebenen Graphen ([23], S.74).Man kann zeigen, dass jeder Graph der sich mit gekrümmten Linien überschneidungsfrei zeichnen lässt,sich auch mit ausschlieÿlich geraden Strecken überschneidungsfrei zeichnen lässt (Fáry's theorem, [10],S.139). Ein ebener Graph welcher ausschlieÿlich gerade Strecken verwendet, nennt man dann planarstraight-line graph (PSLG) [14]. Planare Graphen können auÿerdem ebenso auf der Kugelober�ächeüberschneidungsfrei gezeichnet werden (siehe [7], S.67, sowie den Beweis mittels stereographischerProjektion in [10], S.138). Der Fokus dieser Arbeit liegt ausschlieÿlich auf der Behandlung von zusam-menhängenden planaren Graphen.

Durch die Überschneidungsfreiheit enthält ein ebener Graph Gebiete (faces), welche von Kantenbegrenzt werden. DasAuÿengebiet (das unbegrenzte Gebiet) wird ebenfalls als Gebiet gezählt. DurchBerücksichtigung des ungegrenzten Gebiets besitzt also jeder planare Graph mindestens ein Gebiet.Ein begrenztes Gebiet in einem planaren Graphen ist immer durch einen Zyklus begrenzt. Gebiete eineinem planaren Graphen werden durch ein indiziertes g gekennzeichnet.

v1

v2

v3

v4v5

v6

v7

v8

g1

g2

g3

g4

Abbildung 5: Ein planarer Graph mit drei begrenzten Gebieten g1, g2, g3 und dem Auÿengebiet g4.Der Graph ist identisch mit dem aus Abb. 4, nur die Kante e4,7 wurde hier so gezeichnet dass keineKantenüberschneidungen auftreten. (Also ist auch der Graph aus Abb. 4 planar.)

2.2.2 Vollständige Graphen

In einem vollständigen Graphen sind beliebige zwei Ecken vi, vj ∈ V , i 6= j, durch (genau) eineKante verbunden (Abb. 6). Der vollständige Graph mit n Ecken wird bezeichnet durch Kn. Es isterwähnenswert, dass der in Abb. 6 dargestellte K4 trotz der abgebildeten Überkreuzung planar ist: dieKante e2,4 beispielsweise kann auch �auÿen herum� gezeichnet werden, sodass keine Überschneidungen

7


mehr auftreten. Für den K5 hingegen beweisen wir weiter unten, dass er nicht planar ist, er alsojedenfalls nur mit mindestens einer Kantenüberschneidung in der Ebene eingebettet werden kann.

v1

v2

v3

v4

Abbildung 6: Der vollständige Graph mit vier Ecken (K4): jede Ecke ist mit jeder anderen durch eineKante verbunden.

Lemma 2.1 Für die Anzahl e der Kanten in einem vollständigen Graphen gilt:

e =(

n2

).

Beweis: Die Anzahl der Kanten entspricht also der Anzahl aller 2-elementigen Teilmengen aus einerMenge mit n Elementen (n = |V |). Aus der Kombinatorik wissen, wir, dass die Anzahl aller k-

elementigen Teilmengen aus einer Menge mit n Elementen gleich

(nk

)ist. Also hat Kn genau(

n2

)viele Kanten. �

2.2.3 Bipartite Graphen

Ein bipartiter Graph ist ein Graph dessen Eckenmenge V sich aufteilt in zwei nicht disjunkte Teil-mengen A, B ⊆ V , also V = A ∪B, A ∩B = ∅ (vgl. [23], S.77, sowie [7], S.60). Für jede Kante mussgelten, dass eine zugehörige Ecke in A, die andere in B liegt. Also für alle eij ∈ E gilt vi ∈ A undvj ∈ B. Es darf also keine Kanten geben, deren Ecken in nur einer der beiden Mengen A oder Bliegen.

v1

v2

v3

v4

v5

AB

Abbildung 7: Ein bipartiter Graph mit A = {v1, v2, v3} und B = {v4, v5}. Es gibt ausschlieÿlichKanten zwischen Ecken aus A und Ecken aus B.

In einem vollständig bipartiten Graphen ist jede Ecke aus A mit jeder Ecke aus B verbunden.De�niert man m := |A| sowie n := |B|, so bezeichnet Km,n den entsprechenden vollständig bipartitenGraphen. Die Anzahl der Kanten in einem vollständig bipartiten Graphen ist anschaulicherweise m ·n(Abb. 8).

2.2.4 Gewichtete Graphen

Für praktische Probleme ist es oft notwendig, dass mit jeder Kante Kosten oder Gewichte verknüpftsind, welche je nach Anwendung etwa Entfernungen, Reisekosten, Flugpreise, Zeitaufwand, Wartekos-ten etc. modellieren. Mithilfe spezieller Algorithmen (z.B. Dijkstras Algorithmus, siehe Abschnitt 6)

8


v1

v2

v3

v4

v5

AB

Abbildung 8: Der vollständig bipartite Graph K3,2. Er besitzt 3 · 2 = 6 Kanten.

wird der mit den geringsten Kosten verbundene Pfad in einem gewichteten Graphen ermittelt, alsodas Problem des kürzesten Pfades gelöst (vgl. [21], S.513).

2.2.5 Bäume

Ein Baum ist de�niert als ein zusammenhängender Graph welcher keine Zyklen enthält (vgl. [23],S.57, und siehe Abb. 9).

Abbildung 9: Ein Baum als ein zusammenhängender Graph ohne Zyklen.

Lemma 2.2 Für jeden Baum ist die Anzahl der Kanten um eins niedriger ist als die Anzahl derEcken: e = n− 1.

Beweis (vgl. [7], S.67f.): Man wählt eine beliebige Ecke und ernennt diese zur Wurzel (Abb. 10). JedeKante wird nun dargestellt als Pfeil, wobei von der Wurzel ausgegangen wird und die Richtung vonder Wurzel weg gewählt wird. Diese Richtung ist für jede Kante eindeutig bestimmbar, da es wegender Zyklenfreiheit keinen Pfad von einer Ecke aus geben kann welcher wieder in derselben Ecke endet.Weil der Graph zusammenhängend ist, endet in jeder Ecke des Baumes ein Pfeil; auÿerdem können ineiner Ecke nicht mehrere Pfeile enden, da ansonsten ein Kreis von der Wurzel bis zur Wurzel gegebenwäre. In jeder Ecke auÿer der Wurzel endet also genau ein Pfeil, weswegen die Anzahl der Pfeile gleiche = n - 1 ist. �

Aufspannender Baum: Ein den (zusammenhängenden) Graphen G = (V,E) aufspannender Baumoder Spannbaum ist ein Baum T = (V ′, E′) mit V ′ = V und E′ ⊆ E ([23], S.60, und siehe Abb. 11).Der Graph T ist also ein spezieller Untergraph von G. (Er ist zusammenhängend und hat die identischeEckenmenge zu G. Die Forderung des Aufspannens bedeutet, dass jede Ecke von T von einer Kanteverbunden ist, welche auch ∈ E ist.) Es ist inituitiv einleuchtend, dass jeder zusammenhängende Grapheinen Spannbaum enthält, was in ([23], S.61) durch Angabe eines Verfahrens, welches nachweislicheinen Spannbaum konstruiert, bewiesen wird.

Lemma 2.3 Jeder den Graphen G = (V,E) aufspannende Baum T = (V,E′) ist bezüglich der Anzahl|E′| der Kanten minimal, d.h. es gibt keinen weiteren zusammenhängenden Graphen H = (V,E′′),E′′ ⊂ E, für den gilt: |E′′| < |E′|.

9


Wurzel

Abbildung 10: Illustration zum Beweis für e = n− 1.

Abbildung 11: Ein Graph und sein aufspannender Baum.

Beweis: Sei H ein den Graphen G = (V,E) aufpannender zusammenhängender Graph. Falls HKreise hat, so kann man eine beliebige Kante eines Kreises entfernen, sodass der Graph immer nochzusammenhängend ist. Nach Beseitigung aller Kreise ergibt sich nach De�nition ein aufspannenderBaum T = (V,E′). Eine Entfernung irgendeiner weiteren Kante aus E′ hingegen reiÿt T auseinander:T wäre in diesem Fall nicht mehr zusammenhängend. Auÿerdem gilt, dass jeder weitere Baum H =(V,E′′) mit derselben Eckenmenge nach obigem Lemma gleich viele Kanten wie T besitzt (also |E′′| =|E′| gilt). Also kann es keinen weiteren aufspannenden Baum mit weniger Kanten als |E′| geben. �

In einem gewichteten Graphen bezeichnet der Minimale Spannbaum jeden Baum, welcher den zwi-schen zwei beliebigen Ecken mit den geringsten Kosten verbundenen Pfad enthält. Man kann zeigen,dass der minimale Spannbaum für jede gegebene Zerlegung der Eckenmenge des Graphen in zweiTeilmengen die kürzeste der Kanten enthält, welche Ecken aus der einen Teilmenge mit denen deranderen verbindet (vgl. [21], S.515).

2.3 Dualisierung

Im folgenden Abschnitt betrachet man nur planare Graphen, an dem die Konstruktion des dualenGraphen gezeigt wird. ([24], S.193 f)

Sei f1, f2, .., fr die Regionen vom Graphen G, so ist die Konstruktion von G∗ wie folgt de�niert:

1. G∗ hat r Ecken v∗1, v∗2, ..., v

∗r , wobei v∗i , 1 ≤ i ≤ r, mit den Gebieten fi korrespondiert.

2. G∗ hat genau so viele Kanten wie G

3. Wenn eine Kante e von G die Gebiete fi und fj trennt (müssen nicht verschieden sein), dannverbindet die dazugehörige Kante e∗ in G∗ die Ecken v∗i und v∗j . (Jede Kante gehört zu zweiGebieten und es ist möglich, dass die Kante in ein und derselben Region liegt.)

Man kann nun G∗ einfach konstruieren, indem man zuerst in jede Region fi von G eine Ecke v∗i legt.Dann zeichnet man für jede Kante e, die jeweils die Gebiete fi und fj begrenzt, eine Linie ein, die die

10


Ecken v∗i und v∗j verbindet, sodass sie die Kante e schneidet. Diese Linie repräsentiert nun die Kantee∗ vom dualen Graphen.

Abbildung 12: Ein Graph (durchgezogene Linie) mit seinem Dualgraphen (strichlierte Linie) ([13],S.90)

2.4 Eckengrad, durchschnittlicher Eckengrad, durchschnittliche Kantenzahl

Die folgenden Beweise sind nach der Vorgehensweise von [7] geführt.

De�nition 2.5 Der Eckengrad oder Grad d(v) einer Ecke v ∈ V ist die Anzahl der Kanten, die vonv ausgehen.

Bemerkung: Im Falle einer Schlinge wird die Kante doppelt gezählt. Beispielsweise sind in Abb. 3d(v1) = 3, d(v2) = 4, d(v3) = 4 (!), d(v4) = 2, d(v5) = 1, d(v6) = 0, d(v7) = 1, d(v8) = 1.

Lemma 2.4 Die Summe aller Eckengrade in einem Graphen beträgt 2e, alson∑

i=1

d(vi) = 2e.

Beweis Geht von einer Ecke vi eine Kante aus, so muss sie gemäÿ De�nition in einer Ecke vj enden,wobei i = j zugelassen wird (Schlinge). Wir besuchen jede Ecke und summieren die Anzahl derausgehenden Kanten (= Eckengrad). Es gibt zwei Fälle für eine Kante, welche von einer beliebigenEcke ausgeht: a) die gerade gezählte Kante ist eine Schlinge. Dann wird die Kante gemäÿ obigerBemerkung doppelt gezählt. b) die Kante ist keine Schlinge, endet daher in einer anderen Ecke, wo sieebenfalls noch einmal gezählt wird (oder schon gezählt worden ist). In jedem der beiden Fälle wird dieKante genau zweimal gezählt, also wird jede Kante genau zweimal gezählt, woraus die Behauptungfolgt. �

In Abb. 3 ergibt die Summe der zuvor aufgeschriebenen Eckengrade 3+4+4+2+1+0+1+1 = 16also wie behauptet die doppelte Anzahl der Kanten.

Lemma 2.5 Der durchschnittliche Eckengrad d einer Ecke in einem allgemeinen Graphen beträgt

d =2e

n.

Beweis: Die Summe aller Eckengrade in einem planaren Graphen beträgt (siehe oben) 2e. Damit hatjede der n Ecken durchschnittlich einen Eckengrad von 2e/n. �

Lemma 2.6 Die durchnittliche Anzahl von Kanten f eines Gebietes in einem planaren Graphenbeträgt

f =2e

f.

11


De�nition 2.6 Wir de�nieren fk als die Anzahl der Gebiete, welche von genau k Kanten begrenztwerden. Liegt dabei ein und dasselbe Gebiet auf beiden Seiten einer Kante , so wird die Kante doppeltgezählt.

Beispiele:

• In einem Graphen, welcher nur aus einer Kante besteht, wird das Auÿengebiet aufgrund derobig beschriebenen doppelten Zählung von zwei Kanten anstatt von einer Kante begrenzt, alsogilt f2 = 1.

• In Abb. 5 wird g1 von 5 Kanten begrenzt, g2 von 3, g3 von 3, und das ungebrenzte Gebiet g4

aufgrund der doppelten Zählung von e1,2 von 8. Es ist also f1 = f2 = 0, f3 = 2, f4 = 0, f5 = 1,f6 = f7 = 0, f8 = 1.

Beweis: Die Gesamtanzahl an Gebieten beträgt nach obiger De�nition f = f1 +f2 +f3 +f4 + . . .. DieKanten des Graphen können wir jetzt durch Aufsummieren der begrenzenden Kanten aller Gebietezweimal abzählen:

2e = f1 + 2f2 + 3f3 + 4f4 + . . . (1)

Diese Summe der begrenzenden Kanten aller Gebiete dividiert durch die Anzahl der Gebiete liefertnun die durchschnittliche Kantenanzahl pro Gebiet, also f = 2e/f. �

2.5 Historische Entwicklung

In einem Brief an Christian Huygens drückte Gottfried W. Leibnitz 1670 seine Unzufriedenheit über dieUnzulänglichkeiten der Algebra aus ([15], S.1), da sie sinnngemäÿ weder die kürzesten Beweise, nochdie schönsten Konstruktionen in der Geometrie liefere. Aus diesem Grunde würde eine �neue Art derAnalysis� benötigt, die sich mit �Position� beschäftigt, so wie sich die Algebra mit �Gröÿen� beschäftigt.Dieses Gebiet, welches heute als Topologie bezeichnet wird, entwickelte sich nur langsam, wie CarlFriedrich Gauÿ1833 notierte: �Über diese Geometrie der Position, welche Leibnitz [...] begründete,wissen und besitzen wir, nach eineinhalb Jahrzehnten, nur sehr wenig mehr als nichts� ([15], S.1).Eines der (wenigen) Erkenntnisse, welche von Gauss hier angesprochen werden, werden im Folgendenausgeführt.

2.5.1 Leonhard Euler und das Königsberger Brückenproblem

Leonhard Euler's Studium an dieser neuartigen Geometrie gipfelte in einem einzigen Artikel, wel-cher als der Grundstein für die moderne Graphentheorie gilt, in dem er das berühmte KönigsbergerBrückenproblem mathematisch formulierte und löste (siehe Abb. 13).

Das Problem, das sich Leonhard Euler 1737 stellte, ist wie folgt formuliert (vgl. [15], S.2, und [23],S.72):

Ist es möglich einen Weg durch die Stadt zu �nden, bei welchem man jede der siebenBrücken einmal und nur einmal überquert? Und falls ja, ist sogar ein Rundweg möglich,bei dem man wieder zum Ausgangspunkt zurückkehrt?

Euler löste das Problem, indem er zuerst die Stadtkarte durch ein einfacheres Diagram ersetzte, in demnur die wichtigsten Bestandteile eingezeichnet sind. Diese entsprechen in der modernen Graphentheorieden Ecken für die vom Wasser getrennten Stadtteile und Kanten für die die Stadtteile verbindendenBrücken (Abb. 14).

Euler-Weg, Euler-Kreis, eulerscher Graph:Für die folgende De�nition vgl. [23], S.72, sowie [15], S.5 und S.11:

12


Abbildung 13: Eine alte Stadtansicht von Königsberg, mit eingezeichnetem Flussverlauf des Pregelssowie den sieben von Euler betrachteten Brücken. Entnommen von [5].

v1

v2

v3

v4

Abbildung 14: Die graphentheoretische Darstellung der durch Brücken verbundenen Stadtteile.

De�nition 2.7 Ein Euler-Weg in einem Graphen ist ein Weg, welcher jede Kante genau einmalenhält. Ein Euler-Kreis (Euler-Zyklus, Euler-Tour) ist ein ein Euler-Weg, in dem Start- und Endeckeidentisch sind. Enthält ein Graph eine Eulertour, so nennt man ihn eulersch.

Satz 2.1 Ein zusammenhängender Graph besitzt genau dann einen Euler-Kreis, wenn der Grad al-ler Ecken gerade ist. Ein zusammenhängender Graph besitzt genau dann einen Euler-Weg, wenn erhöchstens zwei Ecken mit ungeradem Eckengrad besitzt.

Beweis: Siehe [23], S.73.

Beispiele: Der in Abb. 14 dargestellte Graph enthält keinen Euler-Kreis, da nicht jede Ecke geradenEckengrad besitzt. Ebensowenig besitzt er einen Euler-Weg, da jede Ecke ungeraden Eckengrad besitzt.Der Graph in 15 a) besitzt einen Euler-Weg (höchstens zwei Ecken mit ungeradem Eckengrad), aberkeinen Euler-Kreis. Der Graph in 15 b) besitzt einen Euler-Kreis und ist daher eulersch.

2.5.2 Der Vier-Farben Satz

Für diesen Abschnitt vgl. ([23], S.76�) und ([22], S.326-339). Viele in der Praxis auftauchenden Pro-bleme kann man darauf zurückführen, dass man in einem entsprechend de�nierten Graphen eine Auf-teilung (Partition) der Eckenmenge �ndet, so dass Kanten nur noch zwischen Ecken in verschiedenenKlassen der Partition verlaufen (wie es zum Beispiel in bipartiten Graphen der Fall ist). Diese Parti-tionen von Ecken kann man gut visualisieren, indem man jeder Partition eine andere Farbe zuordnet,

13


a) b)

Abbildung 15: a) Ein Graph welcher einen Euler-Weg, aber keinen Euler-Kreis besitzt. b) Ein Graphwelcher einen Euler-Kreis besitzt (eulersch).

also die Ecken einfärbt. Im Mobilfunk erhält man so beispielsweise eine Zuordnung von Frequenzenzu Sendern, im Compilerbau eine Zuordnung von Variablen auf Register des Prozessors.

Ein klassisches Graphfärbeproblem ist das Färben von Landkarten, bei dem aneinandergrenzendeLänder nicht dieselbe Farbe bekommen dürfen. Hierbei nimmt man an, dass das Gebiet eines jedenLandes zusammenhängend ist, und dass Länder die nur in einem einzigen Punkt aneinanderstoÿen,gleich gefärbt werden dürfen. Das Färben solcher Landkarten entspricht dem Färben planarer Graphen:Repräsentiert man jedes Land durch eine Ecke und verbindet zwei Ecken genau dann durch eine Kante,wenn die entsprechenden Länder eine gemeinsame Grenze haben (Dualisierung), so erhält man einenplanaren Graphen, in dem jede Ecke eine Farbe besitzt. Nach dem Vier-Farben Satz genügen für jedenplanaren Graphen nur vier Farben (Abb. 16).

Abbildung 16: Eine Landkarte welche beweist dass man mindestens vier Farben benötigt, sodass keinezwei banchbarten Länder dieselbe Farbe erhalten. Der dualisierte planare Graph verbindet Eckenunterschiedlicher Farbe durch gestrichelte Kanten.

Historisch geht das Problem bis ins 19. Jahrhundert zurück: der Teilzeitmathematiker Francis Gu-thrie stellte sich im Oktober 1852 beim Bemalen einer Karte der britischen Grafschaften (Abb. 17) dieFrage, ob vier Farben zum Färben einer beliebigen Landkarte immer ausreichend sind. Sein BruderFrederick, Student am Londoner University College, legte daraufhin das Problem seinem ProfessorAugustus de Morgan, welcher wiederum den groÿen irischen Mathematiker und Physiker William Ro-wan Hamilton versuchen lieÿeine Landkarte zu entwerfen, welche mindestens fünf Farben benötige.Er, wie auch Hermann Minkowski und viele andere später scheiterten an dem Problem, indem sieentweder falsche Gegenbeispiele (Landkarten von denen behauptet wurde sie benötigten mindestensfünf Farben) oder falsche Beweise lieferten. Scheinbar richtige Beweise wurden immer wieder durchGegenbeispiele als solche entlarvt, was den berühmten Wissenschaftsjournalisten Martin Gardner 1975

14


dazu veranlasste, als Aprilscherz eine komplexe Karte zu präsentieren, welche scheinbar mindestensfünf Farben benötige (Abb. 18).

Abbildung 17: Francis Guthrie stellte fest, dass er die Karte der britischen Grafschaften mit nur vierFarben färben konnte, ohne dass er für benachbarte Grafschaften dieselbe Farbe benutzen musste([22], S.327).

Abbildung 18: Ein Aprilscherz von Martin Gardner: er behauptete diese Karte könne nur mit min-destens 5 Farben gefärbt werden ([22], S.331).

Lange also wurde nur vermutet, dass für das Färben von Landkarten vier Farben immer ausreichen,aber 1976 konnte dann dieses Problem von Kenneth Appel und Wolfgang Haken von der UniversitätIllinois gelöst werden.

15


Ihr Beweis ist sehr aufwändig und besteht aus einem theoretischen Teil, in dem das allgemeineProblem auf endlich viele (genau 1482) Teilprobleme reduziert wird, und einem Computerprogramm,das daraufhin alle diese endlichen Fälle überprüft. Dieser computergestützte Beweis wurde allerdingsaufgrund der Unmöglichkeit ihn manuell zu veri�zieren zunächst nicht von allen Mathematikern ak-zeptiert. Von der Vorgehensweise von Appel und Haken inspiriert rief der Computerwissenschaftlerden mit 100 000 Dollar dotieren Leibnitz-Preis aus für das erste Computerprogramm, welches einenSatz aufstellt der �tiefgreifende Auswirkungen auf die Mathematik� hat. Jedenfalls stellte das Vierfar-benproblem die Mathematik-Gesellschaft vor die Herausforderung, den Begri� des mathematischenBeweises neu zu überdenken.

3 Euler'sche Polyederformel

Diese von Leonhard Euler entwickelte Formel liefert eine Beziehung zwischen der Anzahl der Ecken,Kanten und Flächen eines planaren Graphen. Das Resultat schickte er 1750 in einem Brief, der keinenvollständigen Beweis enthielt, an seinen Freund Goldbach. Später wurde die Formel auf mehrere Artenbewiesen, wobei hier der nachfolgende Beweis von Karl Georg Christian von Staudt (1847) gewähltwurde. Dieser verzichtet auf die vollständige Induktion und löst dies über die Geometrie der Lage unddessen Selbstdualismus. ([7], S.167 f)

Satz 3.1 Die Eulersche Polyederformel. Für jeden zusammenhängenden ebenen Graphen G mitn Ecken, e Kanten und f Gebieten gilt

n− e + f = 2. (2)

Beweis: Sei T die Kantenmenge des aufspannenden Baumes und Edie Kantenmenge vom Graphen, somit sei T ⊆ E. Daher ist T ein

Abbildung 19: Ein ebenerGraph G: n = 6, e = 10, f = 6

minimaler Untergraph, der alle Ecken von G verbindet.Der Graphenthält keinen Kreis wegen der Minimalitätsannahme ,d.h. er wurdeauf einen einfachen Graph reduziert.Als nächstes benötigt man den Dualgraphen G∗ von G: Für die Kon-struktion legt man in jedes Gebiet von G eine neue Ecke (dabei zähltauch die Fläche um den Graphen herum als ein Gebiet). Je zweibenachbarte Ecken (zwei Gebiete, die durch eine gemeinsame Rand-kante getrennt werden) werden durch eine Kante von G∗ verbunden.Gibt es mehrere gemeinsame Randkanten, so zeichnet man mehrere Verbindungskanten in den Dual-graphen G∗ ein. (Es können Mehrfachkanten auftreten, auch wenn der ursprüngliche Graph G einfachist.)

Die Menge T ∗ ⊆ E∗ sind diejenigen Kanten im Dualgraphen, die den

Abbildung 20: Duale aufspan-nende Bäume in G und in G∗

Kanten E\T entsprechen. T ∗ verbindet alle Gebiete, weil T keineKreise enthält und umgekehrt hat T ∗ keinen Kreis, da sonst einigeEcken von G nicht mit anderen Ecken verbunden wäre (T ist ein auf-spannender Untergraph und die Kanten von T und T ∗ kreuzen sichnicht). Somit ist auch T ∗ ein aufspannender Baum für G∗.

Bei jedem Baum ist die Eckenanzahl um eins gröÿer als die Anzahlder Kanten (siehe Lemma 2.2).Dies zeigt man dadurch, indem maneine Ecke als "Wurzel' auswählt und sich von dieser auf allen Kanten "wegbewegt'. Dies liefert eineBijektion zwischen den Kanten und der Menge aller Ecken, auÿgenommen der Wurzel, indem wir jederKante eine Endecke zuordnen, zu der sie hinzeigt. Somit hat der Baum T gleich n = eT +1 Ecken undder Dualbaum T ∗ hat f = n∗ = eT ∗ +1 Ecken. (Die Ecken im Dualbaum entsprechen den Flächen im

16


originalen Graphen G.) Addiert man beide Gleichungen so erhält man

n + f = (eT + 1) + (eT ∗ + 1) = (eT + eT ∗) + 2 = e + 2 �

4 Platonische Körper

4.1 Geschichtliches

Ein paar Platonische Körper waren schon bei den alten Ägyptern bekannt, aber durch Platon, derwie viele grichischen Philosophen nach den Grundbausteinen der Welt suchte, wurden sie zum erstenMal bekannt. Er baute sie in seine Philosophie ein und beschrieb sie in seinem Werk Timaios. JedemKörper ordnete er ein Element des (platonischen) Weltbildes zu:

• Erde ⇔ Hexaeder

• Wasser ⇔ Ikosaeder

• Feuer ⇔ Tetraeder

• Luft ⇔ Oktaeder

• Äther oder Quintessenz ⇔ Dodekaeder

Abbildung 21: die fünf Platonischen Körper [2]

Auch Euklid beschäftigte sich mit diesen regelmäÿigen Polyedern. In XIII. Buch der Elemente �ndetman eine genaue Konstruktionsbeschreibung und einen Beweis, dass es nicht mehr von diesen Körperngeben kann.Wir stellen uns auch die Frage: "Warum gibt es nur fünf Platonische Körper?"

4.2 Wiederholung: Polyeder

Unter einem Polyeder wird ein Körper verstanden, dessen Ober�ächen aus einer Anzahl polygonalerFlächen besteht. Dieser ist einfach, sofern er keine Löcher besitzt, d.h. sich stetig in eine Kugelober-�äche formen lässt. Angenommen es gibt zwei Punkte auf dem Polyeder, dessen Verbindungsstreckeden Körper schneidet, so spricht man von einem nicht konvexen Körper. Anders gesagt: Verläuft dieStrecke alle Punktepaare des Körpers im Inneren, so ist er konvex. Und ein regulärer Polyeder bestehtaus regulären Polyonen, d.h. alle Seiten sind gleich lang und die Innenwinkel sind gleich groÿ.(vgl.[11],S.181 f)

Bemerkung: Jeder Polyeder lässt sich als planarer Graph darstellen. Man beginnt mit einem Punktund zeichnet alle benachbarten Punkte und deren Verbindungslinien ein. Zum Schluss wird eine Flächedes Polyeders übrig bleiben, die dann das unbegrenzte Gebiet bildet.

17


Abbildung 22: Die Bezeihung zwischen einem (konvexen) Polyeder und einem planaren Graphen ([12],S.237).

4.3 Zwei Beweise

Der erste Beweis [17] ist sehr anschaulich und eher intuitiv, als mathematisch korrekt. Dennoch darfman die Wirkung solcher präformalen Beweise nicht unterschätzen. Sie sind als Au�ockerung, Einstiegin ein Thema oder als Gegensatz zu der strengen mathematischen Beweisführung, die man eher demBeweis 2 ([11], S.183 f) zuschreiben darf, gut geeignet.

Lemma 4.1 Es gibt nur 5 Platonische Körper.

Beweis 1: Um eine Polyederecke bilden zu können, braucht man mindestens drei Flächen und dieInnenwinkelsumme muss kleiner wie 360◦ sein. Beträgt der Innenwinkel genau 360◦ so be�ndet mansich in der Ebene und ist dieser gröÿer, so entsteht kein konvexer Polyeder mehr.Stoÿen drei Dreiecke zusammen, so erhält man eine Tetraederecke mit einem Innenwinkel von 180◦

(= 3 · 60◦). Vier Dreiecke (4 · 60◦ = 240◦) ergeben eine Oktaeder- und fünf (5 · 60◦ = 300◦) eineIkosaederecke. Fügt man weiter Dreiecke hinzu so erhöht sich die Innenwinkelsumme auf 360◦ undmehr.

3 · 60◦ 4 · 60◦ 5 · 60◦

Abbildung 23: Bildung einer Tetraeder-, Oktaeder- und Ikosaederecke

Benutzt man ein Quadrat als regelmäÿiges Ausgangspolygon, so gibt es nur eine Möglichkeit einePolyederecke zu bilden (3 · 90◦ = 270◦) und es entsteht ein Hexaeder (Würfel). Für den Dodekaederverwendet man ein regelmäÿiges Fünfeck 108◦ mit einem Innenwinel von 324◦ (= 3 · 108◦).

Für weitere regelmäÿige Polygone (Sechseck, Siebeneck,...) kann man keine konvexen Körper erzeugen.Im speziellen ergeben sechs gleichseitige Dreiecke, vier Quadrate oder drei regelmäÿige Sechsecke eineParkettierung in der Ebene.

Beweis 2: Da platonische Körper reguläre Polyeder sind, die f Flächen besitzen und aus regulärenVielecken bestehen, kann man die Kanten einmal nach den Ecken abzählen. Jede Ecke hat denselbenEckengrad und wegen Lemma 2.4 folgt:

n · d(vi) = 2e

18


3 · 108◦3 · 90◦

Abbildung 24: Bildung einer Hexaeder- und einer Dodekaederecke

n = 2e/d(ni) (3)

Nun werden die Kanten nach den Flächen abgezählt.

fk · f = 2e

f = 2e/fk (4)

Nun setzt man (3) und (4) in die Eulersche Formel (2) ein.

2e

d(n)− e +

2e

fk= 2

1d(n)

+1fk

=12

+1e

Bevor man alle positiven Zahlentripel, die die Gleichung lösen, sucht, beachtet man zuerst die An-fangsbedingungen, die die Eigenschaften eines Polyeders erfüllen. Um eine Ecke zu bilden brauchtman mindestens drei Flächen, wobei dann dies drei Kanten bilden. Somit ist der Eckengrad d(n) ≥ 3.Das gleiche Prinzip gilt auch für die Kanten der Polygone. Die kleinste Fläche, die dadurch gebildetwerden kann, ist das Dreieck, welches drei Kanten besitzt (fk ≥ 3). Die letzte Voraussetzung sei, dassd(n), fk 6= 4 sind, denn sonst tritt auf der linken Seite der Gleichung 1/2 auf und auf der rechten Seitezählt man zu 1/2 etwas Positives hinzu, da es mindestens eine Ecke geben muss.Um alle Möglichkeiten zu erhalten, hält man einen der beiden Variablen d(n) oder fk konstant mit 3fest und erhöht den anderen, ebenfalls mit 3 beginnend, jeweils immer um 1 und berechnet schlieÿlichdie Kantenanzahl e.

für d(n) = 3 für fk = 31fk− 1

6 = 1e

1d(n) − 1

6 = 1e

→ fk kann 3,4 oder 5 sein → d(n) kann 3,4 oder 5 sein→ e = 6, 12, 30 → e = 6, 12, 30

Über Rückeinsetzen in Gleichung (3) und (4) erhält man die gewünschte Ecken- und FlächenanzahlTabelle 2 (Aufschlüsselung der Ecken,Kanten und Flächen zu den jeweiligen Figuren)

Anzahl der Ecken Anzahl der Kanten Anzahl der Flächen Regulärer Polyeder

4 6 4 Tetraeder8 12 6 Hexaeder6 12 8 Oktaeder20 30 12 Dodekaeder12 30 20 Ikosaeder

19


4.4 Anwendung: Fuÿball

Ein bekanntes Beispiel, an dem man die Eulersche Polyederformel verwenden kann, ist der Fuÿball,der aus zusammengenähten Fünf- und Sechsecken besteht. Dabei stoÿen in jeder Ecke ein Fünfeckund zwei Sechsecke zusammen. Wieviele Fünf- bzw. Sechsecke braucht man dazu? [1]

Abbildung 25: Zwei Fuÿbälle, links eine geometrische und rechts eine naturgetreue Nachbildung einsFuÿballs [3]

Beweis: Wir bezeichnen N als die Eckenmenge, P die Menge aller Pentagone und H die Menge allerHexagone. Die jeweiligen Kleinbuchstaben bezeichneen deren Anzahl, bzw. eingestrichene Kleinbuch-staben beziehen sich auf ein Element der Menge. Da man auch das Netz eines Fuÿballes zeichnenkann handelt es sich um einen planaren Graphen und somit gilt die Eulersche Polyederformel, dieman für diesen speziellen Fall etwas anders anschreibt. Die Gesamt�äche besteht nun aus der Summeder Pentagone und der Hexagone (f = p + h). Somit gelangt man zur Gleichung

n− e + p + h = 2 (5)

Die folgende Aussage liefert uns eine weiter Gleichung:Jede Ecke des Körpers ist Teil eines Pentagons, welches fünf Ecken hat.

#{(p′, n′) ∈ P ×N |n′ ∈ p′

}=

∑p′∈P

#{n′ ∈ N |n′ ∈ p′

}︸︷︷︸=5

= 5p

=∑n′∈N

#{p′ ∈ P |n′ ∈ p′

}︸︷︷︸=1

= n

5p = n (6)

Bemerkung: Gesucht sind die Anzahl aller Paare (Pentagonecke, Ecke) für die die Ecke in einerPentagonecke liegt. Dabei betrachtet man zum einen nur ein Pentagon und zählt die Ecken ab undsummiert im Anschluss über alle Pentagone , zum anderen man nimmt eine Ecke aus der Eckenmen-ge, prüft wieviele Ecken von verschiedenen Pentagonen eintre�en und summiert schlieÿlich über alleEcken. Nun hat man die Anzahl aller Paare auf zwei verschiedenen Möglichkeiten beschrieben undsetzt sie gleich. Genau die gleiche Vorgehensweise verwendet man bei den Hexagonen.

Beweis Fortsetzung: An jeder Ecke be�nden sich zwei Hexagone, welches jeweils aus sechs Ecken

20


besteht.

#{(h′, n′) ∈ H ×N |n′ ∈ h′

}=

∑h′∈H

#{n′ ∈ N |n′ ∈ h′

}︸︷︷︸=6

= 6h

=∑n′∈N

#{h′ ∈ H|n′ ∈ h′

}︸︷︷︸=2

= 2n

6h = 2n (7)

An jeder Ecke stoÿen drei Kanten zusammen. (siehe Lemma 2.4)

3n = 2e (8)

Nun fasst man Gleichung(4),(5),(6)und (7) zu einem Gleichungssystem zusammenfassen und berech-net, da dieses Gleichungsystem eindeutig bestimmt ist, die einzelnen Variablen. (Diese Rechenschritteseien dem kundigen Leser selbst überlassen.) Somit erhält man einen Fuÿball mit 60 Ecken, 90 Kanten,12 (schwarzen) Pentagonen und 20 (weiÿen) Hexagonen.

Abbildung 26: vom Ikosaeder zum Ikosaederstumpf [4]

Bemerkung: Der Ikosaederstumpf gehört zu der Klasse der Archimedischen Körper, von denen es 13gibt. Graphisch lässt sich dieser konstruieren, indem man alle Ecken abschneidet. Der Schnitt mussvon jedem Eckpunkt aus auf einem Drittel mit diesem verbundenen Seitenkante angesetzt werden.Macht man das nicht so bekommt man keine regelmäÿigen Polygone (Sechsecke) und es erfüllt dieDe�nition eines Archimedischen Körpers nicht mehr.

5 Weitere Beweise mithilfe der Polyederformel

5.1 K5 ist nicht planar

Mithilfe der Euler'schen Polyederformel ist es einfach zu beweisen, dass der vollständige Graph mitEckenanzahl 5 nicht planar sein kann, dass also jede Einbettung in die Ebene (auf eine Kugel) Kan-tenüberschneidungen besitzen muss. Dieser Graph werde im Folgenden mit K5 bezeichnet. Der Beweiswird indirekt geführt.

Satz 5.1 Der vollständige Graph K5 ist nicht planar.

Beweis:Wir nehmen also an, dass K5 planar sei. Dann gilt die Euler'sche Polyederformel n−e+f = 2.Nach Voraussetzung hat der Graph Eckenanzahl 5, also ist n = 5. Also ergibt sich für die Kantenanzahl

e =(

52

)= 5·4

2 = 10. Somit ist f = e + 2 − n = 7. Da gemäÿ Abschnitt 2.4 f = 2ef = 20

7 < 3,

ist also die durchschnittliche Kantenanzahl eines Gebiets kleiner 3. Daraus folgt, dass es mindestens

21


ein (begrenztes) Gebiet gibt, welches durch höchstens zwei Kanten begrenzt wird. (Das Auÿengebiethat hier jedenfalls mehr als 3 Kanten.) Dies wiederum bedeutet eine von 2 Möglichkeiten: a) dasses ein Eckenpaar geben muss, zwischen welchem 2 Kanten verlaufen, also von Ecke vi nach vj undeine Kante von vj nach vi; oder b) es gibt eine Schleife (eine Kante von einer Ecke zu sich selbst).Beide Möglichkeiten stehen im Widerspruch zur De�nition eines vollständigen Graphen. Also kanndie Planaritätsannahme nicht korrekt sein. �

5.2 K3,3 ist nicht planar

Der folgende Beweis läuft entlang denselben Argumentationslinien wir der Beweis des K5.

Satz 5.2 Der vollständig bipartite Graph K3,3 ist nicht planar.

Beweis: Angenommen, K3,3 wäre planar. Dann gilt n− e + f = 2. Es gilt nach Voraussetzung n = 6,sowie e = 3 · 3 = 9. Also ist f = e + 2 − n = 5. Für die durchschnittliche Kantenzahl eines Gebietesgilt wieder f = 2e

f = 185 < 4. Es gibt also mindestens ein Gebiet, welches weniger als 4 Kanten

besitzt. Das Auÿengebiet kann wieder wie oben ausgeschlossen werden, da es jedenfalls mehr als 4Kanten besitzt. Ein begrenztes Gebiet in einem bipartiten Graphen ist aber in jedem Fall ein Zykluswelcher mindestens 4 Ecken, und damit mindestens 4 Kanten besitzt. Somit herrscht ein Widerspruchzur Behauptung, es gäbe ein Gebiet mit weniger als 4 Kanten, weswegen die Planaritätsannahme zuverwerfen ist. �

5.3 Maximaler Eckengrad, maximale Kantenzahl

Zwei weitere Aussagen wollen wir hier beweisen, welche sich aus dem doppelten Abzählen von Kanten(siehe Abschnitt 2.4) ergeben. Als Voraussetzung für beide Aussagen sei G = (V,E) ein einfacherzusammenhängender planarer Graph mit n ≥ 3.

Lemma 5.1 G hat (mindestens) eine Ecke mit einem Eckengrad welcher nicht gröÿer als 5 ist. (For-mal: es gibt ein v ∈ V mit d(v) ≤ 5.)

Beweis: Da G einfach ist, enthält G keine Mehrfachkanten. Deshalb und wegen n ≥ 3 ist jedesGebiet (auch das Auÿengebiet) von mindestens drei Kanten begrenzt1. Also ist f1 = f2 = 0. DieGesamtanzahl der Gebiete ist also gegeben durch f = f3 +f4 +f5 + . . .. Wegen Gleichung (1) gilt aberauch 2e = 3f3 + 4f4 + 5f5 + . . .. Durch Multiplizieren ersterer Gleichung mit der Zahl 3 und Abzugvon der zweiten Gleichung erhalten wir folgende Ungleichung:

2e− 3f ≥ 0. (9)

Jetzt setzen wir indirekt fort: angenommen, jede Ecke hätte Eckengrad ≥ 6. Wir de�nieren nk als dieAnzahl der Ecken mit Eckengrad k. Also können wir die Gesamtanzahl der Ecken wie folgt zählen:

n = n6 + n7 + n8 + . . . . (10)

Aufsummieren der Eckengrade ergibt gemäÿ Lemma 2.4

2e = 6n6 + 7n7 + 8n8 + . . . , (11)

woraus wir durch Multiplikation von Gleichung 10 mit der Zahl 6 und anschlieÿendem Abziehen vonletzterer Gleichung 2e − 6n ≥ 0 schlieÿen können. Beide Ungleichungen werden schlieÿlich geschicktmiteinander kombiniert:

1(Hinweis: in ([7],S.69) wird die Voraussetzung n ≥ 3 o�enbar implizit gemacht.

22


I : 2e− 3f ≥ 0II : 2e− 6n ≥ 0I ′ : 4e− 6f ≥ 0

I ′ + II : 6e− 6n− 6f ≥ 0⇔6(e− n− f) ≥ 0⇔

e− n− f ≥ 0⇔e ≥ n + f,

was der Euler'schen Polyederformel wegen n − e + f = 2 ⇔ e = n + f − 2 widerspricht, weshalb dieAnnahme falsch sein muss, und wir die Behauptung folgern können. �

Lemma 5.2 G hat höchstens 3n− 6 Kanten. (Formal: |E| = e ≤ 3n− 6.)

Beweis: Aus der Eulerschen Polyederformel leiten wir eine Darstellung von 3f ab:

n− e + f = 2⇔f = 2− n + e⇔

3f = 6− 3n + 3e.

Wie in obigen Beweis gilt bei n ≥ 3 die Gleichung ??: 2e − 3f ≥ 0. Durch Umformen, Einsetzen für3f , und abermaliges Umformen resultiert die Behauptung:

2e ≥ 3f ⇔2e ≥ 6− 3n + 3e⇔

3n− 6 ≥ e. �

6 Anwendungen in der Informatik

Bäume für Suche und Sortierung: Vor allem in der Informatik spielen Suchbäume eine enormwichtige Rolle, wie z.B. Binärbäume, Heaps, Rot-Schwarz-Bäume, AV L-Bäume oder 2 − 3-Bäume([21], S.270f.). In modernen Datenbanksystemen sind B-, B∗- bzw. B+, R-Bäume ([16], S.207-220)als Grunddatenstrukturen implementiert, welche Sortier- sowie Suchprobleme mit bewiesenermaÿenhöchstmöglicher Zeite�zienz lösen. Dabei spielt vor allem der Grad der Balanziertheit (Ausgegli-chenheit) und damit verbunden die maximale Höhe eines balanzierten Binärbaums die entscheidendeRolle.

Soganannte Quadtrees bzw. Octrees werden verwendet, um Objekte im 2- bzw. 3-dimensionalenRaum schnell aufzu�nden, was für Computergra�k (z.B. zur Kollisionserkennung in Computerspielen),aber auch für GIS2-Anwendungen von Bedeutung ist (vgl. [12], S.293-203).

Syntaxbäume: Im Compilerbau repräsentiert ein durch den Parser generierter Syntax-Bäum denAufbau des Programmcodes in einer (höheren) Programmiersprache ([21], S.359) und bildet den Aus-gangspunkt für die weitere Übersetzung in Maschinencode.

2Geographic Information Systems

23


Kürzeste Pfade in gewichteten Graphen: Das Problem, den �kürzesten� Pfad (also den Pfadwelcher die Gewichte der Kanten minimiert) zwischen zwei Ecken in einem gewichteten Graphen zuherauszu�nden, �ndet z.B. in Computernetzwerken und Reiseroutenberechnungen breite Anwendung.Der Dijkstra-Algorithmus, welcher spätestens aus dem Jahr 1957 stammt ([21], S.520) und für zweibeliebige Knoten den kürzesten Pfad zwischen ihnen ermittelt, ist durch seine Implementierung inRouting-Protokollen einer der berühmtesten und meist-implementiertesten Algorithmen überhaupt[19]. Ähnliche Algorithmen sind der Floyd-Warshall-Algorithmus, welcher in einem Graphen alle kür-zesten Wege berechnet [19], bzw. die A∗-Suche, welche auf dem Prinzip von Dijkstra aufbaut [18].Solche Algorithmen sind nicht darauf beschränkt, tatsächlich eine Distanz zwischen (geometrischen)Punkten der Ebene zu minimieren, sondern können als ganz allgemeine Verfahren zum Lösen vondiversen Optimierungsproblemen angewandt werden, wie im Scheduling oder für Spielstrategieopti-mierung ([21], S.513, und [18]).

Minimaler Spannbaum und Kostenminimierung: Das Problem des minimalen Spannbaumswird mit dem Algorithmus von Kruskal (seit 1956 bekannt) gelöst, oder mit dem Algorithmus vonPrim, welcher auf dem gleichen Prinzip wie der Algorithmus von Dijkstra basiert ([21], S.520). An-wendung �ndet dies z.B. zur Minimierung von Leitungskosten zwischen Telefonanschlüssen, Stroman-schlüssen [19], aber auch in Computernetzwerken sowie zur approximativen Berechnung einer Lösungfür das berühmte Travelling Salesman Problem [14].

Webseiten-Bewertung in Suchmaschinen: Die Google-Websuche (der sogenannte PageRank -Algorithmus) basiert darauf, das Web als Graphen repräsentieren, in dem Ecken (Webseiten) eineBewertung erhalten, welche unter anderem davon abhängig ist, wie viele Kanten (Links) bei ihr ein-gehen. Die tatsächliche Bewertung kann dann (unter diversen Voraussetzungen) durch Lösen eineshochdimensionalen Eigenwertproblems berechnet werden [20].

Spielstrategieoptimierung: Für Spiele wie Tic-Tac-Toe, Schach, Dame, Go oder Vier-Gewinnt,also in Spielen wo abwechselnd gezogen wird, werden sogenannte Spielbäume berechnet. In einemSpielbaum werden, ausgehend von der aktuellen Spielbrettkon�guration, die weiteren möglichen Kon-�gurationen für eine gewisse Anzahl von Zügen vorausberechnet und in einer Baumstruktur abge-speichert. Abhängig von einer sogenannten Bewertungsfunktion, welche für jede Spielkon�gurationbewertet ob sie vorteilhaft ist oder nicht, wird ein Pfad in dem Spielbaum gesucht, welcher (auchfür optimale gegenerische Züge) zu einer möglichst vorteilhaften Kon�guration bzw. zum Sieg führt.Bekannte Algorithmen dieser Art sind Minimax, Negamax und der Alpha-Beta Algorithmus [18].

6.1 Voronoi-Diagramme

Das sogenannte Voronoi-Diagramm einer zweidimensionalen Punktmenge P = {p1, . . . , pn}, pi ∈ R2,i ∈ {1, . . . , n} ist eine planare Unterteilung der Ebene, welcher die Ebene in (polygonale) Gebiete ein-teilt, wobei jeder Punkt pi ∈ P von einem solchen, möglicherweise unbeschränkten Gebiet gi umgebenist (Abb. 27). Das Gebiet gi, Voronoi-Polygon genannt, besitzt dabei die zentrale Eigenschaft, dassjeder Punkt q ∈ gi einen kleineren Abstand zu pi also zu irgendeinem pj , i 6= j, besitzt (vgl. [12],S.147-151). Die Kanten der Voronoi-Polygone gi und gj sind Teile von Streckensymmetralen zwischenden Punkten pi und pj (Abb. 28).Aus Abb. 27 und 28 wird ersichtlich, dass jede Ecke eines Voronoi-Polynoms Eckengrad k ≥ 3 besitzt(ohne Beweis). Dabei ist anschaulicherweise genau dann k > 3, wenn k viele Eingabepunkte auf einemKreis liegen und kein weiterer Eingabepunkt im Inneren dieses Kreises liegt. Für ein Beispiel denkeman sich den Punkt in der Mitte von Abb. 30 weg.

Im Unterschied zu einem ebenen Graphen besitzt das Voronoi-Diagramm unendlich lange Kanten(Strahlen), siehe Abb. 27. Die Kanten der Voronoi-Polygone verbinden Voronoi-Ecken. Das Voronoi-

24


Abbildung 27: Das Voronoi-Diagramm einer Punktmenge teilt die Ebene, so dass alle Punkte innerhalbdes Voronoi-Polygons von pi kleinere Distanz zu pi als zu einem anderen pj (i 6= j) besitzen ([12],S.149).

Abbildung 28: Die Kante e welche den Voronoi-Polygonen von pi und pj gemeinsam ist, ist ein Teilder Streckensymmetrale zwischen pi und pj ([12], S.149). Einfügen eines weiteren Punkts pk führt hierzu weiteren Streckensymmetralen zwischen pj und pk (strichliert), sowie zwischen pi und pk (nichteingezeichnet). Bei drei Punkten schneiden sich also im resultierenden Voronoi-Diagramm alle dreiStreckensymmetralen in einer einzigen Voronoi-Ecke.

Diagramm kann auf einfache Weise zu einem planaren Graphen umgebaut werden, indem man alleunendlich langen Kanten in einer extra hinzugefügten Ecke enden lässt (Abb. 29).

Es stellt sich die Frage, aus wie vielen Ecken und Kanten ein Voronoi-Diagramm besteht. Klarerweisekann ein einzelner Punkt pi von einem Voronoi-Polygon mit höchstens n − 1 Kanten umschlossensein (Abb. 30), was im schlimmsten Fall n(n − 1), also quadratisch viele Kanten bedeuten würde.Mithilfe eines Resultats aus der Eulerformel können wir allerdings zeigen, dass das Voronoi-Diagrammhöchstens 2n− 5 Ecken und 3n− 6 Kanten (also linear viele) besitzt (vgl. [12], S.150). Weiters zeigenwir dass ein einzelnes Voronoi-Polygon im Schnitt höchstens 6 Kanten besitzt.

Satz 6.1 Sei P = {p1, . . . , pn} eine Punktemenge der Ebene mit n ≥ 3 Punkten. Dann besitzt dasVoronoi-Diagramm höchstens 3n−6 Kanten, sowie höchstens 2n−5 Ecken. (Für n = 3 gilt Gleichheit.)

Beweis: Aus dem Voronoi-Diagramm, welches aus nv vielen Ecken und ne vielen Kanten besteht, wirddurch Hinzüfügen einer Ecke v∞ ein planarer Graph erzeugt, welcher nv + 1 viele Ecken und ne vieleKanten besitzt, wie in Abb. 29 illustriert. Sei nun V = {v1, . . . , vnv , v∞} die Menge der Voronoi-Ecken.

25


Abbildung 29: Durch Hinzufügen eines Zusatzpunktes v∞ wird ein Voronoi-Diagramm zu einem pla-naren Graphen, für den die Eulersche Polyederformel gilt ([12], S.150).

Es gilt |V | = nv +1. Wir wissen von Abschnitt 2.4 dass für die Kantenanzahl des Voronoi-Diagrammsgilt:

nv+1∑i=1

d(vi) = 2ne,

wobei v∞ = vnv+1. Nun besitzt jede Ecke eines Voronoi-Diagramms Eckengrad gröÿer oder gleich 3.Also ist die Summe der Eckengrade - welche ja wie bereits gezeigt 2e ist - gröÿergleich dreimal dieEckenanzahl:

nv+1∑i=1

d(vi) ≥ 3(nv + 1)⇔ 2ne ≥ 3(nv + 1).

Dieses Ergebnis notieren wir als Gleichung I:

I : 2ne ≥ 3(nv + 1).

Weiters können wir die Eulerformel anwenden, wobei die Anzahl der Gebiete gleich der Anzahl derEingabepunkte n ist:

II : (nv + 1)− ne + n = 2II ′ : 2(nv + 1)− 2ne + 2n = 4II ′′ : 3(nv + 1)− 3ne + 3n = 6.

Setzen wir die Abschätzung für 2ne aus I in II ′ ein, ergibt sich:

2(nv + 1)− 3(nv + 1) + 2n ≥ 4⇔−nv + 2− 3 + 2n ≥ 4⇔

nv ≤ 2n− 5.

Setzen wir die Abschätzung für 3(nv + 1) aus I in II ′′ ein, ergibt sich:

2ne − 3ne + 3n ≥ 6⇔−ne ≥ 6− 3n⇔

ne ≤ 3n− 6 �

26


Lemma 6.1 Jedes Voronoi-Polygon besitzt durchschnittlich weniger als 6 Kanten.

Beweis: Da jede Kante zu zwei Voronoi-Polygonen gehört, besitzt jedes Voronoi-Polygon nach Satz6.1 im Schnitt 2 · (3n− 6)/n = 6− 12/n Kanten. �

Abbildung 30: Ein einzelnes Voronoi-Polygon kann n − 1 viele Kanten besitzen, aber insgesamt gibtes nicht mehr als 3n− 6 Kanten ([12], S.150).

6.1.1 Nearest Neighbor Probleme:

Angenommen, man möchte zu jedem Punkt pi seien nächsten Nachbarn pj �nden, also denjenigenPunkt pj , der geringste Distanz zu pi aufweist (i 6= j). Für einen einzelnen Punkt müsste man miteiner naiven Vorgehensweise die Abstände zu allen weiteren berechnen, also n− 1 viele. Würde manalso alle paarweisen Distanzen in einer Punktmenge P = {p1, . . . , pn} berechnen, so würde man dabei(n− 1) + (n− 2) + . . . + 3 + 2 + 1 = n(n− 1)/2, also quadratisch viele Berechnungen benötigen.

Hat man hingegen das Voronoi-Diagramm bereits berechnet, so muss man nur noch diejenigenNachbarn, welche Kanten im Voronoi-Polygon von pi bilden, absuchen. Nach obigem Lemma genügenalso im Schnitt 6, also O(1) viele Berechnungen um den nächsten Nachbarn eines einzelnen Punkts pi

zu �nden, bzw. O(n) für die nächsten Nachbarn aller Punkte.

Man kann zeigen ([12], S.159), dass das Voronoi-Diagramm im schlimmsten Fall mit O(n log n) vielenBerechnungen und mit O(n) Speicherverbrauch berechnet werden kann. Diese Laufzeit ist optimal [14],da das Sortierproblem reduzierbar auf die Berechnung des Voronoi-Diagramms ist. (Wäre O(n log n)nicht optimal, gäbe es also einen noch schnelleren Algorithmus zur Berechnung des Vornoi-Diagramms,dann könnte man auch schneller als O(n log n) sortieren, was nicht möglich ist.) Im schlimmsten Fallist es also möglich, in einer Punktmenge alle nächsten Nachbarn mit nur O(n log n) Zeitverbrauch zubestimmen. Bei einer Punktmenge von z.B. n = 10.000 Punkten, entspricht dies einer Reduktion vonca. 50 Millionen (im Falle eines quadratischen Algorithmus) auf nur 40.000 Berechnungen.

6.1.2 Andere Anwendungen

Mithilfe einer Verallgemeinerung des Voronoi-Diagramms für Liniensegmenten - der sogenannten Me-dialen Achse bzw. medial axis - ist es möglich das Problem des polygon o�setting zu lösen: Findein O(n log n) Zeit eine Kurve, welche von einem Ausgangspolygon überall konstanten Abstand - deno�set - besitzt [14]. Weiters wird die mediale Achse verwendet um einerseits Engstellen (sogenanntebottlenecks) in einem Polygon, andererseits Orte wo dem Polygon ein gröÿtmöglicher Kreis einge-schrieben werden kann, aufzu�nden. Siehe Abb. 31 und 32 für Beispiele zur medialen Achse und derenAnwendungen.

27


Abbildung 31: Die mediale Achse - eine Verallgemeinerung eines Voronoi-Diagramms für Polygone -kann dazu verwendet werden, in O(n log n) Zeit eine Kurve welche überall konstanten Abstand zumPolygon besitzt zu erzeugen (die o�set Kurve, hier in rot, entnommen aus [14]).

Abbildung 32: Die mediale Achse dient dazu Engstellen (bottlenecks) aufzu�nden, sowie Orte, wo eingröÿtmöglicher Kreis eingeschrieben werden kann (entnommen aus [14]).

Aufbauend auf dem Voronoi-Diagramm wird auÿerdem durch Dualisierung eine besonders güns-tige Form einer Triangulierung (ein ebener Graph, dessen Innengebiete Dreiecke bilden) berechnet,die sogenannte Delaunay-Triangulierung ([12], S.188-200), welche z.B. für die Erstellung von 3D-Gittermodellen von Landschaftterrains benutzt und im folgenden Abschnitt näher erläutert wird.

6.2 Delaunay-Triangulierung

6.2.1 Landschafts-Modellierung

Gegeben sei eine Punktmenge P = {p1, . . . , pn} in der Ebene. Von diesen Punkten kenne man zudemdie durch Messung gewonnene Höheninformation h(pi) ∈ R. Die Höhe der anderen Punkte der Ebenekennt man nicht. Das Ziel ist es jetzt, eine �Landschaftsmodell� zu erstellen, wo jedem Punkt derEbene eine Höhe zugewiesen wird.

28


Möglichkeit 1: ein Punkt q mit unbekannter Höhe erhält die Höhe seines nächsten gemessenenNachbarn in P . Nachteil: es entstehen nicht-stetige Voronoi-Plateaus (Abb. 33).

Abbildung 33: Eine Landschaft wird modelliert durch Zuweisung der Höhen des nächsten Nachbarnin P ([12], S.184).

Möglichkeit 2: Die Punktmenge wird trianguliert. Die Landschaft wird dann durch Interpolationan den enstandenden 3D-Dreiecken modelliert. Einem Punkt q mit unbekannter Höhe h(p) wird alsodie Höhe des entsprechenden Punktes des Dreiecks über q zugewiesen (Abb. 34).

Abbildung 34: Landschaftsmodellierung durch Triangulierung einer zweidimensionalen PunktmengeP ([12], S.184).

Eine derart modellierte Landschaft könnte z.B. wie folgt aussehen:

Abbildung 35: Landschaftsmodellierung durch Triangulierung ([12], S.183).

29


Der Nachteil hierbei ist dass das entstandene Modell sehr stark von der ursprünglichen Triangulierungabhängt. Schon einzelne Kanten können einen groÿen Unterschied in der modellierten Landschaftausmachen, wie in Abb. 36 illustriert wird.

Abbildung 36: Eine einzige Kante kann für das resultierende Landschaftsmodell eine groÿe Rollespielen. In a) würde ein Berg in der Mitte rechts und links vom Punkt q steil abfallen; in b) hingegenwürde q in einem tiefen Tal liegen ([12], S.183). Das Problem hierbei sind die vielen schmalen Dreiecke,bzw. die kleinen auftretenden Winkel .

Anhand des vorigen Beispiels sieht man, dass eine möglichst gleichmäÿige Triangulierung (eine Trian-gulierung, in denen die Winkel in den Dreiecken nicht zu klein werden, deren Dreiecke also möglichstgleiche Winkel nahe bei 60◦ besitzen) wünschenswert wäre. Die sogenannte Delaunay-Triangulationleistet genau das, wie weiter unten erläutert.

6.2.2 Konstruktion aus dem Voronoi-Diagramm

Die Delaunay-Triangulation entsteht durch Dualisierung des Voronoi-Diagramms: die Punkte pi, wel-che von Voronoi-Polygonen umgeben sind, sind die Ecken der Triangulierung. Teilen sich die Voronoi-Polygone zweier Punkte pi, pj eine Kante e, so wird zunächst eine neue Kante von pi nach pj gezogen,welche e durchquert. Es ensteht ein planarer Graph G (Abb. 37), dessen innere Gebiete jeweis vondrei Kanten begrenzt sind; für den Beweis siehe ([12], S.189).

Abbildung 37: Durch Dualisierung entsteht aus dem Voronoi-Diagramm V or(P ) (gestrichelt) ein neuerplanarer Graph G, welcher in die Delaunay-Triangulierung übergeführt wird ([12], S.188).

30


Aus G wird nun ein PSLG, was nach Fary's Theorem ist möglich ist (siehe oben, Abschnitt 2.2.1).Die resultierende Triangulierung wird in Abb. 38 illustriert.

Abbildung 38: Die aus dem Voronoi-Diagramm entstandende Delaunay-Triangulierung ([12], S.188).

6.2.3 Eigenschaften der Delaunay-Triangulation

Die Delaunay-Triangulierung weist folgende Eigenschaften auf, welche mitilfe des Voronoi-Diagrammsbewiesen werden ([12], S.190f).

1. Sie ist winkeloptimal. Das bedeutet, sie maximiert also von allen möglichen Triangulierungenden kleinsten auftretenden Innenwinkel aller Dreiecke.

2. Im Inneren eines Umkreises eines Delaunay-Dreicks liegt kein weiterer Punkt ∈ P .

3. Der Umkreismittelpunkt eines Delaunay-Dreiecks mit den Punkten {pi, pj , pk} ist die durch denSchnittpunkt der Streckensymmetralen zwischen pi, pj , pk de�nierte Voronoi-Ecke.

4. Sie kann in O(n) Zeit aus dem Voronoi-Diagramm berechnet werden, insgesamt ist die Kon-struktion also ebenso nur in O(n log n).

6.2.4 Weitere Anwendungen

Mithilfe der Delaunay-Triangulation kann mit nur O(n log n) Zeitkomplexität der bezüglich der Kan-tenlänge minimale Spannbaum einer Punktmenge berechnet werden. Hierbei wird der bekannte Algo-rithmus von Kruskal auf die Delaunay-Triangulation angewendet [14].

Weiters ist es möglich, suboptimale Lösungen des Travelling Salesman Problems zu generieren,deren Laufzeit abhängig von der gewünschten Qualität sind.

7 Satz von Pick

De�nition 7.1 Ein konvexes Polygon P ⊆ R2 heiÿt elementar, wenn die Koordinaten seiner Eck-punkte ganzzahlig sind, es aber keine weiteren ganzzahligen Punkte enthält.

Bemerkung: Dies impliziert, dass weder am Rand noch im Inneren des Polygons Punkte aus Z2

enthalten sein dürfen.

Lemma 7.1 Ist eine invertierbare (n × n)-Matrix M ganzzahlig, also ∈ Zn×n, dann ist der Betragihrer Determinante gleich 1, also |det(M)| = 1.

31


Beweis: Sei M ganzzahlig und invertierbar. Dann sind sowohl det(M) als auch det(M−1) ungleich 0.Weiters gilt: 1 = det(I) = det(M ·M−1) = det(M) ·det(M−1), also 1 = det(M) ·det(M−1), und damitdet(M) = 1/det(M−1). Da det(M) Element aus Z ist, folgt dass |det(M)| = |det(M−1| = 1 gilt. �

Satz 7.1 Jedes elementare Dreieck 4 ⊂ R2, welches durch die Punkte {P0, P1, P2} mit Pi ∈ R2

gegeben ist, besitzt den Flächeninhalt 1/2:

A(4) =12.

Beweis: Seien P0, P1, P2 ∈ R2 derart, dass sie ein elementares Dreieck 4 bilden. Jetzt fasse maneine Dreiecksseite (zB die Strecke P1P2) als Diagonale eines Parallelogramms auf, dessen eine Hälftedas Dreieck, die andere die gespiegelte Version des Dreiecks im Mittelpunkt der Diagonale ist (sieheAbb. 39). Da das gespiegelte Dreieck klarerweise elementar ist, ist auch das resultierende Parallelo-gramm elementar. Ebenso ist es möglich, durch �Hintereinanderhängen� der durch die Dreiecksseitengegebenen Vektoren jeden beliebigen Punkt des Gitters Z2 zu erreichen: dies ist deshalb so, weil mandurch nahtloses und paralleles Aneinanderfügen kongruenter Versionen des Parallelogramms die ganzeEbene �p�astern� kann, also jeder Punkt aus Z2 ein Eckpunkt irgendeines Parallelogramms wird (sieheAbb. 40).

Jeder Punkt aus Z2 kann also durch eine ganzzahlige Linearkombination der Vektoren ~v1 = P1−P0,~v2 = P2−P0 gebildet werden, was nichts anderes bedeutet, als dass ~v1 und ~v2 das Gitter Z2 aufspannen.Weiters sind - das Dreieck besitzt ja positive Fläche - ~v1 und ~v2 linear unabhängig. Da Z2 Dimension2 besitzt, folgt, dass B = {~v1, ~v2} eine Basis von Z2 bildet.

P0

~v1

P1

P2

~v2

4

Abbildung 39: Ein elementares Dreick (dunkelgrau), welches durch Spiegelung am Mittelpunkt der(dick hervorgehobenen) Diagonale ein elementares Parallelogramm erzeugt.

Abbildung 40: Elementare Parallelogramme �p�astern� das Gitter. Also bilden die Vektoren, welchedas Parallelogramm aufspannen, eine Basis des Gitters.

32


Der Flächeninhalt des oben konstruierten Parallelogramms ist gleich dem Betrag der Determinantevon M , wobei M die Matrix mit Spaltenvektoren ~v1 und ~v2 ist. Sei jetzt C eine weitere Basis desGitters mit C = {~u1, ~u2}. Dann gibt es eine invertierbare Übergangsmatrix P , welche einen Koordi-natenvektor bezüglich Basis B in einen bezüglich Basis C umwandelt. Da jeder ganzzahlige Vektordurch ganzzahlige Linearkombinationen der Basiselemente dargestellt werden kann, sind sowohl P alsauch die Übergangsmatrix P−1 von C nach B ganzahlig. Für ganzahlige invertierbare Matrizen giltaber nach Satz 7, dass sie betragsmäÿig Determinante 1 besitzen. Also ist der Flächeninhalt des von ~v1

und ~v2 aufgespannten Parallelogramms gleich 1, womit bewiesen ist, dass das betrachtete elementareDreieck 4 Flächeninhalt 1

2 besitzt. �

Satz 7.2 Der Satz vom Pick. Die Fläche eines (nicht notwendigerweise konvenxen) Polygons Q ⊆R2 mit ganzzahligen Ecken ist durch

A(Q) = nin + 12nrd − 1

gegeben, wobei nin und nrd die Anzahlen der ganzzahligen Punkte im Inneren bzw. auf dem Rand vonQ sind.

Beweis: Jedes nicht konvexe Polygon kann durch eine geeignete Tri-angulierung so zerlegt werden, dass alle Gitterpunkte im Inneren nin

Abbildung 41: Triangulierungeines nicht konvexen Polygons

und alle Punkte am Rand nrd verwendet und zu elementaren Drei-ecken zerlegt werden. Auf diesen Beweis wird aber hier nicht nähereingegangen, der interessierten Leser kann dieses Problem im Buch:The book of proofs [7] unter dem Kapitel 28 - das Museumswärter-problem - nachlesen.Die Triangulierung kann als planarer Graph gesehen werden, der dannauÿen ein unbegrenztes Gebiet und (f − 1) Dreiecke mit Flächenin-halt 1

2 hat. Somit ist die Fläche des Polygons A(Q) = 12(f − 1).

Jedes elementare Dreieck des Polygons hat drei Kanten, wobei diesedoppelt gezählt wird, falls sie im Inneren des Polygons liegt (ein), undeinfach gezählt wird, falls diese eine Randkante erd ist. Somit gilt:

3(f − 1) = 2ein + erd

3f − 3 = 2ein + 2erd − erd

f = 2e− 2f − erd + 3f = 2(e− f)− erd + 3

Da jedes Polygon gleich viele (Rand-)Kanten wie (Rand-)Ecken hat (erd = nrd) und unter Anwendungder Eulerschen Polyederformel, bekommen wir somit:

f = 2(n− 2)− nrd + 3= 2n− 4− nrd + 3= 2n− nrd − 1= 2n− 2nrd + nrd − 1

f = 2nin + nrd − 1f − 1 = 2nin + nrd − 2

A(Q) =12(f − 1) = nin +

12nrd − 1 �

Bemerkung: Jedes Polygon hat gleich viele Kanten wie Ecken, da von seiner n-ten Ecke die n-teGerade zum Anfangspunkt zurückkehren muss. Ansonsten wäre das Polygon unvollständig und es istlediglich ein Polygonzug entstanden.

33


n1

e1

n2e2

n3

e3 n4

e4

n5

e5

n6e6

Abbildung 42: Polygon mit 6 Ecken und 6 Kanten

Literatur

[1] http://bernharddietrich.com/uniarchiv/semester2/MfI2/muster10.pdf. 25.03.2010.

[2] Abbildung der fünf Platonischen Körper. http://members.chello.at/gut.jutta.gerhard/

newsletter/newsletter5.htm. 28.05.2010.

[3] Abbildung eines Ikosaederstumpfes. http://de.wikipedia.org/wiki/Ikosaederstumpf.17.04.2010.

[4] Abbildung: vom Ikosaeder zum Ikosaederstumpf. http://www.muenster.org/mauritz/

projekte_in/Mathe_in_5/fuss/anmerk.html. 17.04.2010.

[5] Abbildung zum Königsberger Brückenproblem. http://de.wikipedia.org/wiki/K%C3%

B6nigsberger_Br%C3%BCckenproblem. 06.05.2010.

[6] Paul Adam and Arnold Wyss. Platonische und archimedische Körper, ihre Sternformen undpolaren Gebilde. Verlag Freies Geistesleben, Stuttgart, 1984.

[7] Martin Aigner and Günter M. Ziegler. Das Buch der Beweise. Springer Verlag, Berlin, 2002.

[8] Howard Anton. Lineare Algebra - Einführung, Grundlagen, Übungen. Spektrum AkademischerVerlag, Berlin-Heidelberg, 1994. 3., durchgesehener Nachdruck 2004. Amerikanische Originalaus-gabe bei John Wiley and Sons, Inc., New York.

[9] Norman Biggs. Algebraic Graph Theory. Cambridge University Press, 1993. 2. Ausgabe.

[10] J.A. Bondy and U.S.R. Murty. Graph Theory with Applications. Elsevier Science Publishing,New York, 1976. 5. Druck, 1982.

[11] Richard Courant and Herbert Robbins. Was ist Mathematik? Springer Verlag, Berlin, 1973.

[12] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. ComputationalGeometry - Algorithms and Applications. Springer Verlag, Berlin Heidelberg, 2000. 2nd, revisededition.

[13] Reinhard Diestel. Graph Theory. Springer Verlag, New York, 1997. elektronische Ausgabe, 2000.

[14] Martin Held. Vorlesung Algorithmische Geometrie. Universität Salzburg, Wintersemester2009/2010. Digitale Lehrveranstaltungsunterlagen abrufbar unter http://www.cosy.sbg.ac.at/~held/teaching/compgeo/comp_geo.html.

[15] Janet Heine Barnett. Early Writings on Graph Theory: Euler Circuits and the Königsberg BridgeProblem - An Historical Project . Colorado State University - Pueblo. Abrufbar unter http:

//www.scientificcommons.org/43513817 (nur elektronisch).

[16] Alfons Kemper and Andre Eickler. Datenbanksysteme - Eine Einführung. Oldenbourg Verlag,München, 2001. 4. überarbeitete und erweiterte Ausgabe.

34

http://bernharddietrich.com/uniarchiv/semester2/MfI2/muster10.pdf

http://members.chello.at/gut.jutta.gerhard/newsletter/newsletter5.htm

http://members.chello.at/gut.jutta.gerhard/newsletter/newsletter5.htm

http://de.wikipedia.org/wiki/Ikosaederstumpf

http://www.muenster.org/mauritz/projekte_in/Mathe_in_5/fuss/anmerk.html

http://www.muenster.org/mauritz/projekte_in/Mathe_in_5/fuss/anmerk.html

http://de.wikipedia.org/wiki/K%C3%B6nigsberger_Br%C3%BCckenproblem

http://de.wikipedia.org/wiki/K%C3%B6nigsberger_Br%C3%BCckenproblem

http://www.cosy.sbg.ac.at/~held/teaching/compgeo/comp_geo.html

http://www.cosy.sbg.ac.at/~held/teaching/compgeo/comp_geo.html

http://www.scientificcommons.org/43513817

http://www.scientificcommons.org/43513817


[17] Günter Maresch. Vorlesungsmitschrift zur Vorlesung Darstellende Geometrie. Sommersemester2008, Universität Salzburg.

[18] Martin Müller. Vorlesungsmitschrift zur Vorlesung Heuristische Suche. Sommersemester 2007,Universität Salzburg.

[19] Werner Pohlmann. Vorlesungsmitschrift zur Vorlesung Algorithmen und Datenstrukturen. Som-mersemester 2002, Universität Salzburg.

[20] Michael Revers. Vorlesungsmitschrift zur Vorlesung Lineare Algebra II und Geometrie. Sommer-semester 2009, Universität Salzburg.

[21] Robert Sedgewick. Algorithmen. Pearson Studium, Addison Wesley, Berlin-Heidelberg, 2002. 2.Au�age.

[22] Simon Singh. Fermats letzter Satz - Die abenteuerliche Geschichte eines mathematischen Rätsels.Deutscher Taschenbuch Verlag, München, 2000. 8. Au�age 2003.

[23] Angelika Steger. Dikrete Strukturen 1 - Kombinatorik, Graphentheorie, Algebra. Springer Verlag,Berlin-Heidelberg, 2001.

[24] K. Thulasiraman and M. N. S. Swamy. Graphs: theory and algorithms. Wiley, New York, 1992.

[25] Lutz Volkmann. Fundamente der Graphentheorie. Springer, New York, 1996.

35

Documents

Die Eulersche Polyederformel und Anwendungen