 |
Die Aufgabe ist unlösbar.
Mit Hilfe der Graphentheorie kann man dieses Ergebnis beweisen:
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. |
|
Lösung
