Platonische Körper (Graphentheoretische Eigenschaften)

Graphentheoretische Eigenschaften

Alle Graphen der platonischen Körper sind reguläre Graphen, weil an jeder Ecke dieser Polyeder die gleiche Anzahl von Kanten zusammentrifft. Der kürzeste Zyklus, die sogenannte Taillenweite, ist gleich der Anzahl der Ecken der Seitenflächen des betreffenden platonischen Körpers.

Der graphentheoretische Durchmesser und der graphentheoretische Radius stimmen überein, weil alle Knoten jeweils graphentheoretisch äquivalent zueinander sind und sich mit Hilfe von Permutationen zusammen mit dem Graphen auf einen isomorphen Graphen abbilden lassen. Daraus folgt, dass alle Knoten dieselbe Exzentrizität haben und sowohl zum Rand als auch zum Zentrum des Graphen gehören.

Netze

Platonische Körper haben wie alle Polyeder verschiedene Netze (siehe Übersicht oben). Es gibt nämlich verschiedene Möglichkeiten, ein hohles Polyeder durch Aufschneiden von einigen Kanten aufzuklappen und in der Ebene auszubreiten. Ist $K$ die Anzahl der Kanten und $F$ die Anzahl der Flächen des Polyeders, dann entsteht durch Aufschneiden von $K-F+1$ Kanten ein Körpernetz. Die Ecken liegen dabei offensichtlich auf dem Rand des Netzes. Die anderen $F-1$ Kanten verbinden jeweils die regelmäßigen Polygone des Netzes.

Jeder platonische Körper hat wie jedes konvexe Polyeder einen ihm zugeordneten ungerichteten planaren Graphen. Dieser Graph ist regulär, denn von jedem Knoten gehen $\frac{2\cdot K}{E}$ Kanten aus, sodass der Grad für alle Knoten gleich $\frac{2\cdot K}{E}$ ist, wobei $E$ die Anzahl der Knoten ist. Der Knotengrad ist gleich der Anzahl der Flächen (und Kanten), die in jeder Ecke des platonischen Körpers zusammentrifft. Bei planaren Graphen ist die genaue geometrische Anordnung der Knoten unwesentlich. Wichtig ist allerdings, dass sich die Kanten nicht schneiden müssen. Die Knoten dieses Graphen entsprechen den Ecken des Polyeders.

Die $K-F+1$ aufgeschnittenen Kanten jedes Netzes bilden zusammen mit den Ecken (Knoten) einen Spannbaum des Graphen. Jedes Netz entspricht genau einem Spannbaum und umgekehrt, sodass hier eine eineindeutige (bijektive) Zuordnung zwischen Netzen und Spannbäumen besteht. Wenn man ein Körpernetz ohne das äußere Gebiet als Graphen betrachtet, erhält man als dualen Graphen jeweils einem Baum mit $F$ Knoten und $F-1$ Kanten und dem maximalen Knotengrad $\frac{2\cdot K}{F}$. Jede Fläche des platonische Körpers wird dabei einem Knoten des Baums zugeordnet.

Diese Betrachtungen hängen mit dem Eulerschen Polyedersatz zusammen.

Duale Graphen und Färbungen

Kantenfärbung des Dodekaedergraphen

Flächenfärbung des Dodekaedergraphen mit dualer Knotenfärbung des Ikosaedergraphen

Die Anzahl der Farben, die mindestens nötig ist, um die Knoten eines Graphen so zu färben, dass benachbarte Knoten immer unterschiedlich gefärbt sind, wird chromatische Zahl genannt (siehe Knotenfärbung). Die entsprechende Zahl für die Kanten nennt man chromatischer Index (siehe Kantenfärbung). Bei den Graphen der platonischen Körpern ist sie gleich dem (maximalen) Knotengrad. Im Zusammenhang mit dem Satz von Vizing werden sie Klasse-1-Graphen genannt.

Die Knoten des Ikosaedergraphen können mit 4 Farben so gefärbt werden, dass benachbarte Knoten immer unterschiedlich gefärbt sind. Dies bedeutet, dass die chromatische Zahl dieses Graphen gleich 4 ist (siehe Knotenfärbung). Außerdem können die Kanten mit 3 Farben so gefärbt werden, dass benachbarte Kanten immer unterschiedlich gefärbt sind. Mit 2 Farben ist das nicht möglich, sodass der chromatische Index für die Kantenfärbung gleich 3 ist.

Um die entsprechende nötige Anzahl der Farben für die Flächen oder Gebiete zu bestimmen, ist der duale Graph hilfreich. Dieser graphentheoretische Begriff der Dualität ist gewissermaßen eine Analogie oder Verallgemeinerung der geometrischen Dualität von Polyedern (siehe Abschnitt oben).

Die Knoten dieses dualen Graphen werden dabei den Gebieten des ursprünglichen Graphen eineindeutig (bijektiv) zugeordnet und umgekehrt (siehe bijektive Funktion). Für den Dodekaedergraphen (siehe Abbildungen) gilt zum Beispiel: Die Knoten des dualen Ikosaedergraphen können mit 4 Farben so gefärbt werden, dass benachbarte Knoten immer unterschiedlich gefärbt sind, aber nicht mit 3 Farben, sodass die chromatische Zahl des Ikosaedergraphen gleich 4 ist. Daraus lässt sich indirekt schließen: Weil die chromatische Zahl gleich 4 ist, sind 4 Farben für eine solche Flächenfärbung des Dodekaeders oder eine Färbung der Gebiete des Dodekaedergraphen nötig.

Hamiltonkreise

Würfelgraph mit Hamiltonkreis

Alle Graphen der platonische Körper besitzen mehrere Hamiltonkreise. Das ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Beim Würfel und beim Dodekaeder ist das alles andere als offensichtlich. Für das Tetraeder, das dem vollständigen Graphen $K_4$ zugeordnet ist, ist es klar. Für das Oktaeder folgt die Existenz von Hamiltonkreisen aus einem Satz von Gabriel Andrew Dirac, für das Ikosaeder aus einem Satz von William Thomas Tutte (siehe Sätze über Hamiltonkreise).

Für die Anzahl der Hamiltonkreise gibt es jedoch keine mathematische Formel und keinen wirklich einfachen Algorithmus. Untersuchungen mit dem Computer zeigen zum Beispiel, dass das Ikosaeder 2560 Hamiltonkreise besitzt.

Eulerkreise

Die Graphen von Tetraeder, Würfel, Dodekaeder und Ikosaeder besitzen keine Eulerkreise, weil der Grad aller Knoten ungerade ist. Das liegt daran, dass in jeder Ecke dieser Polyeder eine ungerade Anzahl von Kanten zusammentrifft. Das Oktaeder besitzt 1844 Eulerkreise, wie Untersuchungen mit dem Computer zeigen.

Übersicht

Die fünf platonischen Körper	Tetraeder	Hexaeder	Oktaeder	Dodekaeder	Ikosaeder
Polyeder
zugeordneter regulärer Graph
chromatische Zahl (siehe Knotenfärbung)	4	2	3	3	4
chromatischer Index (siehe Kantenfärbung)	3	3	4	3	5
Anzahl für die Flächenfärbung (siehe dualer Graph)	4	3	2	4	3
Knotengrad (siehe regulärer Graph)	3	3	4	3	5
Knotenzusammenhangszahl	3	3	4	3	5
Kantenzusammenhangszahl	3	3	4	3	5
kürzester Zyklus (Taillenweite)	3	4	3	5	3
graphentheoretischer Durchmesser	1	3	2	5	3
graphentheoretischer Radius	1	3	2	5	3
Cliquenzahl	4	2	3	2	3
Stabilitätszahl	1	4	2	8	3
Anzahl der Hamiltonkreise	6	12	32	60	2560
Anzahl der Eulerkreise	0	0	1488	0	0