Video 11-2: Graphen Terminologie & Definitionen

0:01 Im nächsten Abschnitt schauen wir uns also die Begriffe an, die man in dieser Graftheorie verwendet als gemeinsame Abstraktion für diese ganz verschiedenen Anwendung. Die Beispiele, die Sie gesehen haben, da gab es natürlich jeweils für Entitäten und Beziehungen eine natürliche Bezeichnung, die für diesen Kontext gut passt. Aber wir hätten gerne Begriffe, die wir verwenden können, zumindest unter uns Informatikern, äh die da so bisschen davon abstrahieren. Und genau das ist äh was man in der Krafttheorie entwickelt hat. Die Kernbegriffe, die allerwichtigsten sind eigentlich nur drei. Das kriegen Sie auf jeden Fall hinsicht zu merken. Es gibt den Graf selber. Das sind natürlich Knoten und Kanten. Äh wie gesagt, Synonym Netzwerk für mich das gleiche. Äh, was sind diese beiden Bestandteile? Ich habe einerseits Knoten, das sind die Entitäten. Auch dafür gibt's eine Reihe von anderen Begriffen, weil es eben aus so vielen Bereichen kommt, ist mal das eine mal das andere gebräuchlich. Besonders knuffig finde ich ja auf Deutsch Ecke.

1:00 Ich denke, das kommt aus der Geometrie, aus so 3D Formen. Da macht das vielleicht Sinn. Auf Englisch ist Vertex die übliche Bezeichnung, die man natürlich auch auf Deutsch verwenden könnte. Äh, Knoten ist, glaube ich, das gebräuchlichste. Daran werde ich mich halten. Ähm, in Formeln nennen wir die klein V nach englisch Vertex und groß V die Menge aller Knoten. Das ist so Standard, dass es sich damit abfinden müssen, dass das die englischen Begriffe verwendet. Das möchte ich nicht ändern. Äh, die Kanten sind Beziehung zwischen genau zwei Knoten und da gibt's auch alle möglichen Synonyme für. Ähm, ich werde mich bemühen, auch wieder hier bei den Standardbezeichnungen zu bleiben. Auf englisch Edge ist so das häufigste in Formelsprache E für Edge auch da wieder und groß e die Menge aller Kanten. Okay. Und ein Graf ist dann in Kurzform einfach diese dieses geordnete Paar von der Menge aller Knoten und der Menge aller Kanten. Soweit so gut.

2:06 Also Knoten und Kanten, darum geht's. Ähm, für die weiteren Details muss man ein bisschen Fallunterscheidung treffen. Ich werde den Teil hier relativ kurz halten. Ich wollte es aber am Anfang als Kapitel haben, damit Sie später noch mal zurückscrollen können, was es da so an Auswahl gab und die Begriffe an einer Stelle gesammelt sind. Da wir gesehen haben, Grafen kommen in so vielen verschiedenen Bereichen vor, ist es nicht verwunderlich, dass man manchmal teils andere unter äh Klassifizierung braucht. Und wir haben ein paar davon ja auch schon gesehen. Z.B. Wir können Kanten entweder eine Richtung haben oder eben nicht eine Richtung haben. Dann kann man sie in beide Richtungen verwenden.

2:45 Wenn sie eine Richtung haben, dann heißt das Ding ein gerichteter Graf. Directed Graph auf Englisch und wir wenn auch die Graf auf Deutsch habe ich viel schon gelesen. Ähm ist die Abkürzung für die englische Version, aber ist einfach bequem und kurz und knackig. Wenn die Kanten keine Richtung haben, dann ist es halt ein ungerichteter Graf. Ich versuche das so extra deutlich auszusprechen, weil es so viele ähnliche Begriffe gibt. Es gibt da unten dann ungerichtet und ungewichtet. ähm manchmal ein bisschen ein Zungenbrecher. Äh die Frage, ob ich zwischen zwei Knoten höchstens eine Kante haben kann, also entweder keine oder es gibt die Kante. Wenn das der Fall ist, dann nennen wir das einen einfachen Graf und das wird unsere Standardannahme auch sein. Aber man könnte auch manchmal den Wunsch haben, dass es zwischen zwischen zwei Knoten irgendwie mehrere Parallele Kanten gibt. könnte man in dem Straßennetz sicher sich vorstellen. Äh, dann ist es eben ein Multigraf oder ein Graf mit parallelen Kanten.

3:52 Ähm, gibt dann noch diese andere Anomalie, dass ich so eine Kante von mir zu mir selbst zurückhabe. Äh, fällt mir jetzt kein so richtig gutes Beispiel ein, wo das natürlich vorkommt, aber ähm die nennt man dann Schleifen und der Standardfall wird für uns eigent sein, dass wir annehmen, dass es die nicht gibt. Dann ist der Graf schleifen frei. Und das letzte ist, die Kanten können entweder eine Gewichtung haben. Manche Kanten sind teurer, günstiger, schneller, wie auch immer. Was dann die Anwendung darunter versteht, ist das eine. Wir nehmen einfach anders irgendwelche Zahlen, dann ist es eben ein gewichteter Graf, ansonsten ist es ein ungewichteter. Okay, sie werden in den diversen Anwendungen sehen, dass es natürlich ist, das eine oder das andere zu haben. Ich möchte nur am Anfang vorweg sagen, wenn jemand sagt Graf, dann müssen Sie wissen, welche Version davon ist gemeint.

4:50 Um das einmal auch festzuhalten, äh für diese zwei Hauptarten, nämlich gew gerichtete und ungerichtete Grafen, möchte ich einmal eine sinnvolle formale Definition angeben. Auf denen werden wir uns wenig versteifeln, aber wenn Sie in Übung und sonst wo irgendwie mal was etwas gründlicher beweisen sollen, dann müssen sie ja irgendwie wissen, wie man die Grafen hinschreibt. Am Ende ist alles mengenle, also hier die Definition für ungerichtete Grafen.

5:18 Äh unsere Standardannahme, also wenn nichts anderes irgendwie explizit genannt ist, dann gilt ein Graf ist für uns immer ungewichtet, ungerichtet, schleifefrei und einfach. Also keine Zahlen an den Kanten, keine Richtungen an den Kanten, keine Kanten von einem Knoten zu sich selbst zurück und keine Parallelen Kanten zwischen zwei Knoten, höchstens eine. Dann kann ich den Graf so aufschreiben, meine Knoten sind eine endliche Menge. Darf ich mir aussuchen, was das genau ist? Und die Kanten sind eine Teilmenge aller zweielementigen Mengen.

5:53 Dafür gibt's keine schöne Standardnotation, also haben wir eine erfunden. Ähm gibt auch verschiedene Bücher, die da verschiedene erfunden haben. Was hiermit gemeint ist, ist einfach die Menge aller Teilmengen von Knoten, die genau zwei Knoten enthalten.

6:11 Hier ist ein Beispiel. Also formal aufgeschrieben sind die die Knoten hier einfach die ersten natürlichen Zahlen. Wie sich für Informatiker gehört, fangen wir bei der Null an. Werden wir noch drauf zurückkommen, äh warum wir das machen. Und die Kanten sind einfach zweielementige Mengen. Okay, Mengen eben deshalb, weil die Richtung keine Rolle spielt.

6:36 In aller Regel wollen wir Grafen zwar äh formal so modellieren, aber um damit zu arbeiten oder eine Intuition zu kriegen, malen wir die meistens in dieser Art Knoten jetzt irgendwie Kreise oder was ähnliches und die Kanten als Striche dazwischen. Das ist einfach eine natürliche Art, diese Information besser zugängig zu machen als hier diese äh textuelle Version. Ähm, aber bitte dran denken, dass was gilt, nur diese Mengen sind und zwei Bilder, die die gleichen Mengen repräsentieren, sind der gleiche Graf. Dass diese Punkte hier eine XY Koordinate in der Ebene haben, das kennt der Graf nicht, hatte ich beim Straßennetz vorhin auch schon angedeutet. Also, das sind die gleichen Grafen, nur dass wahrscheinlich die Variante, den zu malen etwas bequemer ist.

7:26 Wenn Sie sowas suchen, dann gibt's ein ganz hübsches Tool, dass ich Ihnen einmal kurz zeigen möchte. Dafür kopiere ich mir noch mal den Graf hier. Kochshow, ich habe da was vorbereitet. Also, da gibt's eine Website, die heißt äh ja, der Link war auf der auf den Folien. Ähm, das kommt aus Competitive Programming Kreisen. Äh, was man da einfach tun kann, ist einen Graf angeben.

7:54 Man muss sagen, wie viele Knoten sind, dann liste ich die Knoten selbst. Das können die Zahlen 0 bis 5 sein, wie hier. Also, sie dürfen auch andere äh Labels vergeben. Und danach liste ich alle Kanten auf als hoffentlich selbsterklärend, wie das heißt. Und dann haben sie hier ähm diesen Graf und könnt i so rumschieben und der ähm hat so ein äh Force Driven Layout Algorithmus, der den so ein bisschen modifiziert. Dann kann man, wenn man so ein bisschen hier das Gefühl hat, ah, diese Kante da, die ist doof. Ich schiebe die fünf mal so ein bisschen mit Schwung daunter, blup. Und dann sieht der Graf bisschen besser aus. Also, wenn man das hier äh ein paar mal hin und her schiebt, dann kriegt man besseres Gefühl dafür, wie der Graf ähm vielleicht strukturiert ist. Man kann den aber auch die Knoten dann zwingen, an Ort und Stelle zu bleiben und wieder irgendwelche hässlichen Layouts konstruieren.

8:46 Wenn Sie da ein bisschen ähm an Beispielen mit rumspielen wollen, ist das, glaube ich, die die effizienteste Art, eine schöne Art, den Graf zu malen zu finden. Macht's intuitiver.

9:00 Das ist alles zu ungerichteten Grafen. Also die Formul Formalisierung, die Sie im Kopf haben sollten, ist einfach diese hier. Ähm, es gibt eine Variante noch, das ist die für gerichtete Grafen. Da möchte ich jetzt natürlich ähm sowas erlauben, dass es eine Kante hier auf für den Hinweg und eine für den Rückweg gibt. Und deswegen kann ich das nicht als zweielementige Mengen darstellen. Stattdessen Knoten genauso, aber die Kanten sind jetzt einfach Paare von Knoten. Und hier die etwas sperrige Notation, das heißt ja einfach, es sind beliebige Paare, aber ohne schleifen.

9:49 Auch hier wieder die Standardannahme. Wenn jemand Ihnen sagt, wir haben einen Diegraf und steht sonst nichts weiter dabei, dann ist er ungewichtet, schleifenfrei und einfach und dann passt zu dieser Formalisierung. Auch da wieder ein Beispiel. Ähm, hier haben wir jetzt einfach Paare statt Mengen. Das heißt, insbesondere ähm schlechtes Beispiel, hier gibt's keine Kante hin und zurück, aber könnte ich natürlich haben. Schmuggeln wir mal noch eine ein und dann hätte ich diese Rückwärtskante hier eben auch. Das ist hier erlaubt. Für den gerichteten Grafen macht das Sinn, das ist ja nicht redundant, dass ich hier hin und zurücklaufen kann. Ist nicht äh selbstverständlich. Ähm, auch da noch mal in diesem Tool können Sie auch auf gerichtet wechseln. Dann ist einfach jetzt die Kanten gehen jetzt von dem linken zu dem rechten, ansonsten hat sich hier nichts verändert. Ja, und dann können sie auch hier das gleiche Spiel betreiben und ein bisschen versuchen, den Graf schöner anzuordnen. Er will nicht mehr da oben.