Good Will Hunting

Date: 13. März 2016 Posted by: MichWitz In: Blog

Einer der besten Filme von Robin Williams ist Good Will Hunting.
Schon allein der Titel des Filmes – „Guter Will Hunting“ oder „Die Jagd nach dem guten Willen“ – ja wie den nun. Aber darum soll es hier nun gar nicht gehen.

Ihr erinnert Euch an den Film? Ihr erinnert Euch daran, wie Will auf den Fluren der Hochschule sauber machte und zwischendurch, wie nebenbei, eine offen ausgeschriebene Wochenaufgabe der Mathe-Fakultät löst? Gut, genau hier halten wir an und wollen uns die Aufgabe nebst Lösung einmal anschauen.

„Finden Sie alle nicht-isomorphen, homöomorph irreduziblen Bäume vom Grad zehn.“

Ok, alles klar, oder?

Nicht ganz? Gut, dann helf ich etwas nach.

Als erstes – wenn wir die Lösung nebst Herleitung haben, werden wir erkennen, dass diese Aufgabe gar nicht so hochkompliziert ist … sobald wir sie übersetzt haben.

Wir wollen also alle Bäume vom Grad zehn finden, welche nicht-isomorph und homöomorph irreduzibel sind. Nachdem wir unsere Zunge entknotet haben geht es frisch ans Werk.

Was sind mathematische Bäume? – Das sind Graphen, in welchen es keine Kreise gibt. Wir nähern uns der Oberstufenmathematik.
Graphen sind nichts anderes als Punkte, die durch Striche verbunden sind – wir kennen das aus Diagrammen.

Nehmen wir somit einen Punkt A und verbinden ihn mit Punkt B haben wir einen Graphen – erweitern wir Ihn um Punkt C und verbinden B mit C und C mit A, haben wir einen Graphen, der wie ein Dreieck ausschaut, aber auch ein Kreis ist – der Weg von Punkt A zurück zu Punkt A geht zB über B und C. Der Graph ist somit KEIN Baum – nehmen wir die Verbindung C-A weg, ist er ein Baum – weil kein Kreis.

Graph_Baum

So lange wir also einen Graphen haben, dessen Punkte so verbunden sind, dass wir immer wieder den selben Weg zurück nehmen müssen, den wir zuvor weg gegangen sind, dann haben wir einen Baum – gibt es im Graphen irgendwo eine Möglichkeit über einen anderen Weg zurück zu gelangen, dann ist es KEIN Baum.

Es ist wie in der Natur – an einem Baum gibt es nur Knoten, an denen sich die Zweige (Verbindungslinien) verästeln, oder Blätter (die Blätter und die Knoten sind dabei die Punkte).

Damit wissen wir nun was ein Baum ist. Ein Baum von Grad 10 ist dann ganz banal ein Baum mit 10 solcher Knoten oder Blätter

Das einfachste wäre nun den ersten Baum so zu bauen – Punkt 1 verbunden mit Punkt 2 verbunden mit Punkt 3 … bis Punk 10. Im Grunde eine Linie mit vorn und hinten je einen Punkt und dazwischen den restlichen 8 aufgefädelt. Diese Lösung ist für uns aber nicht möglich, weil dieser Baum NICHT homöomorph irreduzibel ist … Der Zungenbrecher ist schuld!

baum1-10

Homöomorph irreduzibel bedeutet, dass ein Punkt des Baumes nicht mit GENAU ZWEI Punkten verbunden sein darf. Also eine Verbindung zu genau einem Punkt oder zu mehr als zwei Punkten sind ok – GENAU ZWEI scheiden aus. Da unsere Punkte 2 bis 9 (aus den obigen Baum) immer genau nur mit ihrem jeweiligen Vorgänger und Nachfolger verbunden sind – immer GENAU ZWEI – haben wir keinen homöomorph irreduziblen Baum,

Wer aufgepasst hat, der erkennt, dass auch unser Baum von A nach B nach C (ohne A-C, da sonst kein Baum!) NICHT homöomorph irreduzibel ist.

Wo stehen wir also:
1. Baum = Graph ohne Kreise
2. Grad 10 = zehn Knoten/Blätter/Punkte
3. Homöomorph irreduzibel = jeder Punkt muss mit genau einem – oder mehr als zwei Punkten direkt verbunden sein.

Fehlt uns noch nicht-isomporph.

Isomorphe Bäume, sind Bäume die zwar unterschiedlich ausschauen, aber durch Kippen, Drehen und Verbiegen gleich werden.

isomorph

Bild 1 und 2 sind somit isomorph, da die Verbindung B-D so verbogen werden kann, dass aus dem Baum in Bild 1 der Baum in Bild 2 wird. Und genau das soll nicht sein dürfen.

Somit gilt für „Finden Sie alle nicht-isomorphen, homöomorph irreduziblen Bäume vom Grad zehn.“

1. Baum = Graph ohne Kreise
2. Grad 10 = zehn Knoten/Blätter/Punkte
3. Homöomorph irreduzibel = jeder Punkt muss mit genau einem – oder mehr als zwei Punkten direkt verbunden sein.
4. nicht-isomorph = Bäume die nach Kippen, Drehen oder Verbiegen gleich aussehen gelten als EIN Baum.

Nun, da wir die Bedingungen geklärt haben, frisch ans Werk: Womit fangen wir an?

Der – für mich – einfachste Lösungsweg ist das Bilden einer Kette mit immer mehr Punkten, um die wir dann die verbleibenden Punkte gemäß der Bedingungen anbringen.

Die kleinste Kette ist eigentlich keine – es ist einfach ein Punkt – ein Punkt, mit dem die restlichen 9 Punkte direkt verbunden werden.

Die nächste Kette wäre die mit zwei Punkten. Nehmen wir nun unsere Bedingungen, dann müssen wir diesem zweiten Punkt mindestens zwei der verbleibenden Punkte „mitgeben“, damit dieser Punkt mit mehr als zwei Punkten verbunden ist. Gegenprobe – verschieben wir Punkt 2 raus und hängen nur Punkt 3 an Punkt 2, so wäre Punkt 2 mit 3 und 1 verbunden – GENAU ZWEI – und das darf nicht.

Damit haben wir mehrere Varianten der Kette mit zwei Punkten – 6 Punkte am ersten und 2 Punkte am zweiten, 5 am ersten und 3 am zweiten und an beiden 4 Punkte. Achtung – 3 Punkte am ersten und 5 am zweiten wäre gleich dem 5 am ersten und 3 am zweiten, was wir ja schon hatten – selbiges mit 2 und 6 – somit scheiden diese beiden Konstellationen aus wegen nicht-isomorph.

Baum1-2

Zwischenstand – 4 Bäume aus den Ketten mit einem und zwei Gliedern.

Weiter geht es mit Ketten aus drei Gliedern. Hier gibt es wieder mehr Varianten. Der neue dritte Punkt am Ende benötigt wieder mindestens zwei weiter Punkte – verbleben 5 – davon braucht der mittlere Punkt mindestens einen Punkt und der vorderste hätte dann noch 4 über – das wäre dann also eine Verteilung von 4-1-2, wie im ersten Bild unten. Dann gibt es noch die Verteilung 3-1-3, 3-2-2 und 2-3-2 – (2-2-3 und 2-1-4 scheiden aus da isomorph und je ein Punkt am vorderen oder hinteren wegen homöomorph irreduzibel). In Bilder schaut das dann so aus:

Baum2

Zwischenstand – 8 Bäume.

Erweitern wir unsere Kette auf 4 Punkte. Hier gibt es nur eine Variante die nicht homöomorph irreduzibel (jeder Punkt mit genau einem oder mehr als 2 Punkte verbunden) ist – 2-1-1-2.

Baum4

Da eine Kette mit 5 Punkten unter den gegebenen Bedingungen nicht funktioniert – verbleiben wir bei nunmehr 9 Bäumen zum Grad 10, welche nicht-isomorph und homöomorph irreduzibel sind.

Ist die Lösung somit 9? – NEIN – eine trickreiche Variante der Dreier-Kette haben wir vergessen. Der vordere und hintere Punkt der Kette braucht jeweils nur zwei Punkte – somit bleiben drei über. Drei Punkte am mittleren Punkt der Kette hatten wir aber oben schon einmal. Was aber, wenn wir nur einen Punkt direkt am mittleren Punkt verbinden und die beiden verbleibenden Punkte wiederum an jenen. Tricky – aber machbar.

Baum3plus

Somit wäre der 10te und schwierigste Baum auch unser letzter zu findende Baum.

Es gibt genau 10 nicht-isomorphe, homöomorph irreduzible Bäume vom Grad zehn.

Aber das habt Ihr sicherlich schon 5 Minuten weiter oben gewusst und habt mich hier nur alles lang und breit aufschreiben lassen.

 

tl:dr

„Finden Sie alle nicht-isomorphen, homöomorph irreduziblen Bäume vom Grad zehn.“

Baum1-2

Baum2

Baum4

Baum3plus

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.