Video 11-1: Graph-Anwendungen

0:02 Im nächsten Kapitel schauen wir uns Grafen an und Grafalgorithmen, insbesondere. eine Abstraktion, die in ganz viel begegnet, begegnen wird, vielleicht auch schon begegnet ist und zu der es äh ein paar Standardrezepte gibt, mit denen man ganz oft relativ schnell zu Ergebnissen kommen kann und man muss da einfach auch die Begriffe ein bisschen kennen, dann können sie auch ganz tolle Bibliotheken einfach verwenden, aber wenn sie gar nicht wissen, was so die äh zugrunde liegenden Mechanismen sind, dann ist es sehr schwierig, das sinnvoll einzusetzen. Also, es lohnt sich wie natürlich in allen Kapiteln, aber hier lohnt sich es noch mal besonders aufzupassen auch äh gerade wenn sie sich in angewandter Richtung sehen oder Data Science studieren.

0:46 Äh wir werden uns durch diverse Kapitel durch ähm arbeiten. Sehen Sie dann. Äh, ich möchte aber zuerst ein bisschen motivieren, warum wir uns überhaupt mit diesen Konstrukten beschäftigen.

0:57 Machen mal erst ein bisschen Spaß zum alle wieder an Bord holen. Und natürlich hat die Frage auch so einen leicht ernsten Hintergrund. Äh Graf ist leider ein Wort, das überladen ist mit diversen Bedeutungen.

1:14 Also Ziel in der Aufgabe ist, dass zu Buchstaben Zahlenfahrer angeben für alle, die zusammenpassen. Sie dürfen mehrere schicken. Okay, ich glaube, ich ähm verstecke da nicht allzu viel spannendes, wenn wir zwischendrin mal reinspitzeln.

2:07 Also, da gibt's so ein paar äh die hervorstechen und dann gibt's auch so ein paar Rand Dinger. Da geht die Frage wieder. ist jetzt nicht die allerernsteste Frage. Ist aber glaube ich ein alte Klausuraufgabe mal gewesen. In äh anderen Institutionen hatten wir das verwendet als äh dafür dafür bestehen sie nicht alleine, aber irgendwann muss man anfangen.

2:43 Okay, wenn sie so ein bisschen gesettelt hat, ich lass sie mal noch abstimmen ganz kurz, warum die Frage überhaupt ähm ist natürlich, dass Graf ziemlich vieles heißen kann und äh ein paar davon sind natürlich irgendwie ein bisschen quatschig. Also hier der gibt die Antworten so jetzt sukzessive äh von wenig relevant für uns zu mehr relevant für uns frei. Äh das ist der Acentraf aus z.B. Französisch, denn würde man etwa so schreiben? Ich glaube tatsächlich auch mit einem Axor, aber ich wollte es nicht zu einfach machen. Äh, okay. Ist natürlich eigentlich kein Graf. Grave of Englisch. Okay, kennen Sie auch. Hat hoffentlich auch nicht so viel mit uns zu tun. Wobei Tombstones tauchten eventuell beim Hashing ja mal auf. Ähm, dann gibt's natürlich den Zahl Grafzahl so rum. Äh, The Count auf Englisch auch sehr schön. ähm kennen Sie hoffentlich auch äh weniger relevant für uns. Das sind die falsch geschriebenen Grafen. Also ein Steffig Graf, na ja, das Schwarz-Weißbild ist vielleicht mittlerweile ganz passend. So alt ist sie nun auch nicht, aber das war das, was irgendwie mit den passenden Rechten verfügbar war.

3:55 Für uns sind natürlich die Grafen mit pH hauptsächlich relevant und da gibt's mindestens diese zwei. Das sind die, die wir uns hier anschauen wollen. Aber es gibt natürlich auch das, was man vielleicht als Plot bezeichnen könnte, wenn man die Unterscheidung machen möchte. Ähm im mathematischen Sinn gibt's dann auch noch mehr Begriffe, die ähnlich sind. Man kann auch den Graf einer Funktion als die Menge dieser Punkte auf dieser Linie da bezeichnen. Habe ich auch schon so gesehen. Was soll das alles äh für Sie bedeuten? Sie müssen einfach, wenn jemand Graf sagt, fragen, was genau gemeint ist. Sonst weiß man eventuell nicht äh welcher da so äh tatsächlich gemeint ist. Okay, hier also noch mal äh die Auflösung. Waren da jetzt irgendwelche witzigen Paare dabei? Äh, also ich denke, sie haben äh ja, es okay, ich lese es nicht nicht mal vor. Gut, also alles sind an Bord. Wir wissen, es dreht sich im wesentlichen um diese Grafen, aber was ist das eigentlich und warum sollte ich mich äh dafür interessieren?

5:00 Die abstrakteste Version, würde ich sagen, ist diese Definition. Graf ist eine Konstruktion, wo es irgendwelche Entitäten gibt, irgendwelche Objekte und wir geh wir sind im Prinzip interessiert an diesen Objekten und ihren Beziehungen und speziell sind es paarweise Beziehungen, also immer zwischen zwei solchen Entitäten gemalt im Bild hier, indem wir da so einen Strich dazwischen ziehen. Sie sehen schon in dem Beispiel ist so angedeutet, dass diese Entitäten vielleicht irgendeine Bedeutung in der echten Welt haben. Da stehen kleine Zahlen auf diesen Verbindungen, auf den Beziehung. Das heißt, die können auch noch mit einer Gewichtung versehen sein und so weiter und so fort. Kommen wir auch gleich noch zu. Äh, sie finden die in ganz vielfältiger Form in ganz vielen verschiedenen Anwendungen, was wiederum ähm auch ein paar äh weitere Begriffsverwirrungen nach sich zieht. Ähm, synonym für uns sind Netzwerke zu Grafen. Ähm, man kann da sicher irgendwie auch Unterschiede sehen. Im Kontext von dem von den Grafalgorithmen würde ich sagen, wir beiden sind das gleiche. Also oft sehen Sie Netzwerkanalyse als etwas als Begriff, der häufig verwendet wird, heißt im Wesentlichen Arbeiten mit solchen Grafen. Äh, wo findet man die? Z.

6:19 äh soziale Netzwerke, wo es um Personen und ihre Beziehung geht oder physische Netzwerke, wo es z.B. um Straßenkarten gehen könnte oder auch irgendwelche Stromleitungsnetze die Unterscheidung zwischen Worldwide Web und Internet äh wird so landläufiger vielleicht gleich gesetzt. Internet ist wirklich die das Netzwerk, das physische Netzwerk der Rechner mit Backbones und all den ähm der Infrastruktur dazu. Und Worldwide Web sind die Webseiten, die quasi die Inhalte, deswegen auch Informationsnetz, also das Worldwide Webin Webseiten mit Links dazwischen. Äh gibt's natürlich noch mehr Netzwerke, die inhaltlicher Art sind ontologien sind Begriffe, die in Beziehung stehen. Man könnte vielleicht neuer sagen, Knowledge graphs wäre so äh Ding, was man viel findet. Da haben dann die Beziehung auch noch eine eine Bezeichnung und dann gibt's jede Menge äh aus den Wissenschaften ähm andere äh Arten von Daten, die sich irgendwie so darstellen, dass da Entitäten mit Beziehungen vorkommen. Wenn man sich diese Beispiele so anschaut, dann könnte man fast fragen, haben die denn überhaupt irgendwas gemeinsam oder ist da nicht mehr trennendes, als sie verbindet?

7:37 Und es macht aber Sinn, die alle zusammen zu betrachten aus einer algorithmischen Sicht, denn es gibt Fragestellungen, die in diesen sehr unterschiedlichen Bereichen immer wieder auftauchen und die sich übertragen lassen. Ist jetzt erstmal ein hohes Versprechen, aber sie werden ein paar Beispiele noch sehen, hoffentlich. Ähm, das heißt, wir wir können uns da Lösungen erarbeiten, die man in verschiedenen Bereichen verwenden kann. Und aus Software Ingenieursicht ist wieder verwendbarer Code das Beste, was wir bauen können. Und insofern sind diese Algorithmen, insbesondere diese Grafalgorithmen, die wir uns hier anschauen werden, die ultimativen wieder verwendbaren äh Software Stücke, weil sie in in ganz ganz unterschiedlichen Bereichen tatsächlich zum Einsatz kommen können. Um das bisschen konkreter zu machen, habe ich ein bisschen ähm gespielt. Einerseits äh ein nahliegendes Beispiel ist Routenplanung. Kennen sie alle, haben sie alle verwendet. Ähm z.B. wie man von hier am schnellsten zur Mensa kommt, da gibt's ja so ein Streit, ob man hier oben rumläuft oder hier rum geht, aber die Wahrheit ist offensichtlich.

8:43 ähm die Entitäten hier ist vielleicht gar nicht so klar, was man aus einer Straßenkarte für einen Graf machen würde. Zeige ich Ihnen auch gleich noch animiert. Ähm eigentlich macht am meisten Sinn, eine Straßenkreuzung als so ein Entität zu verwenden. Und die Beziehung ist, wenn zwei Kreuzungen durch eine Straße verbunden sind oder Straße können sie frei interpretieren. In dem Fall sind ja eher Fußwege. Ähm, im Allgemeinen sind die meisten solcher Wege bidirektional verwendbar, aber es gibt natürlich auch Ausnahmen und oft denken wir von so Strecken als gewichtet, entweder die Zeit, die es braucht, da lang zu gehen oder die Länge in Metern oder was auch immer. In der Regel haben die Gewichtung. Äh dazu ein kleines Spielbeispiel.

9:36 Also hier ist äh könnt sie auch auf der Website, wenn die dann wieder geht ähm selbst mit rumspielen. Op Street Maps ist Ihnen vielleicht ein Begriff. bei Alternative zu Google Maps, Apple Maps, sonst was Maps mit äh Community gepflegten Inhalten oder äh Informationen. Und sie können hier einen Bereich markieren und den in einen Graf umwandeln lassen. Live Demo ist natürlich immer riskant, weil das ähm Aufruf an diesen Server macht. Aha, schade. Wenn es nicht geht, dann gibt's noch die Offline Variante.

10:22 Dann schummle ich mal und habe das sozusagen schon vorbereitet. Äh ist ein bisschen wackelig, weil Open Source. Also, was Sie jetzt hier sehen, da müssen wir, glaube ich, näher rangehen, um irgendwas sehen zu können. Äh, da sind wir. Also sie sehen, es gibt an gewissen Punkten jetzt Knoten, nämlich immer da, wo mehr als zwei Wege zusammenführen. In der Abstraktion von dem Graf sind die Punkte an den richtigen Stellen gezeichnet, aber die Straßen sozusagen nicht. Die sind einfach als gerade Linien eingezogen.

10:54 Und wenn wir dann jetzt z.B. von hier zur Mens laufen wollen, können Sie die zwei Knoten anklicken und dann finden Sie den kürzesten Weg. Ähm, die die Karte ist natürlich das, was uns normalerweise äh interessiert, aber eigentlich sieht das so aus. Ja, für den Graf selbst gibt es nur diese Punkte und Verbindungen mit bestimmter Länge. Und selbst diese Anordnung in dieser zweidimensionalen Ebene gibt es für den Grafen eigentlich nicht unbedingt. Das ist etwas, was jetzt aus der Anwendung kommt für den Graf selbst. Und für die Frage, wie komme ich von einem Punkt am schnellsten zu einem anderen Punkt? äh ist nicht wichtig, dass diese Punkte in der Ebene angeordnet sind, sondern nur, dass ich die Längen der Distanzen, die Längen dieser Wegstrecken kenne. Okay, das ist ein Beispiel. Das ist relativ nahlegend, dass das irgendwelche Beziehungen zu einem Graf hat. Insbesonderes sind ist die Anwendung ihnen natürlich bekannt. Ein zweites, wo vielleicht viele die Geschichte kennen, aber für die, die sie vielleicht nicht kennen, erzähle ich sie einfach mal.

12:00 Ähm, der Patrank Algorithmus von Google. Ähm, mir ist bewusst, das ist jetzt für viele nicht mal mehr Lebenszeit, aber äh vor Google gab es Suchmaschinen, die im Wesentlichen so funktioniert haben, dass sie einen Suchbegriff suchen und die Website, auf der dieser Begriff am häufigsten vorkommt, die taucht im Ranking ganz oben auf. Das war halt so das einfachste, wie würde man eine Suchmaschine bauen, wenn man irgendwie versucht Leuten zu ermöglichen, nach Begriffen zu suchen? Ähm irgendwie finde ich, wenn ich jetzt nach Baum suche diese Millionen von Webseiten, irgendwie muss ich die Reihenfolge bestimmen, welche oben auftaucht, welche die wahrscheinlich relevanteste ist für den Nutzer, der gesucht hat. Und ähm die erste nahliegendste Variante war eben zu sagen, ich mache das abhängig von wie oft dieser Begriff z.B. auf der Seite auftaucht, vielleicht noch mit einem statischen Ranking gepart, dass manche Webseiten inherent wichtiger sind oder öfter angeklickt wurden. Kann man natürlich leicht ausnutzen, indem Sie auf Ihrer Website noch ein paar zusätzliche Vorkommen der üblichen Suchbegriffe unterbringen, die Sie abfangen wollen. Das war dann auch wirklich ein Problem.

13:10 äh und Googles erste Version, wie sie die Seiten angeordnet haben. Meines Wissens ist es mittlerweile deutlich anders und sie erzählen es einfach auch nicht mehr Betriebsgeheimnis. Aber die erste Version ähm ist eben eine völlig andere Idee, wie man diese Relevanz von Seiten bestimmen kann, nämlich indem man von der Idee ausgeht, dass äh auf relevante Seiten viel verwiesen wird. Sie haben also explizit diese Grafstruktur, die links zwischen Seiten als Hauptkriterium gewählt und gar nicht so sehr auf den Inhalt der Seite geachtet. Also der der Inhalt der Seite bestimmt, welche Seiten überhaupt in der in dem Ranking auftauchen. Das muss ihr Suchbegriff schon vorkommen, aber unter allen, die den Suchbegriff enthalten, wird die Seite nach oben gespült, die von vielen vertrauenswürdigen Seiten verlinkt wird. Das ist aber ein rekursives Problem. Woher kriege ich jetzt, welche Zeiten vertrauenswürdig sind? Und äh sie haben sich dafür im Prinzip folgendes überlegt. Angenommen, wir haben einen hypothetischen Random Surfer, der also einfach im Web den ganzen Tag unterwegs ist. äh die end die längste ähm Wikipedia Odyssee aller Zeiten. Äh sie klicken immer auf einen zufälligen Link auf der aktuellen Seite und der bringt sie zu einer neuen Seite und mit einer kleinen Wahrscheinlichkeit starten sie irgendwo völlig neu.

14:36 Ähm und das definieren wir als Relevanz. Wie lange verbringen Sie im Schnitt auf der Seite, die Sie suchen, unter all den möglichen Seiten. Das natürlich verteilt auf die, was weiß ich, Milliarden von Seiten eine furchtbar kleine Zahl pro Seite, aber relativ zueinander kann ich die trotzdem ranken. Äh, z.B. ein Mini könnte so aussehen. Hier sind die Webseiten und diese Seite 8 verweist z.B. auf Seite füllen. Deswegen gibt's diesen Pfeil und der Random Surfer würde jetzt hier einfach durch die Gegend flitzen. Ähm, ich mache mal diese das Stamping ist mit welcher Wahrscheinlichkeit verfolge ich tatsächlich einen zufälligen Link. Die verbliebenen 5% heißt, ich fange wieder zufällig irgendwo im Netzwerk an. Uniform aus allen Knoten gewählt. Und wenn Sie das so eine Weile beobachten, dann sehen Sie, es gibt schon Webseiten, auf denen wir im Schnitt mehr Zeit verbringen. Rein optisch auch jetzt mal abgesehen von der Größe, die die Animation dazu malt, sie sehen immer wieder den Knoten 3 aufleuchten, einfach weil viele Kanten dahinführen.

15:50 Es ist aber nicht ganz so einfach, dass es einfach nur die Seite ist mit vielen eingehenden Links. Äh, es kann auch sein, dass es eine wichtige Seite gibt, die nur einen ausgehenden Link hat und der führt immer zu ihnen. Das ist so ein bisschen globaleres Maß. Äh, das ist die Definition. Das ist sozusagen das, wonach Google die Seiten gerankt hat. Äh, was Ihnen vielleicht auch aufgefallen ist, ist das dauert relativ lange schon auf diesem kleinen Netzwerk, bis sich das ungefähr stabilisiert. Vielleicht noch ein Schritt zurück. Man kann mathematisch beweisen, das stabilisiert sich immer, wenn man es lang genug laufen lässt, gibt's so einen durchschnittliche Zeit, die man auf jeder Seite verbringt und die konvergiert in dem Sinne. Äh, das ist aber viel zu langsam, um das zu berechnen. Selbst auf diesen paar Seiten dauert's schon lang. Google macht das also anders. Und was eigentlich dahinter steckt, ist eine Markofkette für die die Mathematik dahinter kennen.

16:43 Ähm es gibt hier immer ausgehende Kanten, die sind gewichtet. Ähm und wir suchen die stationäre Verteilung. Wenn keiner dieser Begriffe Ihnen was gesagt hat, dann vergessen Sie es. Frauen Sie nicht wissen. Äh, ich wollte nur die Verbindung herstellen für die, die das schon kennen. Was wir machen, ist äh eine Simulation von diesem Random Surfer, indem wir am Anfang, jetzt schauen Sie mal hier auf das Bild auf der Seite mit den ähm Gewichtungen für die Knoten. Am Anfang hat jeder Knot, jede Seite eine gewisse Menge Wasser oder Wichtigkeitswasser und in jedem Schritt wird jetzt über die ausgehenden Links das Wasser her verteilt. Also, ich schiebe mein ganzes Wasser zu allen Seiten, auf die ich zeige, aber ich kriege natürlich auch Wasser von außen wieder, weil eben jemand auf meine Seite verweist. Selbst wenn ich das nur einen Schritt mal mache, ist schon ähm deutlich ungleich verteilt. Und hier unser Knoten 3 z.B. wieder hat deutlich mehr Wasser bekommen als die meisten anderen. Und sie sehen auch hier gibt's noch diese ähm Schummelstriche. Man kann natürlich in dem kleinen Beispiel auch einfach symbolisch ausrechnen, was die diese stationäre Verteilung ist. Und da sind wir nach einem Schritt schon recht nah dran. Wenn wir noch ein paar Schritte machen, dann schaukelt sich das dann relativ schnell auf so einen Wert ein.

17:58 Und jetzt passiert nur noch in den Nachkommerstellen was. Das ist der Page Rank Algorithmus. Äh letztlich eine eine große verteilte Matrixvektormultiplikation ein paar mal. Wie gesagt, wenn Sie irgendwann Marketten lernen, dann denken Sie an das zurück und dann ist das ziemlich einfach. Ähm Google Erkenntnis ist natürlich nicht nur, dass man diesen Algorithmus so verwenden kann, sondern die Implementierung auf einem verteilten Kluster für eine Milliarde Website ist noch mal ein bisschen kniffliger.

18:35 Also auch ein Graf ähm völlig anders verwendet. Äh, aber definitiv der initiale Erfolg von jetzt eine der größten Techkonzerne. Ähm, hatten wir glaube ich alles gesagt. Noch mal hier noch mal rausgekehrt. Ein Hyperlink von einer Seite auf eine andere Seite ist natürlich mit einer Richtung versehen. Ich kann die nicht unbedingt wieder rückwärts verfolgen. Anders als beim Wegennetzwerk, wo die meisten Straßen in beide Richtungen verwenden verwendbar sind.

19:05 Ein letztes Beispiel habe ich noch. noch mal ganz anderer Kontext äh Bioinformatik oder Biologie. Ähm will nicht so weit ausholen. Sie wissen vermutlich, wir haben alle DNA und ein Genom aus vier vier Zeichen, das die Appation codiert. Äh man könnte so tun, als wäre das einfach ein langer langer String. Im Grunde sind es mindestens pro Chromosom einer, aber nicht so wichtig. Ähm was durchaus ein äh eine Routine eine Routinemhode sein kann, um gewisse äh Erdbkrankheiten zu diagnostizieren, ist, dass man mal von dem Individuum das komplette Genom sequenziert. Wer weiß, wie viele ähm Buchstaben in unserem Genom sind, um und bei Größenordnung.

19:53 Okay, sehen Sie gleich. Ähm ist ja eine ganz witzige Idee, oder wie viel Information steckt eigentlich in uns zwar DNA? Ähm, das menschliche Genom hat etwa 3 Milliarden Basenfare, 3 Milliarden Zeichen. Das irgendwie viel, aber auch nicht beliebig viel. Ein paar Gigabyte, ne, am Text. Also, ich kann es als Textdatei speichern. Ähm, das ist nur für einen Chromosomsatz. Wir haben natürlich zwei von beiden Elternparen. Der witzigere Punkt fand ich ähm, wenn man die Differenz von einem Genom nimmt und dem Referenzgenom z.B. ähm ist die Differenz eigentlich nur so 20 Megb. Also ihr was sie individuell macht, können sie an E-Mail anhängen. Darum geht's mir aber gar nicht. ähm ein Genom zu sequenzieren hieße also diese 3 Milliarden Basenpaare auszulesen. Und wir tun mal so, als wäre das ein langer String. In Wirklichkeit sind es 20 oder 40 46, aber äh ja äh das hab wir trotzdem noch Millionen von Zeichen jeweils. Was man mit Labortechniken kann, sind aber nur kleine Schnipsel auslesen.

21:03 Also, ich hätte eigentlich gerne hier diesen super langen String, aber was ich bekomme sind nur Bruchstücke davon. Was ich bekommen kann sind Bruchstücke von ganz ganz vielen Kopien, htatausenden Kopien. Das heißt, die Bruchstücke, die überlappen sich und ich komme auch davon ausgehen, dass ich sozusagen von jeder Stelle Bruchstücke bekomme. Trotzdem ist das ein riesen Chaos. Ich habe dann hunderttausende von Bruchstücken, die alle nur tausendstel Millionstel je nach Rechnung von dem Gesamtstring abdecken. Wie kriege ich daraus eigentlich wieder dieses Genom zusammengepuzelt? Das ist die Aufgabe, das ist das äh sequenzieren von dem Genom. Das können Sie mittlerweile für 1000 € kaufen. Das ist also gelöst in dem Sinne. Und die Lösung ist rein algorithmisch. Die Labortechnik steckt, man kann da ein bisschen noch drehen und man kann es günstiger machen, aber die steckt ansonsten an diesem Problem fest. Der Rest ist Informatik und ähm die Kernalgorithmen sind da auch wieder auf einem Grafem aufgebaut. Aber bevor wir genauer lesen, wie das geht, zeige ich Ihnen einfach ein Beispiel wieder.

22:30 Also angenommen, das hier ist ist ihr komplettes Genom etwas kleiner gemacht. Ähm, dann ist was Sie aus dieser Maschine bekommen, äh Schnipsel. Das ist jetzt noch mal ein Stück vereinfacht. Ich habe jetzt sozusagen immer vier Zeichen genommen und an jedem an jeder Startstelle bekomme ich eins. Also, ich habe eine eine Kopie von dem von den vier Buchstaben vom ersten angefangen, dann eine Kopie von den vier Buchstaben beim zweiten angefangen und so weiter. Aber ich kriege die jetzt halt durcheinander gewürfelt und wir bauen daraus einen Graf in der folgenden Art. Aus jedem Schnipsel wird so eine Verbindung von zwei Knoten, die jeweils die ersten die ersten und die zweiten drei Zeichen enthalten.

23:16 Also dieses hier GATT wird zu Gat mit einem Strich zu ATT. Also ich lass das erste und letzte Zeichen jeweils weg und verbinde die. Das ist ein bisschen crazy, aber warten Sie ab. Äh, ich mache das für alle von diesen Schnipseln und dann gibt's natürlich manche wie diese beiden, bei denen diese Knoten das gleiche das gleiche Label haben. Das heißt, ich kann jetzt die Knoten identifizieren, die den gleichen Aufschreib haben. Und wenn ich Glück habe, so wie in diesem Fall, dann kann ich jetzt einfach dem einen Weg hier folgen. Schneckentempo. ähm und kann danach mein Genom rekonstruieren.

24:05 Und so funktioniert der Kram tatsächlich mit noch ein paar äh Feinheiten, die eben aus der Bioinformatik dann nötig werden, weil man nicht ganz so saubere Daten bekommt. Lassen Sie mich aber noch ein Beispiel zeigen. Mus do irgendwie Enter noch drücken.

24:27 Hier habe ich ein längeres Beispiel. Und hab das wieder in Schnipsel zerlegt. Wir machen das gleiche Spiel und ordnet die an. Aber diesmal kommt so ein etwas chaotischeres Bild raus. Und tatsächlich ist jetzt die Rekonstruktion nicht eindeutig. Ich kann zwar auch wieder solche Pfade finden, die quasi jede jede Verbindung einmal verwenden. Das ist eine Option, aber ich hätte auch diese zweite Option nehmen können. Und dann habe ich das Problem, dass diese zwei ähm Optionen beide möglich wären, dann funktioniert das nicht. In dem Fall ist die Lösung, wenn ich die äh Schnipsel etwas länger mache, dann geht's tatsächlich. Ähm ist jetzt in diesem Fall die echte Lösung ist halt, dass wir tatsächlich versuchen etwas längere Schnipsel zu haben, dann tritt das Problem nicht so sehr auf. Ähm ich will nicht zu sehr vom Thema abkommen, habe ich wahrscheinlich schon ein bisschen getan. Äh, ich möchte nur an der Stelle auch noch mal zeigen, wie ein Graf dahinter steckt. Der Algorithmus ist der, den Sie beim äh das ist das Haus des Nikolaus verfolgen, wenn Sie mal drüber nachdenken. Ist genau das gleiche. Wir suchen eine Möglichkeit durch den Graf zu laufen und jede jeden Strich genau einmal zu verwenden. Das ist genau, was Sie da auch beim aus des Nikolaus machen auf dem immer gleichen Beispiel, weil sie können ja auch noch, das ist das Haus und nebenan wohnt der Weihnachtsmann und so kennen sie. Man kann das noch größer machen. Ähm, das ist das für große Kinder. Also, die Entitäten sind hier Teilstrings von dem ganzen Genom und Beziehungen sind es gibt was, was die verbindet und ich versuche dann so einen Pfad zu finden.

26:17 Okay. Äh, das Ding heißt de Bring Graf, sollte ich vielleicht einmal noch sagen. Ähm, die Aussprache ist bei den niederländischen Namen ja nicht unbedingt äh selbsterklärend.

26:29 Also drei völlig verschiedene Beispiele. Ähm hinter jedem steckt ein Standard Grafalgorithmus. Einmal kürzeste Wege finden, einmal ja diese Markofketten äh bzw. dieses im Kreislaufen von dem Random Surfer und einmal Euler Eulerkreise finden, Euler Pfade finden. Und all diese ähm Algorithmen funktionieren wunderbar auf dem abstrakten Graf und lassen sich übertragen auf andere Anwendung.