Das geht nur, wenn man bedenkt, die Erde ist eine Kugel und eine Leitung wird einmal rund herum gelegt. Auf dem Blatt Papier sieht das dann so aus, dass eine Leitung rechts raus geht und von links wieder reinkommt.
Wenn dieser Trick nicht erlaubt ist, geht es nicht.
---
Man kann zeigen, daß der Graph K(3,3), der aus sechs Ecken x1, x2, x3, y1, y2, y3 besteht, wobei jedes xi mit jedem yj durch genau eine Kante verbunden ist, nicht planar ist (d.h. nicht ohne Überkreuzung zeichenbar ist).
Angenommen, wir könnten diesen Graphen als planaren Graphen zeichnen. Dann hätte dieser n = 6 Ecken, m = 9 Kanten, und nach der Eulerschen Polyederformel könnten wir die Anzahl der Flächen ausrechnen:
2 = n - m + g = 6 - 9 + g,
also g = 5.
Weiterhin gilt, daß jede Fläche des Graphen eine gerade Anzahl von Ecken haben muß, denn Häuser und Versorgungswerke wechseln sich ab. Daher hat jedes Gebiet mindestens 4 Ecken und also auch mindestens 4 Kanten. Daher gilt 2m > 4g.
In unserem Fall bedeutet dies 18 = 2m > 4g = 20. Dieser Widerspruch zeigt, daß der Graph K(3,3) nicht planar ist.
Thema: ...kleine Rätselaufgabe für zwischendurch (Gelesen 30488 mal)
