Hallo, unser nächster Themenblock dreht sich um das Thema Graphen. Wir haben in der ersten Vorlesung schon gesehen, dass es verschiedene Datentypen gibt.

Und der Datentyp, mit dem wir uns hauptsächlich beschäftigt hatten, bisher war der rechteckige Datentyp, also ein Tabellendatentyp.

Aber gerade auf Daten, die von sozialen Netzwerken herkommen oder ähnlichen Objekten, da ist eine Grafenstruktur meistens praktischer.

Daher werden wir uns jetzt einige Zeit mit Grafen beschäftigen.

Und natürlich starten wir mit einer Definition.

Wir wollen verstehen, was ein Graf ist.

Es gibt sehr viele verschiedene Facetten zu diesen Grafen, aber ich denke, das sinnvollste Objekt sich jetzt hier hauptsächlich anzuschauen, ist der sogenannte gerichtete und gewichtete Graf.

Der hat drei Komponenten.

Die erste Komponente ist eine Menge von Knoten, das sind einfach nur Objekte.

Man kann sich erst eine Liste vorstellen, die haben dann später sozusagen eine Ausrichtung im Raum, kann man sich vorstellen, aber die sind nicht tatsächlich irgendwie örtlich fixiert,

sondern sie sind einfach eine lose Menge von Objekten, die irgendwo existieren.

Man visualisiert ihn dann örtlich angeordnet, aber aufgrund der nächsten Tatsache, nämlich der, dass die zweite Komponente von Grafen ist eine Menge von Kanten.

Und eine Menge von Kanten ist erstmal nur eine Teilmenge des kathetischen Produktes von Knoten, wieder die Menge der Knoten.

Wobei man schreibt, wenn das Objekt u,v in E ist, also hier sind natürlich u und v, sind beides Knoten, also sagt das Objekt u,v ist eine Kante, wenn,

das schreibt man dann kurz als u,v und dann nennt man u,v eine Kante von u nach v. Also was bedeutet das? Naja, es bedeutet einfach genau, was dran steht.

Man nennt das dann eine Kante, weil man es so zu visualisieren kann, das ist u und v und es bedeutet, es gibt hier so eine Verbindung von u nach v.

Also hier bei einem gerichteten Grafen ist die Reihenfolge wichtig, es gibt auch die ungerichteten Grafen, da ist es einfach nur eine Verbindung von u und v, aber nicht von u nach v.

Hier ist ein gerichteter Graf, da ist die Reihenfolge von u nach v hier wichtig.

Und dann gibt es eine Gewichtsfunktion, die einer Kante, also einem Objekt in E, eine Zahl zu eröffnen, also eine positive Zahl.

Also wenn wir eine Kante haben, die auch existiert, es gibt Kanten, die existieren vielleicht nicht, vielleicht gibt es diese zwei Kanten, dann hat es das hier ein Gewicht,

zum Beispiel, also das ist u, das ist v, das ist w und w von u,v ist dann eine Zahl und die schreibt man dann zu diesem Pfeil hier dazu.

Und Gewichtsfunktion, das kann es verschiedene Bedeutungen haben, entweder es ist ein Maß für die Stärke einer Verbindung, also wie eng verwandt sind die,

oder es kann auch eher das Gegenteil sein, wie groß der Abstand zwischen u und v ist, es könnte eine Kulisse der Kilometerangabe sein, es könnte aber auch so etwas sein wie ein Verwandtschaftsgrad oder so etwas ähnliches.

Das ist immer etwas im Kontext, alles für verschiedene Anwendungen, was so eine Gewichtsfunktion sein könnte.

Aber auf jeden Fall heißt es, u verbindet nach v mit einer Gewichtung, mit einer Stärke und v gewichtet, vw ist eine Kante mit einer anderen Gewichtung.

In dem Fall w von vw, ja w ist ein bisschen ungegünstig, hier ist w eine Kante, dann nennen wir das nochmal nicht w, sondern z.

Hier ist der Knoten z und wir haben eine Kante von v nach z mit Gewicht w von v,z.

All diese Dinge kann man jetzt, wenn man möchte, ganz kompakt in einer Matrix speichern.

Jetzt überlegen wir uns, wie das jetzt hier zu lesen ist, das ist immer eine quadratische Matrix, keine symmetrische Matrix, die hat jetzt hier sechs Einträge.

Das erste was wir ablesen ist, dass es sechs Knoten gibt, das ist die Anzahl der Zeilen auf Spalten, also machen wir eben mal sechs solche Knoten, die nenne ich jetzt a, b, c, d, e, f und ich schalte es jetzt einfach auch nochmal so hin, a, b, c, d, e und f.

Und jetzt wenn diese Matrix, die nennen wir jetzt einfach mal W und W von, ich nenne es jetzt i,j soll w von i,j sein.

Jetzt überlade ich hier die Notation, kleinwesende Funktion und W ist die Matrix, die wir bekommen, das ist hier auswertend in jedem Punkt und Null, also es ist die Wiesnfunktion, wenn i mit j verbunden ist und es ist Null sonst.

Also Null, eins gibt keine Kante und Impositionsgewicht heißt es gibt eine Kante mit gewissem Gewicht.

Dann schreiben wir dies noch einmal hier auf, ich gebe jetzt einfach mal hier diese Notation, diese Reihenfolge, natürlich haben die keine geografische Ordnung, diese Knoten, ich mal sie einfach irgendwie hin, das kann jetzt eine ungünstige Visualisierung sein, aber das werden wir gleich sehen.

Also es gibt eine Kante von a nach b mit Gewicht 0,5, es gibt eine Kante von a nach d mit Gewicht 1, von b kommen wir nach e mit Gewicht 1, von c kommen wir nach e mit Gewicht 0,3

und nach f mit Gewicht 1, von d kommen wir nach b mit Gewicht 0,2, e nach d, das ist hier, e nach d mit Gewicht 1 und von f nach f, so dies selbst mit Gewicht 0,3.

Jetzt sehen wir schon, das ist vielleicht nicht die aller günstigste Visualisierung gewesen, die man sich vorstellen kann, aber dennoch, also sie liefert jetzt hier so ein Bild von Knoten und Verbindungen zwischen diesen Knoten.

Wie gesagt, was dieses B jetzt genau bedeutet, das ist anwendungsabhängig.

So eine Matrix ist meistens eine sehr ungünstige Schreibweise, denn angenommen wir haben jetzt nicht nur 6 Knoten, sondern sagen wir 10 Millionen Nutzer in einer großen Webanwendung,

dann haben wir 10 Millionen Knoten, damit haben wir 10 Millionen mal 10 Millionen Kanten und das ist eine riesige Menge an Daten, die wir speichern müssen,

aber meistens ist es so, dass die Anzahl der existierenden Kanten nicht wirklich die Anzahl der Knoten noch 2 ist, sondern typischerweise fragmentiert sich der Graph irgendwie in, man könnte sagen Cluster,

Cluster ist vielleicht nicht das ganz richtige Wort, aber in Gruppierungen, in zusammenhängende Komponenten, in Klicken, man sieht ja, in Bereiche, die miteinander sehr stark vernetzt sind, aber nicht mit dem Rest stark vernetzt sind.

Typischerweise ist es so, dass die Anzahl der Kanten, die ein positives Gewicht haben, recht klein ist und dann ist es besser statt der Matrix eine Antiazenzliste zu machen,

also einfach nur eine Liste von, also zu jedem U sucht man nach allen Knoten, die von U aus erreicht werden.

Und bei einer gewichteten Graphen kann man natürlich auch noch zuspeichern die V und W, sodass U mit V verbunden ist und W ist die Gewichtsfunktion von U und V,

also so könnte man dann vollständig das Gewicht dazuspeichern.

Okay, also das ist meistens die Beste, aber meistens ist das wirklich damit tatsächlich zu arbeiten, gerade auf großen Graphen sollte man nie so eine vollständige Matrix hier sich anschauen.

Dann gibt es verschiedene andere Graphen, die relevant sind.

Es gibt nicht die klare Grapheneffektion, die für alle Fälle die richtige ist, also wir sprechen jetzt noch über ein paar Varianten davon.

Ungerichtete Graphen haben die Eigenschaft, dass wenn U nach V verbunden ist, auch V nach U verbunden ist.