Mathothek

Viele der etwas älteren Besucher der Mathothek erinnern sich an eine nicht im Unterricht behandelte Aufgabe, sondern in Pausen oder Freistunden diskutierte Aufgabe. Es ging darin um Direktverbindungen dreier Häuser zu einem Stromerzeuger, einem Wasserwerk und einem Gaswerk. Wesentliche Bedingung in der Aufgabe war, dass sich die Verbindungen nicht kreuzen durften. Immer scheiterte man an der neunten Verbindung.

Das folgende Exponat ist mit dieser Aufgabe praktisch gleich.

Die Geschichte dieser Aufgabe ist auch nicht viel aufregender als die Versorgungsgeschichte. Sie könnte etwa so lauten: Es waren einmal drei Häuslebauer, und jeder hatte seinem Haus gegenüber in einiger Entfernung einen Rundbau errichtet sowie eine gepflasterte Wegverbindung  von seinem Haus zum Rundbau angelegt. Nach einer Weile verabredeten sich die drei Nachbarn, die eine Rundhütte als Sauna, die zweite als Party-Raum und die dritte als Gästeraum zu benutzen. Soweit war alles klar. Aber dann bestand jeder der Drei auf je einem eigenen Weg von seinem Haus zu jeder der drei Rundbauten. Man wurde sich einig, die Kosten hielten sich – dank eigener Mitarbeit – in Grenzen, und es ging los. Es ging zügig voran bis zu dem unten zu sehenden Moment:

Der Blaue drohte mit dem Kadi. Zum Glück war eine Frau der Streithähne eine Mathematikerin und kompetent in der diskreten Mathematik, die bis heute einen Boom erlebt. Sie sagte: “Jungs spart euch eure Nerven und euer Geld, dieser Graph ist nicht planar, ist nicht zu plätten!” Die Männer verstanden richtig, es gab in ihrem ursprünglichen Sinne keine Lösung.

Wann ist ein Graph plättbar oder planar?

Ein Graph heißt in der Graphentneorie plättbar oder planar, wenn dieser Graph sich in der Ebene zeichnen lässt, mit Punkten für die Ecken oder Knoten und Verbindungslinien für die Kanten, ohne dass sich die Linien kreuzen.

Jeder der fünf platonischen Körper ist ein Graph, der plättbar ist. Hier sind jeweils der platonische Körper und sein geplätteter Graph:

Entscheidend für einen planaren Graphen ist es, dass er sich in der Ebene so darstellen lässt, dass sich keine Kanten schneiden. Dazu ist es egal, wie gebogen man die Kanten zeichnet. Eine Kante ist genau dadurch eine Kante, dass sie zwei Knoten verbindet.

Das nächste Exponat ist ein Beispiel für einen planaren Graphen:

Es handelt sich wieder um ein gemeinsames Grundstück. Auf dem eingezäunten Grundstück stehen drei Wohnhäuser und je ein eigenes Gartentürchen. Die Eigentümer einigen sich darauf, dass jeder von ihnen einen separaten Weg von seinem Haus zu seinem Türchen bekommen soll. Gibt es eine Lösung ohne Überschneidung? Eine solche könnte folgendermaßen aussehen:

Ein Spielzeug für Kleinkinder wirft in diesem Kontext natürlich die Frage auf, ob das Ding ein plättbarer Graph ist. 

Ja, das Spiel ist kreuzungsfrei in die Ebene zu legen. Man muss nur einen der beiden Drähte an einer Stelle lösen, aus der Überkreuzung mit dem anderen befreien und wieder an dem entsprechenden Knoten befestigen.

Dieses Objekt besteht aus einer Grundplatte mit fünf Paaren roter. gelber, blauer, grüner und schwarzer Pinnnadeln und fünf Verbindungsleitungen mit den gleichen Farben. Lassen sich je zwei Pinnnadeln mit  einer Leitung derselben Farbe verbinden, ohne sich zu schneiden. Hier eine Lösung – ein planarer Graph.

Von den plättbaren Graphen führt ein Weg zur Färbung und damit zum Vierfarbensatz.

Aber es gibt ein weiteres Exponat in der Mathothek, bei dem es eine Verbindung zu diesem Artikel gibt, und zwar über den Euler’schen Polyedersatz: Für jeden planaren Graphen gilt, dass mit E=Anzahl der Ecken, K=Anzahl der Kanten und F=Anzahl der Flächen die Gleichung E+F=K+2 richtig ist.

Eine kleine Aufgabe zum Schluss: Ist das Haus vom Nikolaus plättbar?

Das Nikolaus-Haus ist ein offener Euler-Kreis, enthält einen Hamilton-Kreis und ist plättbar!