Noch einmal beschäftigen wir uns heute mit dem Stadtwerkeproblem mit dem Titel "Gas, Wasser und Strom". Sie erinnern sich? Es geht darum, drei Häuser so mit Strom, Wasser und Gas zu versorgen, dass siech die Leitungen nicht kreuzen. Hierzu rechts nochmals die Grafik. Obwohl das nun schon einige Zeit her ist, habe ich erst kürzlich von Herrn Andreas Schnitter die wohl ultimative Lösung erhalten. Herr Schnitter schreibt dazu:

   "Es geht darum, jedes der drei Häuser mit Gas (G), Wasser (W) und Elektrizität (E) zu versorgen, ohne dass sich die Leitungen kreuzen. Es gibt einen Satz in der Graphentheorie (Tutte) der besagt, dass ein Graph genau dann nicht ohne Kreuzpunkte der Kanten zeichenbar ist, wenn er als Teilgraph eine Unterteilung des vollständigen Graphen mit fünf Knoten (K 5) oder des vollständigen bipartiten Graphen mit je drei Knoten pro Partition (K 3,3) enthält.

   Das Häuserproblem entspricht genau dem K 3,3 - ist also in dieser Ebene nicht lösbar! Das läßt sich mit dem Polyeder-Satz von Euler beweisen: dieser Graph, um einen solchen handelt es sich hier, ist nicht planar.

   Die Aufgabe ist lösbar, wenn sich die genannten Objekte auf der Oberfläche eines Toruses befinden."

   Ah, ja! Das ist also des Rätsels Lösung, einfach und korrekt erläutert. Sicherlich könnte es durchaus sein, dass manch einer den Äußerungen nicht wirklich folgen kann, da nicht jeder unbedingt Mathematik studiert haben muss. Es könnten Fragen auftauchen wie

Wer oder was ist Tutte?

Kennt jemand Euler?

Was ist ein bipartiter Graph?

Was für 5 Knoten (K 5) sind gemeint?

Welche Partition mit mit je drei Knoten (K 3,3)?

   Sicherlich könnten weitere Fragen als die aufgeführten auftauchen, doch sind wir mal ehrlich ... auf eine Schachseite gehen und noch nicht mal Euler oder Tutte, geschweige denn einen bipartiter Graph kennen ... Einen Tipp kann ich ja mal geben: Leonhard Euler war ein bedeutender Mathematiker, er lebte vom 15.4.1707 bis 18.9.1783 in St. Petersburg, die letzten Jahre in Berlin. Seine mathematische Laufbahn begann 1727 in Newtons Todesjahr. Eulers überragendstes Werk ist jenes über die Variationsrechnung (1744), wo es im weitesten Sinn um Optimierungsprobleme geht. Nach Euler benannt sind die "Eulersche Zahl e" (Basis der natürlichen Logarithmen) und die "Eulerschen Konstante". Die Formeln hierzu:

   Mit unserem Stadtwerkeproblem hat aus folgendes Spiel zu tun (Beispiel links): Zwei Spieler, Spieler A und Spieler B, spielen ein Spiel. Es sind sechs Punkte auf einem Blatt gezeichnet. Spieler A nennt bei jedem Zug zwei Punkte, und Spieler B soll sie mit einer Linie verbinden, ohne durch andere Punkte zu gehen oder schon gezeichnete Linien zu kreuzen. Spieler A darf einen Punkt höchstens dreimal in einem Spiel nennen. Kann Spieler B zwei Punkte nicht nach den Regeln verbinden, so verliert er. Sonst endet das Spiel, wenn Spieler A alle Punkte dreimal genannt hat, mit dem Gewinn von Spieler B. Und, erkennen Sie das Stadtwerkeproblem bei diesem Spiel?

   Aber bevor wir uns allzutief in mathematische Feinheiten und weitere städtische Probleme vertiefen, schauen wir uns lieber eine Schachpartie an. Schwarz erspielte sich einen Vorteil, den er mit einem groben Fehler nicht nur vergibt, sondern gleich die ganze Partie einstellt.

   Weitere verständliche Erklärungen zu den mathematischen Erläuterungen über Kreuzpunkte, Graphen, Graphentheorien sowie Kanten, Teilgraphen und bipartiten Graphen werden im Forum gerne entgegengenommen.