Dieser Gastartikel ist ein Beitrag zum ScienceBlogs Blog-Schreibwettbewerb. Alle eingereichten Beiträge werden im Lauf des Septembers hier im Blog vorgestellt. Danach werden sie von einer Jury bewertet. Aber auch alle Leserinnen und Leser können mitmachen. Wie ihr eure Wertung abgeben könnt, erfahrt ihr hier.

sb-wettbewerb

Dieser Beitrag wurde von Lukas Prader eingereicht.
———————————————————————————————————————–
Will Hunting und die Graphentheorie

Ich schalte den Fernseher an, öffne den Teletext – und da lese ich es! Robin Williams ist tot. Kaum zu glauben! Unendlich schade um diesen brillanten Schauspieler mit seinen abwechslungsreichen Rollen.
Offenbar versuchten auch die Fernsehsender, den Tod des Stars aufzuarbeiten. Kurzerhand disponierten sie ihre Abendprogramme um – und so wurde bestimmt jeden Tag irgendwo ein Robin-Williams-Film gezeigt.

Als (angehender) Mathematiker hat mich natürlich einer davon ganz besonders interessiert: Good Will Hunting. Williams verkörpert darin die Rolle des Psychologen Sean Maguire, für die er mit einem Oskar ausgezeichnet wurde. Im Film geht es aber vor allem um das Aufeinandertreffen zweier scheinbar gegensätzlicher Menschen: Auf der einen Seite der Hausmeister Will Hunting, auf der anderen der MIT-Professor Gerald Lambeau, der gar ein Empfänger der überaus renommierten Fields-Medaille (quasi des „Mathematik-Nobelpreises“) ist. Lambeau interessiert sich sehr für Will – warum, mögen Sie fragen. Wie kann ein Hausmeister einen Mathematiker begeistern? Ganz einfach: Mit Mathematik! Will entpuppt sich als wahres Mathematikgenie und letztlich muss Lambeau sogar gestehen, dass er Will in seinem eigenen Fach eindeutig unterlegen ist. Wahrscheinlich halten das viele Leute für Fiktion, was es allerdings nicht ist! Mathematische Wunderkinder (oder eben Wundererwachsene wie Will), die aus dem Nichts auftauchen und mit den „echten“ Mathematikern konkurrieren, sind zwar nicht häufig, aber es gibt sie tatsächlich. Der indische Buchhalter Srinivasa Ramanujan, der mit seinen Briefen die britische Mathematikelite begeisterte, ist das wohl bekannteste Beispiel für einen Will Hunting des wahren Lebens.

Auch im Film ist es so, dass Professor Lambeau eher durch Zufall auf Wills Talent aufmerksam wird: Er erwischt ihn dabei, wie er ein Rätsel auf einer Gangtafel (völlig korrekt) löst, das für seine Studenten bestimmt war. Zwei Jahre lang hätten die MIT-Professoren für die Lösung gebraucht, gesteht er in einer Vorlesung. Dementsprechend entsetzt ist er natürlich, als er erkennt, wie mühelos Will damit fertig wird. Tatsächlich handelt es sich dabei aber um ein Rätsel, das jeder von uns verstehen und lösen kann – und das werden wir im Laufe dieses Textes auch tun! Zugegeben: Die Aufgabenstellung ist das einzig Komplizierte am ganzen Rätsel. Die Lösung ist weitaus leichter. Versprochen! Ich haue die Angabe jetzt ganz einfach raus – danach gehen wir sie Wort für Wort durch und lösen das Rätsel. Also nicht schrecken! Abgemacht? – Na dann:

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

Ich nehme an, Sie haben bereits alles verstanden. Dann können wir ja fortfahren … Haha, jetzt habe ich mir mit Ihnen einen Spaß erlaubt – wird nicht wieder vorkommen. Als ich das zum ersten Mal gelesen habe, habe ich auch nur Bahnhof verstanden. Das Rätsel wird uns tief in die Graphentheorie führen – eine mathematische Teildisziplin, die sich mit ganz speziellen Strukturen befasst. Um herauszufinden, was genau ein solcher Graph ist und wofür man sie braucht, unternehmen wir eine kleine Zeitreise ins 18. Jahrhundert:

Das preußische Königsberg … Eine Stadt mit einer langen Geschichte. Der Fluss Pregel durchzieht das Stadtzentrum. Erst zweigeteilt vereinigen sich hier die Flussarme, schließen eine Insel ein (den Kneiphof) und vereinigen sich anschließend wieder. Reihenhäuser zieren die Ufer, auf dem Wasser tummeln sich Schiffe und zahlreiche Enten. Ein großer Dom auf dem Kneiphof überragt die Reihenhäuser. Um alle Stadtteile bequem erreichen zu können, wurden sieben Brücken errichtet (siehe dazu die Karte unten). Sie sind er Gegenstand einer Frage, die die Bewohner er Stadt seit jeher quält, aber nach wie vor unbeantwortet ist: Kann man auf einen Stadtspaziergang jede der sieben Brücken genau einmal überqueren? Genau einmal – das bedeutet, man darf weder eine Brücke auslassen noch zweimal oder gar öfter über sie flanieren. Wie kann man so eine Frage überhaupt angehen? Die Königsberger spazieren und spazieren, sitzen vor ihren Landkarten … Es gelingt ihnen einfach nicht, eine Route zu finden.

1 / 2 / 3 / 4 / Auf einer Seite lesen

Kommentare (26)

  1. #1 CM
    26. September 2014

    Habe mich sehr amüsiert – schön geschrieben! Und ich habe mich daran erinnert gefühlt:

  2. #2 Lisa Leander
    26. September 2014

    Ich mag den Film sehr gern und erinnere mich gut an die Szene mit den vielen “Böbbels” (Blättern) an der Tafel. Toll zu erfahren, was dahinter steckt, und dass es eigentlich so einfach ist! Vielleicht sollte es ein Insider-Witz für Mathematiker sein 😉

  3. #3 Dampier
    26. September 2014

    Schöner Artikel! Wie spannend Mathematik sein kann, habe ich erst spät durch solche gelungenen Populärwissenschaftlichen Darstellungen erfahren, in der Schule hat mich das völlig überfordert. Aber vielleicht hatte ich damals einfach andere Dinge im Kopf 😉

    Nun ja, Mathematiker werde ich in diesem Leben nicht mehr, aber ich freue mich immer über so spannende Enblicke.

    Kleiner Kritikpunkt: die farbigen Punkte sind praktisch nicht zu erkennen, das sieht alles schwarz aus. Die Erklärung funktioniert aber trotzdem.

    Den Film fand ich eher langweilig.

    grz
    Dampier

  4. #4 Alderamin
    26. September 2014

    Ich finde den Artikel auch so gut wie perfekt. Unterhaltsam geschrieben, was zum Mitdenken, Bilder sind dabei. Einer meiner Favoriten (deren es fünfe gibt).

  5. #5 Florian Freistetter
    26. September 2014

    Der Artikel gefällt mir auch sehr gut! Stellenweise hätte ich mir ein klein wenig mehr Ausführlichkeit gewünscht. Aber bei so einem abstrakten Thema ist es immer schwer und die allgemeinverständliche Umsetzung ist hier mehr als gut gelungen!

  6. #6 Paul Busse
    26. September 2014

    Ein sehr guter Artikel. Als Elektrotechniker bin ich schon etwas mit Graphentheorie in Kontakt gekommen, auch wenn Bäume bei uns eher selten vorkommen, weil da kein Strom fließt. Aber auch ohne mein Vorwissen denke ich wäre der Artikel verständlich gewesen. Ein interessantes und komplexes Thema wurde hier sehr gut erklärt.

    Was die abschließende Frage angeht. Ein Baum vom Grad 3 mit den genannten Eigenschaften kann nicht existieren, oder? Die 3 Punkte liegen immer in einer Reihe, wobei der mittlere Knoten den Grad 2 hat und damit homöomorph reduzibel wäre. Richtig?

  7. #7 Bullet
    26. September 2014

    … und die einzige Methode, die Reduzibilizierbarkeit aufzuheben, wäre die Kreis- (na ja, eher die Dreieck-)struktur. Hilft auch nich … 🙁

  8. #8 Lukas Prader
    26. September 2014

    Vielen Dank für die vielen Rückmeldungen! Ehrlich gesagt hätte ich nicht gedacht, dass jemand den Artikel zu Ende liest, so lang wie der ist …

    @CM: Ja, das Video kannte ich, und ehrlich gesagt bin ich genau so auf dieses Thema gekommen. 😉

    @Lisa Leander: Ich glaube auch, dass es ein Insider-Witz ist. Bei den Simpsons kommen solche Witze auch sehr oft vor (Simon Singh hat dazu ein ganz gelungenes Buch geschrieben.

    @Dampier: Ja, ich muss gestehen, die Punkte sind wirklich schlecht unterscheidbar. Ich wollte eher “langweilige” Farben nehmen, damit es nicht so grell wirkt, was nun aber zur schlechten Sichtbarkeit geführt hat.

    @Alderamin/Florian Freistetter: Danke für das Lob! 🙂 Mein Ziel war es eben, dieses so gut wie unbekannte Thema interessant zu verkaufen. Wenn das ein Mathematiker liest, wird er es sicherlich auf zu kitschig/ungenau finden, aber es soll ja auch keine Forschungsarbeit sein.

    @Paul Busse/Bullet: Es freut mich sehr, dass Sie sich darüber Gedanken gemacht haben: Tatsächlich gibt es keinen solchen Baum vom Grad 3. Entweder hätte man sonst einen Kreis (kein Baum –> verboten), oder man hätte einen Punkt mit genau zwei Verbindungen, was ja auch verboten ist. 😉

  9. #9 Fliegenschubser
    26. September 2014

    Ein sehr guter Artikel!

  10. #10 Chaaron
    26. September 2014

    Der Artikel ist sehr interessant und verständlich geschrieben. Selbst ich habe das kapiert, aber in einer Klausur gäbe es trotz richtiger Lösung nicht die tolle Punktzahl…
    Leider genügt es den Mathematikern nicht, wenn man etwas aufmalt.
    Die Frage ist: wie berechnet man das Ganze?

  11. #11 Chaaron
    26. September 2014

    Öhm, ich meine natürlich die volle Punktzahl, auch wenn diese dann toll ist…

  12. #12 Realistischer
    26. September 2014

    Um auch was kritisches anzumerken: die 2 angegebenen Regeln für Graphen, dass alle Punkte zusammenhängen müssen und sich keine Linien überkreuzen dürfen — das gilt nicht für Graphen allgemein sondern beschreibt den Spezialfall der zusammenhängenden planaren Graphen.

  13. #13 Lukas Prader
    26. September 2014

    @Fliegenschubser/Chaaron: Vielen Dank für das Lob! Tatsächlich gibt es (wie für das meiste in der Mathematik) eine Formel, mit der man die Anzahl der Bäume berechnen kann.
    [siehe dazu: https://amininima.wordpress.com/2013/05/12/not-that-good-will-hunting/ ]

    @Realistischer: Vielen Dank für die Korrektur, das war mir nicht bekannt. In diesem Rahmen habe ich “Graph” quasi als Vereinfachung für die von Ihnen genannten “zusammenhängenden planaren Graphen” genannt.

  14. #14 DerMannMitHut
    26. September 2014

    @Chaaron: Ich würde in einer Klausur die volle Punktzahl geben. Denn es ist auch ein gültiger mathematischer Beweis, wenn man offensichtlich alle Möglichkeiten durchgeht und zeigt, warum es keine weiteren Möglichkeiten geben kann.

    Dafür braucht man keine Formel. Formeln werden in der Mathematik zwar gerne verwendet, aber nur um komplizierte Sachverhalte einfach und kompakt darzustellen (auch wenn das für den Laien oft anders wirkt).

  15. #15 rolak
    26. September 2014

    Ich nehme an, Sie haben bereits alles verstanden

    Auch noch ein Hellseher… 😛

    Ein großer Dom

    Der Königsberger Dom. Mit Kants Grab. Eine der (für mich) Muß-Anlaufstellen in der viel zu schmal bemessenen Freizeit in dem einwöchigen Aufenthalt damals ’97. Vier Verwandte mit angeheuertem Kleinbus auf den Spuren der Vorfahren im Umland. Versunken im Übungsgebiet (geschickt am 1.Mai besucht..) – sowohl das Bauernhöfli, fast alles vom nahegelegenen Dorf und auch fast ich. In einer harmlosen Panzerspur-Pfütze, die sich als oberste Schicht einer anderthalb Meter tiefen Schlammkuhle entpuppte. Amüsierte die Mitreisenden königsberglich – schwupps, sackt er weg, schwupps, steigen die Arme mit Brieftasche und Kamera zum Himmel 😉

    Achten wir auf den grünen Punkt!

    Der so ungemein geschickt getarnt ist…

    grau dargestellt

    den würde ich ohne Kontext nur mit Farbwert-Analyse finden.

    Bei der Programmierung haben wir es ja mehr mit den Gärtnern zu tun – Bäume hegen und pflegen, Neues dazugesellen, bei Bedarf beschneiden, Reste entsorgen. Unabhängig davon ist der Artikel flott geschrieben, Interesse weckend und die Problematik umfassend beschreibend.

  16. #16 Lukas Prader
    26. September 2014

    @rolak: Vielen Dank für das humorvolle Feedback und die Anekdote! Ja, die Farbwahl bei den Punkten ist ungünstig gewählt. Wenn man auf die Bilder klickt, erhält man eine vergrößerte Ansicht – und da sind (zumindest meiner Meinung nach) die Farben besser unterscheidbar.

  17. #17 PDP10
    26. September 2014

    @Lukas Prader:

    “und da sind (zumindest meiner Meinung nach) die Farben besser unterscheidbar.”

    Ähm … naja … auf meinem Laptop-Display Grau und nicht-ganz-grau-irgendwie-blau … 🙂

    Aber ansonsten: wirklich schöner Artikel!

    Ich liebe dieses Graphentheorie Zeugs (auch wenn ich bei den richtig abstrakten Untiefen total passen musste), weil man da mit ein paar Zeichnungen wunderschön komplexe Sachverhalte erklären kann.

    Und das hast du hier ziemlich gut gemacht.

  18. #18 rolak
    26. September 2014

    auf die Bilder klickt

    Mit kleinem Finger ganz links unten im Barré, also ctrl-shift. Dann gehts (nur hier?) in einem neuen Tab auf, der auch den Fokus bekommt, ohne daß ich den Kontext (Text) aus dem direkten Zugriff verliere.

    Beide Punkte sind ja auch im Text beschriebenen und eindeutig identifizierbar – doch beim grünene vermeine ich nur nach intensivem Starren einen Unterschied auszumachen, nicht festhaltbar. Bei der gößeren Variante wars eindeutig. Beim Anderen half nicht einmal das.. kann klarerweise auch an der aktuellen Brillen-Monitor-Kombi liegen. Kleiner Check: Putzen bringt nix. Immer noch sehe ich verschiedene Variationen von Anthrazit herumtanzen. Und zwar mehr als zwei, nicht sehr hilfreich – vielleicht hast Du ja ne schöne neue optische Täuschung gebastelt.

  19. #19 Lukas Prader
    26. September 2014

    @PDP10: Vielen Dank für das Lob! Beim Verfassen hat mich selbst überrascht, wie praktisch und vor allem wie lebensnah die abstrakte Graphentheorie sein kann. Aber das ist ja das Tolle an Mathematik: Sehr viele Menschen haben Angst vor ihr (das lernen sie in der Schule), obwohl sie unser Freund und Helfer ist – keineswegs unser Feind.

  20. #20 Peroppi
    27. September 2014

    Ein echt schöner Artikel. Hab ihn spontan komplett durchgelesen obwohl ich eigentlich gar keine Zeit hatte 😀

    Ich mag den Stil, die Dinge zu erklären, sehr natürlich trotz aller Lockerheit gut strukturiert. Was Graphen sind, war mir klar, aber diese Aufgabe und auch die speziellen Attribute kannte ich nicht. Mit der Erklärung habe ich alles sofort verstanden, obwohl ich auch nur schwarze Punkte gesehen hab 😉 Interessant, jetzt als ich die Kommentare überflogen habe ist mir aufgefallen dass da ja doch blaue, graue und grüne sind – aber nur wenn ich schräg auf mein Laptopdisplay schaue.

  21. #21 Chemiker
    27. September 2014

    Ganz großes Plus! Richtig gut geschrieben und verständlich, auch ohne daß man den Film gesehen hat.

  22. #22 Lukas Prader
    27. September 2014

    @Peroppi/Chemiker: Vielen Dank für das Lob! Jetzt habe ich mir das mit den Punkten noch einmal bewusst angeschaut und tatsächlich: Wenn man den Bildschirm weit nach hinten klappt, sieht man nur schwarze Punkte. Deswegen ist es mir wohl nicht aufgefallen, ich habe ihn viel schräger nach vorne.
    Und ich glaube gar nicht wirklich, dass der Film notwendige “Vorkenntnis” für den Artikel ist. Es geht ja vor allem um das Rätsel und weniger um die Handlung.

  23. #23 Pterry
    27. September 2014

    schöner Artkel. ich habe nach dem Lesen heute darüber nachgedacht, wo sowas Anwendungen finden könnte. mit dem U-Bahn-Plan-Beispiel hatte ich das Problem, dass da ja auch “Punkte” also Stationen wegfallen, wenn da keine andere Linien schneiden. Und ich bin beim Nachdenken bei Twitter (und dann bei Mindmaps) gelandet: ich fände es sehr interessant, Tweets und ihre Replies mal von der oben-unten-Reihenfolge weg darzustellen (seitlich z.B.). Da können bestimmt auch schöne Bäume wachsen 🙂

  24. #24 Lukas Prader
    27. September 2014

    @Pterry: Das mit dem “Punkte wegfallen” (bzw. dass sie homöomorph irreduzibel sein müssen) gilt ja nicht für alle Graphen, sondern hier nur für die Bäume im Rätsel.
    U-Bahn-Pläne und alle anderen Pläne von Verkehrsmitteln sind also schon Anwendungen von Graphen. Mindmaps auch, klar. Jede Hierarchie (z.B. Position der Arbeiter in einer Firma, die Einteilung der Zahlenmengen), oder allgemein jeder Plan (z.B. wie der Briefträger jeden Tag geht) ist eine Anwendung von Graphen.

  25. #25 Michael
    Hamburg
    28. September 2014

    Toller Artikel, und: Nein: Auch ich, als Mathematiker fand ihn weder “kitschig” noch “ungenau”.
    Daher Danke, vor allem auch für den Schluss!

  26. #26 Lukas Prader
    30. September 2014

    @Michael: Vielen Dank für das Lob! Das freut mich natürlich besonders, wenn er sogar bei Mathematikern gut ankommt.