Es waren einmal vier Einsiedler in ihren Hütten, die wollten Wege anlegen, um sich gegenseitig aufsuchen zu können. Da sie sehr zänkisch waren, sollten sich diese Wege aber nicht kreuzen. So vermied man ungewollten Streit.
Sie fertigten einen Plan an, wie sieÄÖÄÖÄÖÖLÖLÖLSie setzten sich noch einmal intensiv
die Wege anlegen könnten, dochÄÄÄÄÄÄÄÄÄÄÄÄÄmit dem Plan auseinander, und
dieser wurde von ihnen gleichÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄentschieden sich zu einem anderen
wieder verworfen.ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄWegenetz.
Diese beiden Pläne stellen Graphen dar, die alle die selben Knoten (Häuser) und
Kanten (Wege) besitzen. Die Kanten sind nur verschieden dargestellt. Wir unterscheiden
deshalb nicht zwischen ihnen. Es handelt sich um 2 Darstellungen des gleichen Graphen.
Dabei ist auch eine solche Darstellung möglich, in der sich keine Kanten im Bild
schneiden. Die Graphen bei denen dies möglich ist, nennen wir eben.
Die vier Einsiedler hatten gerade die Lösung ihres Problems gefunden, als sich ein
Fünfter zu ihnen gesellte. Jetzt wurde es schwieriger. Kann man auch zwischen den
nunmehr fünf Hütten die Wege kreuzungsfrei anlegen?
Mit anderen Worten : Ist dieser Graph eben?
Zur Lösung dieses Problems benutzen wir die nach L. Euler (17 07 - 1783) benannte Eulersche Polyederformel: - Für einen zusammenhängenden Graphen mit Knotenanzahl e, Kantenzahl k und Flächenzahl f
(bei "ebener" Darstellung; einschließlich der äußeren Fläche)
gilt stets: e + f = k + 2.
Noch mal zur Erinnerung: - e = Knoten = Häuser
- k = Kanten = Wege
- f = Flächen= Bereiche zwischen den Wegen.
Bei dem Graphen mit den vier Nachbarn ist zum Beispiel:
- e = 4
- k = 6
- f = 4
Bei dem Graphen mit den fünf Nachbarn ist zum Beispiel:
- e = 5
- k = 10
- f = ?
Angenommen dieser Graph währe "eben" und wir hätten eine entsprechende Darstellung gefunden. Dann wollen wir uns jedes Flächenstück (auch das "äußere") als ein Land vorstellen und die Kanten als Ländergrenzen.
Die Zahl der Länder (Flächen) ist: f = k + 2 - e
(Also: f = 10 +2 - 5) f = 7
Jedes Land stellt nun an jeder seiner Grenzen genau einen Posten auf. Die Gesamtzahl
der Posten bezeichnen wir mit p.
Weil an Jeder Grenze von jeder Seite genau ein Posten
steht, ist dann: p = 2k
( Also: p = 2 * 10) p = 20
Andererseits hat aber jedes Land mindestens 3 Grenzen.
Hieraus folgt: p >= 3f und 3f = 21.
Wie ihr sicher alle bemerkt habt ist irgend etwas an dieser Gleichung falsch.
Ich sag euch auch was: 3 * 7 sind zwar 21, doch 20 ist nicht größer oder gleich 21!
Aus dem so erhaltenen Wiederspruch können wir schließen, dass die Annahme, der
Graph sei eben, falsch ist! Die fünf zänkischen Nachbarn können ihr Vorhaben also
nicht verwirklichen, weil sich immer mindestens 2 Wege kreuzen würden!
So, seid ihr jetzt etwas auf den Geschmack gekommen? Ja? Dann nichts wie rann an
die Knobelaufgabe 4!!!
Der Faden der Ariadne