Eigenraum (@eigenraum.podcasts.social.ap.brid.gy)

EIG055 Romangraphen Thomas Kahle Im Buch „Die Coruscant-Krise“ entdecke ich Mathematik: Die Kapitel schicken einen immer kreuz und quer durch das Buch zu anderen Kapitel. Diese Struktur ist ein azyklischer gerichteter Graph. Den musste ich mir natürlich mal aufmalen, damit ich einen Überblick über alle Kapitel finde, und weiss, wie ich mich zum besten Ende durchschummeln kann. * Eigenraum EIG011 – Graphentheorie * DAG * OEIS Folge 3024 * DAGitty * Breiten– und Tiefensuche * Topologische Ordnung * Kausalitätstheorie und Structural equation modeling Feedback gerne auf Mastodon @[email protected], an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite. Automatisch generiertes Transkript (nicht geprüft) So, hallo zusammen ihr Lieben, hier ist wieder der Eigenraum. Das Jahr 2025 neigt sich dem Ende entgegen, es war auch eine Weile still hier auf diesem Kanal, aber jetzt wollen wir das Jahr nochmal mit einem sozusagen großen Knall ausklingen lassen. Das Eigenraumversprechen gilt. Wir podcasten mehrmals jährlich. Und so war es auch dieses Jahr und so wird es auch nächstes Jahr wieder sein. Und auf einen festen Rhythmus kann ich mich ja irgendwie nie einlassen, weil ich ja ein abwechslungsreiches Leben führe, das nicht immer eine regelmäßige Podcast-Veröffentlichung erlaubt. Aber dafür, wenn eine Folge fertig ist, dann wird sie auch veröffentlicht. Außer ganz, ganz selten, wenn was Besonderes ist. Aber dazu später nochmal mehr. Und mit später meine ich nicht in dieser Folge, sondern später in diesem Jahr. So, hier ist also Eigenraum Nummer 55. Es ist Dezember 2025. Mein Name ist Thomas Kahle. Ich bin Mathematiker an der Otto-von-Gierige-Universität Magdeburg an der Elbe. Sowohl die Stadt Magdeburg liegt an der Elbe, als auch die Universität mehr oder weniger an der Elbe liegt. Und ich mache das hier, weil ich denke, dass es nicht genug Mathe-Podcasts gibt. Nicht genug Mathe-Podcasts, nicht genug Mathe-Podcasts für all die Mathematik, die es da draußen gibt in unserem Leben. Zum Beispiel in Romanen. Ich habe nämlich kürzlich ein interessantes Buch gelesen. Also genau genommen habe ich es sogar vorgelesen. Und der Titel dieses Buches ist die Coruscant-Krise. Coruscant, die Fans von Science-Fiction kennen, spielt im Star-Wars-Universum. Genauer gesagt in der Clone-Wars-Universum oder in der Clone-Wars-Epoche. Aber das ist jetzt eigentlich gar nicht so wichtig. Der Inhalt war auch so, naja, ein wenig belanglos und an den Haaren herbeigezogen. Aber wenn die Kinder sich das gerne aus der Bibliothek ausleihen wollen, dann gerne, bin ich immer dabei. Und dieses Buch hat so ein bisschen komischen Stil. In dem Buch gibt es nicht immer so direkte Du-Ansprache der Leserin oder des Lesers. Und dann kann man auch noch so Entscheidungen treffen. Also man fängt so an zu lesen und kaum hat man die erste Seite gelesen, steht dann sowas wie, willst du jetzt schnell weiterrennen oder willst du dein Lichtschwert zücken und kämpfen? Und wenn man rennen will, dann muss man irgendwie zu Kapitel 14, wenn man kämpfen will zu Kapitel 71 oder sowas und dann blättert man dahin und da geht es dann eben weiter mit der Geschichte und so hat man dann so ganz viele Entscheidungen zu treffen und irgendwann kommt man zu einem Ende und dann kriegt man auch noch so eine Punktzahl. Also sowas, da steht dann so, okay, es ist jetzt zu Ende, irgendwie, keine Ahnung, man ist irgendwie schwer verletzt oder gedemütigt oder hat gewonnen oder sowas. Und dann kriegt man so drei von zehn Machtpunkten oder so. Wenn man nur drei von zehn hat, ist das natürlich ein bisschen frustrierend. Geht man vielleicht nochmal zurück. Also das Coole ist ja, in dem Buch kann man einfach wieder zurückblättern und die Zeit zurückdrehen. Und dann entscheidet man sich kurz vor dem fatalen Fehler, der zu nur drei von zehn Punkten führte, nochmal um. Da kann man vielleicht so einen kleinen dummen Unfall, den man hatte, vermeiden. Aber, naja, manchmal kann man die Geschichte dann doch nicht mehr richtig ändern und man merkt, dass man ganz früh einen Fehler gemacht hat. Und man kann natürlich auch nochmal zurück zum Anfang springen und ganz am Anfang alles wieder komplett anders machen, sich der dunklen Seite anschließen oder was weiß ich. Und das wird irgendwie so ein bisschen unübersichtlich, was hatte man jetzt eigentlich schon gelesen, was kann man hier noch machen. Also habe ich mir als Mathematiker irgendwie gedacht, ich brauche da erstmal einen Überblick, also jetzt einfach hier so drin rumlesen. Nee. Also habe ich mir mal ein Blatt Papier genommen und habe ich links oben die 1 hingeschrieben für das erste Kapitel, da wo es losgeht. Und wenn man den Text von der 1 dann gelesen hat... Da muss man sich entscheiden, ob man, und das stimmt jetzt wirklich, ob man bei Kapitel 96 oder bei Kapitel 26 weitermachen will. Natürlich in diesem Text, in der Geschichte sind da irgendwie Dinge mit verbunden, also irgendwie Verhaltensweisen oder eben irgendwie Entscheidungen, die die Story in eine grob andere Richtung lenken können. Aber ich will ja erstmal nur wissen, was hier überhaupt möglich ist, also wie das überhaupt geht. Und dann bin ich mal ohne groß zu lesen, direkt zu der 96 geblättert und direkt am Ende von dem kleinen Kapitel habe ich dann mal geschaut, was dann da passieren kann. Und da kann man eben zu 114 oder 54 gehen. Und bei der anderen Wahl, die man am Anfang hatte, bei der 26, kommt man zu 46 und 81. Also ist es wie so eine aufspaltende Geschichte. Also ich habe jetzt schon vier Möglichkeiten entdeckt und ich male mir das auf meinem Blatt als so ein Pfeildiagramm. Ich mache immer für jedes Kapitel, was ich neu entdeckt habe, mache ich so einen kleinen Kreis, schreibe die Zahl da rein und mache dann einen Pfeil, von wo ich da hinkam, von wo nach wo ich kam. Und das ist ja schon ein mathematisches Konzept, also das ist ein gerichteter Graph, würden wir in der mathematischen Sprache sagen. Zu Grafentheorie hatten wir auch schon einiges im Eigenraum. Ich glaube Eigenraum Folge 10 und 11 sind da relevant, könnt ihr gerne nochmal reinhören. Und hier besteht unser Graf immer aus den einzelnen Kapiteln, das sind die Ecken des Grafen in der Fachsprache und dann von jedem Kapitel ausgehend die gerichteten Kanten, die male ich auf meinem Blatt einfach als Pfeile, zu welchen Kapiteln ich von dahin aus springen kann, wo ich weiterlesen kann, je nachdem wie ich meine Entscheidung treffe. Und in diesem Graphen war es nun so, dass manchmal gibt es gar keine Entscheidung und dann wird man einfach direkt irgendwo hingeschickt. Meistens hat man zwei Entscheidungsmöglichkeiten und ganz selten hat man auch mal drei Entscheidungsmöglichkeiten. So, ich hatte mein Bild von diesem ganzen Roman, das habe ich dann fertiggestellt, bin ich alles durchgegangen und hatte ich neulich schon auch auf Mastodon gepostet. Oder ihr könnt es jetzt auch in den Shownotes oder auf der Episodenseite sehen oder im Podcast-Player, wenn euer Player das unterstützt. Also es ist ein ganz schönes Gewusel von Pfeilen und am Ende habe ich sogar zwei ganze A4-Blätter vollgemalt mit dem gerichteten Graphen dieser Geschichte. Und eine interessante Sache passiert gleich bei der 96, die ich eben schon hatte, einer der Wahlmöglichkeiten, die direkt nach 1 kommen. Von der aus konnte man nämlich zur 114 oder zur 54, aber von der 114 aus hat man gar keine Wahl, sondern man kommt zwangsläufig auch zur 54. Also ist man da direkt von der 96, kommt man immer zur 54 und man kann sich nur entscheiden, ob man direkt geht oder eben mit dem kleinen Umweg um die 114. Und in der Geschichte haben sie da eingebaut, dass man auf diesem Umweg irgendwie noch eine kleine Information erhält, die einem später im Buch hilft, eine Entscheidung richtig zu treffen, um zu einer höheren Punktzahl zu kommen. Jedenfalls hilft einem das, wenn man das Buch so liest wie vorgesehen, also wenn man es jetzt so auseinander nimmt wie ich und sich nur die Struktur anguckt und schaut, wie komme ich auf effizientem Weg zur höchsten Punktzahl, dann ist es jetzt nicht so ganz wie der interaktive Roman, den das Buch auf dem Titel ankündigt. Ich finde, interaktiver Roman ist irgendwie so ein 1990-Wort, oder? Interaktiv irgendwie klingt das so ein bisschen so wie Multimedia oder so. Ja, also jedenfalls, da gibt es so ein ganzes Genre dazu. Das ist so ein Choose-Your-Own-Adventure. Ich erinnere mich aus meiner Kindheit auch. Ich glaube, es gibt auch so drei Fragezeichenbücher, die nach dem gleichen Prinzip aufgebaut sind, dass man eben immer diese Entscheidungen treffen kann. Oder in manchen Comics, es gibt auch bestimmt lustige Tagebücher, die diese Eigenschaft haben. Aber das Ding hier ist schon recht umfangreich. Also es hat irgendwie 139 Kapitel und da hätte ich mir eigentlich auch schon, als ich anfangen habe, in meinem Grafen zu malen, gedacht, dass ich vielleicht lieber ein A3-Blatt oder ein A2-Blatt hätte nehmen sollen, denn ich habe ja dann auf jeden Fall 139 kleine Kreise und noch die ganzen Pfeile dazwischen. Also ich habe jetzt jedenfalls die ganze Geschichte hingemalt und betrachtet, und war irgendwie so ein bisschen naiv rangegangen und das hat also eine gewisse Komplexität, die sich eigentlich in meiner ersten Handzeichnung finde ich ganz schön ausdrückt. Ich musste dann immer, wenn ich so ein Blattrand kam, muss ich dann so meine Fade, die ich verfolgt habe, so ein bisschen um die Ecke biegen und so hat das eine ganz interessante Optik entwickelt. Wie in so einem Kriminalfall, wie so, wenn so der Kommissar so ein Riesendiagramm hat mit allen Verdächtigen und allen Beweisen und dann Lotto so Verbindungspfeile zeichnet und so, so sieht das ein bisschen aus. So, nun ist das Ganze aber eigentlich ja nicht nur so ein Graph, Sondern das ist eine Geschichte und ich habe überprüft, dass es keine gerichteten Kreise in dieser Geschichte gibt. Also es ist auf jeden Fall wirklich, ich habe es überprüft, nicht möglich, dass man zu einer Stelle kommt, bei der man schon mal war. Und dann könnte man ja irgendwie im Kreis laufen. Also man kommt wirklich immer vorwärts und immer zwangsläufig zu irgendeinem Ende. Also egal, welche Wahlen man trifft, man kann nur endlich lange lesen und dann kommt man zum Ende und man liest nie was doppelt. Und solche Graphen, die diese Eigenschaft haben, die nennt man azyklische gerichtete Graphen, weil es eben keine Zykel gibt. Also so im Kreis gehen entlang von Pfeilen in der richtigen Richtung. Das nennt man einen Zykel in dieser Theorie und nennt es so einen Graph azyklisch, wenn er keine solche gerichteten Kreise hat. Natürlich gibt es Kreise, wenn man die Pfeilrichtungen nicht beachtet, also wenn man die ignoriert. Ich hatte ja vorhin schon die 96 und dann die Möglichkeit zur 54 direkt zu gehen oder über die 114 oder 144 oder was es war. Und dieser kleine Umweg führt ja dann zu so einem Dreieck und wenn man die Pfeilrichtungen nicht betrachten würde, hätte man ja da schon so einen kleinen Kreis aus drei Ecken. Oder auf Englisch nennt man so einen gerichteten, einen A-Zyklischen Graph, aber ein DAG, ein D-A-G, ein Directed Acyclic Graph. Was eigentlich ganz witzig ist, weil einige Leute beschweren sich auch darüber, weil es nämlich die Reihenfolge der Adjektive falsch ist. Also Directed Acyclic Graph klingt ja wie gerichteter, A-Zyklischer Graph. Und dann bindet A-Zyklisch stärker an Graph. Also denkt man erst mal, man hat einen Graph ohne Zykel, der nicht gerichtet ist. Und dann macht man noch irgendwie Pfeilrichtungen an die Kanten. Aber eigentlich ist es ja so, dass wenn man die Pfeilrichtung entfernt, dass es dann doch Zykel geben kann, nur dass die Zykel nicht die Richtung beachten. Ja, also in jedem Zykel muss man irgendwann gegen den Pfeil laufen, wenn man den Zykel langlaufen will. Naja, lassen wir das. Also DAG ist der gebräuchliche englische Begriff und der wird auch im Deutschen verwendet. Die Anzahl solcher Graphen kann man übrigens rekursiv ganz gut berechnen, wächst aber sehr schnell. Ist auch schon lange bekannt, das ist eine Folge mit kleiner Nummer in der OEIS, nämlich die Folge 3024. Und wenn ich da jetzt mal zum Beispiel schauen will, wie viele Möglichkeiten für die Story in meinem Roman es jetzt also gegeben hätte, für die 139 Kapitel, da komme ich aber schon in ein kleines Problem, denn bereits für vier Kapitel gibt es 543 mögliche Story-Verläufe, also 543 mögliche DAGs, gerichtete, a-zyklische Graphen oder a-zyklisch gerichtete Graphen. Und für fünf Kapitel gibt es schon 29.281 und das wächst sehr, sehr schnell. Also in der Tabelle, die bei OIS immer da so mitgeliefert wird, da geht das nur bis 15. Also 139 war dort nicht verzeichnet. Obwohl es jetzt mit einem Computer nicht schwer wäre, diese Zahl auszurechnen, ist sie dort nicht mehr verzeichnet, weil sie einfach riesig ist. So, auf OIS findet man auch noch andere witzige Verweise. Die Anzahl dieser DAGs auf N-Ecken ist auch zum Beispiel gleich der Anzahl der N-Kreuz-N-Matrizen, die nur 0,1-Einträge haben und nur positive Eigenwerte. Hm, wer hätte das gedacht? Aber manchmal ist das ja super nützlich für die mathematische Forschung. Also diese OES, die kann eigentlich nicht überschätzt werden in ihrer Nützlichkeit. Denn das könnte man sich ja vorstellen, dass man vielleicht in seiner Forschung doch mal sowas trifft. Hm, wie viele 0,1-Matrizen gibt es eigentlich, die nur positive Eigenwerte haben? Und das könnte man dann mithilfe der OIS direkt rausfinden, dass die irgendwie in Bjektion zu diesen DAGs stehen. So, meine Zeichnung ist so ein bisschen unübersichtlich und wenn ich jetzt am Ende, nachdem ich alles gesehen habe, nochmal angefangen hätte, hätte ich da bestimmt so ein paar Layout-Entscheidungen etwas besser treffen können oder gleich ein größeres Papier nehmen oder woanders anfangen auf meinem Papier. Aber natürlich gibt es auch Computer, die das gut können. Also Graphen-Layout ist zwar kein komplett triviales Problem, aber es gibt eine Software, die DAX darstellt, die Software DAGITI und die findet ihr unter DAGITI.net oder auf GitHub. Und warum es diese Software gibt und warum die sogar von der Deutschen Forschungsgemeinschaft DFG gefördert wurde, da komme ich gleich nochmal drauf zu sprechen. Aber diese Software ist jedenfalls so ziemlich einfach zu bedienen, also es läuft im Browser und dann macht man sich so eine Liste von seinen Kanten, also man kann einfach jetzt, ich könnte mir jetzt einfach hinschreiben, okay von K1, Kapitel 1 komme ich zu K96 und K54 oder was es war und dann gehe ich das ganze Buch einmal durch, schreibe mir diese ganze Liste ab und dann macht er mir ein schönes Bild. Und das Bild packe ich dann auch noch mal, das computergenerierte Bild, packe ich dann auch noch mal in die Shownotes und poste das. So, Und ich habe es aber jetzt per Hand gemacht, also da habe ich auch einen Algorithmus verwendet und das ist jetzt so ein grafentheoretischer Algorithmus, den man Breitensuche nennt und der gehört in der formalen Sprache der Algorithmen, gehört dazu der Klasse der uninformierten Suchalgorithmen, also ein uninformierter Suchalgorithmus. Ich weiß ja nur, dass es diesen Graphen gibt. Wenn ich das Buch jetzt neu habe, dann weiß ich irgendwie, okay, die Kapitel sind irgendwie so verknüpft über diese Kanten. Aber ich kann ja nicht unbedingt vorhersehen, wie der Graph aussieht. Und jetzt exploriere ich den Graphen und ich kann keine Information über den gesamten Graphen verwenden, weil ich einfach nur am Anfang des Buches anfangen kann und ich kann das Buch irgendwo aufschlagen und lokal den Graphen erkunden. Also wenn ich bei einem Kapitel bin, dann kann ich zwar rausfinden, wo führt dieses Kapitel jetzt hin, aber ich kann zum Beispiel nicht einfach rausfinden, ohne alles durchzuschauen, was für Pfeile kommen zu diesem Kapitel. Also das ist so ein Prinzip bei diesen uninformierten Suchalgorithmen. Und bei meiner Handzeichnung habe ich eben diese Breitensuche verwendet. Und das bedeutet genau das, was ich am Anfang beschrieben habe. Ich fange mit der 1 an und habe gesehen, die hat zwei Ziele. Und dann habe ich mir die beiden Ziele angeschaut und habe gesehen, die hat jeweils wieder zwei Ziele. Und dann schaue ich mir von diesen die Ziele wieder an und dann habe ich diese kleine Schleife entdeckt von 114 zu 54 und so weiter. Und das hatte für mich den Vorteil, dass ich dann irgendwie immer so ein bisschen genug Platz lassen konnte. Also ich habe dann die zwei Entscheidungen so in unterschiedliche Richtungen auf dem Papier gezeichnet, sodass dann noch möglich war, sodass ich genug Platz hatte für diese Auffächerung. Letztendlich fächert die Story aber natürlich nicht beliebig auf, weil das würde ja dann so ein exponentielles Wachstum an verschiedenen Handlungssträngen gibt, sondern es gibt nur eine ziemlich kleine Anzahl von Strängen, die dann wirklich parallel laufen, vielleicht so fünf oder so ist das an der dicksten Stelle. Und dann gibt es halt immer wieder Knotenpunkte, wo auch Stränge wieder zusammenlaufen und es gibt natürlich Enden, wo man irgendwie dann verloren oder gewonnen hat. Und es gibt auch noch einen anderen Algorithmus, der dann auch in Konkurrenz zu meiner Breitensuche steht und das ist die sogenannte Tiefensuche und die funktioniert so, dass man erstmal immer einen Strang bis komplett zu Ende verfolgt. Also das könnte ich zum Beispiel auch machen. Ich fange bei meiner Eins an und ich nehme dann immer die oberste Wahlmöglichkeit, immer die Wahlmöglichkeit, die mir als erstes angeboten wird. Und dann gehe ich immer die erste Wahlmöglichkeit, erste Wahl, erste Wahl, erste Wahl, erste Wahl, dann gehe ich bis zum Ende. Ich komme zu irgendeinem Ende komme ich ja. Also das liegt in der Natur, dass es keine gerichteten Kreise gibt, komme ich immer zu einem Ende. So, wenn ich bei einem Ende bin, dann gehe ich wieder zurück bis zur letzten Wahl und nehme bei dem letzten, den ich gemacht habe, nicht die erste Möglichkeit, sondern die zweite Möglichkeit. Und dann, aber ab dann wieder die erste, erste, erste, erste, bis ich wieder beim Ende bin, dann wieder zurück, bis ich das letzte Mal was gewählt habe und da die zweite Möglichkeit wieder bis zum erste, erste, erste, bis zum Ende. Und so kann ich auch den kompletten Graphen explorieren. Im Fall meines tatsächlichen Grafenmalens hätte das, glaube ich, zu einem Tod mit zwei von zehn Punkten geführt und da wäre ich dann zurückgegangen zur letzten Kreuzung, hätte dort die zweite Möglichkeit gewählt und dann immer die erste entlang des Pfades und so weiter und für mein händisches Malen hätte das, glaube ich, einen ganz anders aussehenden Grafen gegeben. Also ich hätte dann ja den ersten Strang, diesen langen Pfad, immer die oberste Entscheidung, wohl irgendwie am Rand des Blattes machen können. Und dann den ersten Abzweig direkt da drunter, das hätte wahrscheinlich irgendwie so strukturierter ausgesehen und wäre irgendwie so lang gezogen, stelle ich mir das jetzt vor. Ich habe es aber nicht gemacht, weil ich habe nur einmal die Breitensuche mit meiner etwas chaotischen Methode gemacht und ja, mich dann an der tiefen Suche, es hat schon ganz schön lang gedauert, also diese 139 Dinger da aufzumalen, so ganz schnell ging das jetzt auch nicht. Ich habe auch versucht, meinen Sohn mit einzuspannen, aber der hatte dann nach irgendwie Tiefe 3 hatte da keine Lust mehr, aber ich habe durchgehalten bis zum Ende. So, dann habe ich mir noch über eine Sache nachgedacht. Ich meine, ich habe das Buch noch nicht mal zu Ende gelesen. Ja, so richtig spannend. Also, naja, lassen wir uns nicht aus über die Schreibkünste der Star Wars Autorinnen und Autoren. Ist auch interessant, auf dem Buch steht auch überhaupt kein Autor oder Autorin vorne drauf, ja. Würde man ja denken, wenn man Autor oder so ist, dann würde man sich gerne auf dem Cover verewigen des Buches, das man geschrieben hat, aber irgendwie ist das, glaube ich, ja, also das steht einfach nur Star Wars, The Clone Wars drauf und die Coruscant-Krise und du entscheidest. Ein interaktiver Star Wars-Abenteuer-Roman und nicht mal Autoreninformationen. Ist ein Kollektiv, eine Firma, ein großer Konzern. Naja, wie dem auch sei, ich habe mich jetzt jedenfalls nicht gefragt, wie das Ding ausgeht oder wie es ausgehen kann, sondern ich habe noch darüber nachgedacht, mit diesen Zahlen. Die Autoren, die haben diese Zahlen der Kapitel komplett durchgemischt. Also man springt da ständig hin und her und muss ständig hin und her blättern. Das Buch, das habe ich ja aus meiner geliebten Stadtbibliothek ausgeliehen. Also Leute, geht in eure Stadtbibliothek. Es ist so ein Traum, dass es sowas gibt. Aber, also ich habe das Buch ausgeliehen und es ist schon ziemlich abgegriffen vom ganzen Blättern. Ich glaube, alle müssen da die ganze Zeit drin rumblättern. Naja, ist ja auch logisch, wenn man dann von 96 wieder zu 2 und von 2 wieder zu 71 und so hin und her geschickt wird. Und dann habe ich mich gefragt, könnte man die Kapitel nicht irgendwie auch anders anordnen? Ist es zum Beispiel möglich, die Kapitel so zu ordnen, dass man niemals wieder zurückgeht? Also, dass man immer von einer kleineren Zahl zu einer größeren Zahl geschickt wird. Also im Buch immer vorwärts. Also egal, welche Entscheidung man trifft. Und in der Ordnung, die die hatten, war das natürlich nicht so. Also die 26 schickt mich zur 81 und die schickt mich dann wieder zur 9, irgend sowas und das möchte ich vielleicht nicht. Und jetzt frage ich mich, könnte ich also die Kapitel komplett neu durchnummerieren und dann auch neu anordnen im Buch, sodass es immer nur hochgeht. Und ja, das ist möglich. Und es gibt sogar viele schnelle Algorithmen. Die so eine neue Anordnung der Ecken eines DAGs, eines gerichteten azyklischen Graphen, herausfinden, die nur linear viele Schritte in der Anzahl der Kapitel brauchen. Den Algorithmus kann man sogar beschreiben. Ein einfacher Algorithmus, der geht wie folgt. Man bestimmt erst mal die Startkapitel, von denen es ja eigentlich prinzipiell mehrere geben könnte. Also die Kapitel, wo man nicht hingeschickt werden kann. Also Kapitel, an denen es losgeht, wo man nie hinkommt. In meinem Buch war es nur Kapitel 1. und ich wusste auch, dass es nur Kapitel 1 war, da war diese Suche ziemlich einfach. Und von jedem von diesen Kapiteln aus macht man dann folgendes. Also man macht sich die sozusagen in eine Liste, ja. Und die kann ich auch in einer beliebigen Reihenfolge machen, ja. Also wenn da gar keine Kanten hinkommen, dann ist es ja egal, wenn ich da bin, dann komme ich nur zu anderen Kapiteln, die irgendwie sowieso später kommen sollen, ja. So, und ich muss ja also nur dafür sorgen, dass diese Startkapitel irgendwie als erste kommen, ja. So, von diesen Startkapiteln nehme ich jetzt ein Kapitel her und dann schaue ich, wo ich da hingeschickt werden kann. Ich nehme einfach ein Kapitel, wo ich von meinem Startkapitel aus hingeschickt werden kann. Also ein erstes Folgekapitel. Und an diesem Folgekapitel muss ich jetzt schauen, ob ich da noch auf andere Art und Weise hinkommen kann. Ob es noch einen anderen Pfeil gibt, außer den vom Startkapitel, wo ich gerade hergekommen bin, der auch zu diesem Kapitel führt. Also, ob da noch andere Pfeile hinzeigen. Ihr müsst denken, für diesen Algorithmus jetzt kenne ich den Graphen schon. Ja, ich habe den jetzt vor mir gemalt, weil der Algorithmus geht jetzt davon aus, dass ich den gesamten Graphen kenne. Das heißt, an jeder Ecke kann ich auch entscheiden, was kommt hier an, was geht hier weg, weil ich den Graphen schon kenne. Und das Ziel meines Algorithmus ist ja jetzt, eine Anordnung der Ecken zu finden. Okay, so und also ich bin jetzt an der Ecke und gucke, ob da noch andere Ecken ankommen, falls ja dann nehme ich die Ecke jetzt noch nicht auf, sondern ich entferne aus meinem Graphen die Kante von Kapitel 1 zu diesem Kapitel zu dem ich gerade gekommen bin ich hebe mir das Kapitel aber noch später fürs Nummerieren auf, weil ich ja gerade rausgefunden habe dass es noch andere Kanten gibt, wie ich da hinkommen kann und die, Kapitel, die da sind, die müssen ja noch davor kommen, deswegen nehme ich den jetzt noch nicht auf aber ich nehme auf jeden Fall diese Kante raus. Okay, so, falls es aber die einzige Kante war, falls ich auf der letzten oder einzigen Kante dahin gekommen bin, zu dem Kapitel, an dem ich jetzt gerade bin, dann nehme ich es in meine Liste der neuen Startkapitel auf oder ich gebe ihm einfach gleich die nächste Nummer. Also ich deklariere es als neues Startkapitel. Und ja, dieser Algorithmus funktioniert und in lineare Zeit, in der Anzahl der Ecken, findet der so eine Ordnung, man nennt es dann eine topologische Ordnung. Und so eine topologische Ordnung ist super wichtig, zum Beispiel für so Job-Scheduling nennt man das, also wie sagen wir mal so Arbeitsplanung, die Reihenfolge von Arbeiten zu planen. Da hat man ja zum Beispiel irgendwelche Abhängigkeiten, also wenn man eine komplizierte Maschine zusammenbauen will, so einen 3D-Drucker oder so, dann hat man irgendwie so eine mehrstufige Fertigung. Also um den 3D-Drucker zusammenzubauen, brauche ich erstmal einen Motor, einen X-Motor, Y-Motor, Z-Motor und ich brauche irgendwelche so eine Stangengetriebe, die muss ich also alle vorher herstellen. Und wenn ich jetzt nur eine Person bin, dann kann ich mir diesen, so einen Grafen hinmalen, in Abhängigkeiten. Also unten ist mein 3D-Drucker. Und für 3D-Drucker brauche ich diese und diese und diese Zutaten. Die müssen hergestellt werden. Dazu brauche ich diese und diese und diese Zutaten. Und dann kriege ich so einen gerichteten Grafen von Abhängigkeiten. Und hoffentlich ist er a-zyklisch. Dann kann man das nämlich machen. Und dann kann ich ihm eine topologische Ordnung angeben, die mir sagt, in welcher Reihenfolge ich jetzt diese Arbeitsschritte ausführen kann. Sodass immer, wenn ich einen Arbeitsschritt machen will, alle Voraussetzungen für diesen Arbeitsschritt schon erfüllt sind. Und dafür braucht man das. Der Algorithmus, den ich eben erwähnt habe, der hat sogar noch die schöne Eigenschaft, dass der auch gleichzeitig noch rausfindet, ob das so ein Deck war. Wenn es nämlich kein Deck war, dann ist der Algorithmus irgendwann fertig, aber es sind noch Kanten in dem über. Der entfernt ja eigentlich immer eine Kante in jedem Schritt. Und wenn am Ende, wenn er alle Vertizes durch hat, aber es sind noch Kanten über, dann ist irgendwas schiefgegangen. Und das, was schiefgegangen ist, es war kein Deck, es gab einen Kreis, das ist schiefgegangen. Okay, so, jetzt wollte ich noch einmal sagen, warum die DFG das Malen von solchen Grafen fördert. Also die DFG hat nicht gefördert, dass wir alle unsere Star Wars, Clone Wars, Coruscant-Krise Comic-Romane, nee, ist kein Comic-Roman, sondern du entscheidest interaktive Romane. Schön darstellen können, sondern hier geht nämlich eigentlich noch eine ganz andere interessante Mathe-Geschichte los, für die ich heute leider nicht mehr so viel Zeit habe, das machen wir in einer anderen Folge. Aber gerichtete Graphen, ohne solche Schleifen, die beschreiben auch kausale Zusammenhänge. Und es gibt einen ganzen Bereich der Statistik, der gerne ergründen möchte, wie es zu Dingen kommt. Das wollen wir alle im Leben, also die ganze Physik, die ganze Naturwissenschaft. Wir versuchen da irgendwie rauszufinden, was die Gründe für so die Dinge sind, die hier so passieren. Und ja, also die Statistik will ja zum Beispiel so Fragen beantworten, wie verursacht Rauchen Lungenkrebs. Solche medizinischen Fragen. Und die Forscherinnen und Forscher, die das untersuchen, die benutzen dazu statistische Methoden und solche Modellierungen mit Grafen, mit gerichteten Grafen. Weil ein gerichteter Graph kann ganz einfach ausdrücken, ist ein geeignetes Modell für eine kausale Abhängigkeit. Aus A folgt B. Und aus A folgt B ist was anderes als aus B folgt A. Also die Reihenfolge oder die Richtung eines Pfeils ist von entscheidender Wichtigkeit, wenn man Kausalität untersuchen will. Klassische Statistik. Untersucht Korrelationen, aber Korrelationen lassen eben keine Richtung zu. Das ist eben der Unterschied zwischen Korrelation und Causation, was ja oft diskutiert wird und natürlich ist es wünschenswert herauszufinden, ob es Korrelationen gibt, aber noch besser ist es herauszufinden, ob es Causationen gibt. Und dann, was wir in der Statistik messen können, sind Korrelationen, aber durch geschickt konstruierte Experimente und interessante mathematische Effekte kann es eben manchmal möglich sein, gerichtete Abhängigkeiten zu finden, die man dann als Kausation interpretieren kann. Zum Beispiel kann man solche Korrelationen finden durch Interventionen. Also das ist eigentlich das klassische medizinische Experiment. Man gibt eine Intervention, man behandelt einen Teil der Patientengruppe mit irgendeiner neuen Behandlung und schaut dann, wie sich etwas verändert und funktioniert. Da bricht man eben die Richtung auf durch Einwirken auf die Wahrscheinlichkeitsverteilung. Also man beobachtet nicht nur, sondern man designt ein Experiment. Und ein Modell, statistisches Modell, was dann aus so einer grafischen Struktur, so einem DAG sich ergibt, wäre zum Beispiel, dass entlang des gerichteten Graphen an jeder Ecke eine Berechnung stattfindet. Also die Ecke steht für eine Zufallsvariable und die nimmt vielleicht die Werte von den anderen Ecken, die Pfeile zu ihr haben, führt mit denen irgendeine Berechnung aus, summiert die zum Beispiel, gibt vielleicht noch etwas eigenen Zufall hinzu, aber so wird die Information entlang des Graphen, entlang der Pfeilrichtungen weiter transportiert und ja, damit kann man eben ganz viel modellieren. Das läuft so ein bisschen unter dem Namen Base-Schnetze auch, obwohl natürlich auch der Begriff DAG sehr verbreitet ist. Und weil das so wichtig ist, von Medizin bis Quanteninformationstheorie, gibt es da eben sehr viele Tools. Und wenn ihr euch DAG-ITI, ich weiß gar nicht, wie man das ausspricht, also dieses Visualisierungstool herunterladet, werdet ihr sehen, dass es auch dann so an Statistiksoftware wie R angebunden ist. Gut, aber von der Kausalitätstheorie wird hier noch ein anderes Mal zu erzählen sein. Ich habe es auf dem Zettel, aber für heute mache ich erstmal Schluss hier. Ich danke euch fürs Zuhören, wünsche euch noch eine schöne Zeit. Kommentare, Ideen, Lob, Kritik erreichen mich am besten immer auf Mastodon unter at eigenraum at podcasts.social. Und da poste ich ja auch regelmäßig kleine Sachen, die zu kurz für eine Folge sind oder irgendwie visuell oder mir einfach auffallen bei meinem Surfen im Netz. Und vielleicht wollt ihr da mal reinschauen. So, ich mache mich jetzt auf die Suche nach einem Roman, dessen Kapitel kein Deck bilden. Vielleicht irgendwas mit Zeitreisen oder so. Also falls ihr da irgendwas wisst, gebt mir gerne einen Tipp und dann verliere ich mich da richtig schön in den Kausalschleifen und es wäre auch okay, wenn es nicht aus dem Star Wars Universum kommt und ja, also wir hören uns bald wieder, macht's gut und tschüss. https://eigenpod.de/eig055-romangraphen/