Video 11-3: Ungerichtete Graphen API

0:03 Nachdem wir uns jetzt angeschaut haben, wie man Grafen formal definiert und dass sie auch in diversen Anwendungen wirklich hilfreich sind, wollen wir jetzt in die Grafalgorithmen einsteigen. Äh, der erste Schritt ist noch mal ein bisschen fokussiert auf speziell ungerichtete Grafen. Äh, ein paar Sachen sie da ähm natürlicher zu beschreiben und ein paar Probleme sind speziell für ungerichtete Grafen natürlicher. Deswegen fangen wir mit denen an und dann werden wir uns auch drüber unterhalten müssen, wie wir die wie wir Grafen im Computer repräsentieren. Darüber haben wir ja auch noch nicht gesprochen. Ähm noch mal zur Motivation, wie wir es auch ähäh schon gesehen hatten, äh Grafen kann man insbesondere auch für irgendwelche räumlichen Abstraktionen verwenden. Und wahrscheinlich ist die diese Abstraktion, dass man zwar Orte in der Wirklichkeit mit einem Knoten repräsentiert, aber die Verbindung gar nicht so malt, wie sie in der topologischen Karte zu sehen wären. Die Idee gibt's wahrscheinlich am direktesten, am klarsten in so Linien äh Plänen von öffentlichen Verkehrsnetzen.

1:06 Da hat man auch genau diese Art von Knoten und Verbindungen und man malt sie aber so, dass die Verbindungen leichter zu sehen sind, wo muss ich U-Bahn wechseln, wenn ich hier in Paris unterwegs bin, Metro dann. Ähm und es ist nicht mehr repräsentativ repräsentiert, dass die Abstände z.B. gleich sind oder die Punkte an der richtigen ähm an den richtigen Koordinaten liegen, das ist nur so ungefähr ähm aufrechterhalten.

1:33 Äh hier noch ein paar Begriffe ähm die wir teilweise schon hatten, aber am Beispiel ganz schön auch noch mal also Knoten hatten wir schon gesagt und Kanten.

1:50 Dann ist hier ähm wenn uns die Identität der Knoten nicht so wichtig ist, dann malt man oft einfach so ein Kreis, statt eine spezielle Zahl reinzuschreiben. Ähm, die Knoten haben einen Grad, das ist der Grad eines Knoten, das sind die Anzahlverbindungen, die da hingehen. Deswegen hat dieser Knoten hier gerade 3, weil es drei eingehende Kanten gibt. Dann habe ich hier Zusammenhangskomponenten auf Englisch vielleicht fast noch einfacher. Das sind Teile vom Graf, die nicht verbunden sind. Ja, also eine Komponente hier bedeutet von jedem von jedem Knoten zu jedem anderen kann ich kommen, indem ich nur überche Kanten laufe. Aber hier von hier da gibt's einfach keine Verbindung. Und äh dann gibt's hier noch den, das ist bisschen kniffliger, Pfad oder Weg, was manchmal in dem Kontext nicht synonym ist, äh wenn wir drauf kommen, wenn es wichtig wird. Äh hier ist ein Pfad ist einfach so eine eine Folge von Kanten, die ich nacheinander laufen kann, glaub ich, intuitiv. Ähm recht klar, was man damit gemeint ist, wenn das eine Straßenkarte wäre. Und das letzte ist auf Deutsch Pycho entweder Kreis oder Zykel.

3:15 Das ist eben ein solcher Weg, bei dem ich am Ende wieder bin, wo ich angefangen habe, ne? Viele der Begriffe sind relativ intuitiv, außer in den Randfällen ist es z.B. erlaubt, dass der Pfad ähm Umwege enthält. Also wäre es okay, dass ich irgendwie so laufe? Na, das sieht man jetzt nicht so gut. Ich das noch mal mit größer wäre. Oh, okay.

3:47 Wäre das ein gültiger Part, wo ich sozusagen eine einen Umweg gemacht habe und auf dem gleichen Weg wieder zurückkomme? Antwort hängt von der Definition ab. Manchmal möchte man das erlauben, manchmal nicht und gibt keine allgemeingültige Antwort. In aller Regel eher nicht.

4:06 Äh hier ist eine allgemeine Liste von Problema auf Grafen, die ich an der Stelle jetzt noch gar nicht groß durchgehen möchte. Da geht's, glaube ich, eher darum zu zeigen, es gibt eine ganze Menge Fragen, die man stellen kann oder stellen könnte und ähm die haben alle feste Namen, weil die alle an irgendeiner Stelle relevant sind. Wir werden uns nicht alle hier anschauen. Äh Teile werden ih da auch noch mal in anderen Vorlesungen wieder begegnen oder mindestens wenn sie da vertiefen. Hier ist auch kurz erklärt, was dahinter steckt. Äh was ich vielleicht betonen möchte, ist, dass die in der Schwierigkeit die komplette Spanne von algorithmischen Problemen abstechen abstecken. Es gibt Beispiele von Fragen, die sehr einfach zu zu lösen sind, wenn man ein paar Beispiele sehen. im Wesentlichen in in der gleichen Zeit, in der ich den Graf einmal lese, kann ich auch das Problem mit lösen und es gibt Probleme, die sind so schwierig wie die schwierigsten Probleme, die man eigentlich lösen kann und niemand ähm kennt einen effizienten Weg das zu tun.

5:02 Und es ist, wenn man nur die Definition von dem Problem anschaut, ganz und gar nicht offensichtlich erstmal welche welche sind. darum geht's hier so ein bisschen. Ähm heißt für Sie natürlich einfach, dass man da ein bisschen Bescheid wissen muss, wenn ihn jemand irgendwo in einem Anwendungskontext ein Problem vorsetzt und ihn z.B. sagt: "Ja, ich bräuchte so einen Hamilton Kreis, also einen Weg durch diesen Graf, der jeden Knoten genau einmal besucht." Dann sollten sie wissen nach dem Ende ihres Studiums, dass das eine sehr schlechte Idee ist und sehr schlechte Nachricht, wenn das genau ist, was Sie tun müssen, denn das ist ein NP vollständiges Problem, für das es höchstwahrscheinlich keine allgemeine Lösung gibt, keine Effiziente, die irgendwann fertig wird. Während das sehr ähnliche Problem der Eulerkreise hatten wir vorhin gesehen in in den Debroin Graf äh Grafen. Wenn ich jede Kante einmal verwenden will, ist das ein sehr einfaches Problem. Subtile Änderung in der Definition kann da große Auswirkungen haben. Äh das ist einfach so ist ein bisschen lästig, aber heißt halt, dass sie so ein bisschen Grundwissen über Grafalgorithmen einfach mitbringen können. Dann kann man sehr schnell ähm na ja unnütze Zeitverschwendung verhindern. Z.B. eine allgemeine Lösung für ein schwieriges Problem, wo niemand eine kennt, zu suchen oder ähm sich abmühen mit einem mit einem Problem, für dass es gute Algorithmen schon gibt, die man erstmal probieren könnte. Ja, wenn man sukzessive noch mal auf diese Probleme zurückkommen oder auf eine Teilmenge dieser Probleme.

6:40 Äh für die Vorlesung, wir gehen jetzt langsam zur Richtung wie repräsentieren wir Grafen im Computer? werden wir eine Konvention treffen, nämlich, dass die Knoten immer die ersten Integer sind und damit sind sie Array Indics. Das ist genau, wie wir sie verwenden wollen. Ähm, wenn ich das nicht habe, wenn ich meinen Graf mit irgendwelchen anderen äh Labels auf den Knoten habe oder irgendwelche anderen Namen für die Knoten, dann wissen Sie dank unserem äh Abschnitt über über Wörterbücher, über Symbol Tables, Symboltabellen und bin linbäume oder Hashing ja auch schon wie sie effizient von dem einen zum anderen übersetzen können. Also z.B. Wir könnten sie eine Hashtabelle verwenden, die diese Strings, die Namen der Knoten auf Indic abbildet und vielleicht noch ein Array für den Rückweg und dann können Sie immer hin und her übersetzen. Der Punkt ist aber, sie machen die Übersetzung einmal, wenn wenn Sie jemand fragt, was ist der kürzeste Weg von Mehrzweckgebäude zu Menser, dann übersetzen Sie einmal, welche Knoten im Graf sind. Für die ganze Rechnerei im Graf haben wir dann die effizienten Zugriffe über die Array Indic und am Ende übersetzen sie zurück, welcher Weg dann wie der Weg im ursprünglichen Graf hieß.

8:01 Okay. Wir hatten schon gesprochen Schleifen, sie ern sich und parallele Kanten, gleicher Begriff auf Deutsch, sind in aller Regel verboten. Liießen wir aus. ähm mit Ausnahmen ab und zu machen. Okay, damit können wir angeben, wie wir unsere Grafen repräsentieren. Erstmal als Interface in Java oder als ähm als API. Es ist kein Formal, kein Interface. Es ist eine eine Klasse direkt angegeben. Aber was ist so die Abstraktion, die wir verwenden wollen? Man kann einen neuen Graf anlegen, indem man die Anzahl Knoten festhält. Die Anzahl Knoten ist sozusagen statisch. Äh, die Kanten, die kann man sukzessive hinzufügen dieser Variante und dann kann ich ähm ich kann fragen, wie viele Knoten, wie viele Kanten gibt es und ich kann die Nachbarn von einem Knoten finden. Damit könnte man z.B. fühlenden Graf dann ausgeben.

8:59 Als Standardbeispiel haben Sie hier ähm dieses Miniprogramm, das letztlich einen Graf einliest und dann für jede Kante einmal so eine Zeile auf der Ausgabe produziert. Ähm können sich vielleicht vorstellen, wie das funktioniert.

9:21 Was wir uns noch mal im Detail anschauen wollen, ist wie man die Realisierung von diesen Funktionen und insbesondere dieser hier macht. Ich habe das bewusst jetzt sehr schnell übersprungen, weil wir gleich dann noch mal im Detail drüber sprechen im nächsten Abschnitt.

9:41 Äh typischer Code, der dann so einen Graf verwendet, könnte z.B. dieser sein, der den Grad von dem Knoten berechnet. Also, wenn ich einen Grafen habe und einen Knoten, der Knoten ist dann jetzt einfach ein int. Das hatten wir so vereinbart, das äh ist dann auch hoffentlich kleiner als dieses V.

10:01 Dann kann ich eben den Grad bestimmen, indem ich alle ausgehenden Kanten mir anschaue und hochzähle. Also, ich fang bei null an. Ich schaue mir alle Nachbarn von meinem Knoten V an, dass die W heißen, benutzen wir gar nicht und zählen einfach hoch. So, minimale ähm Benutzung von dieser API.