Algorithmen und Datenstrukturen

Graphenalgorithmen

• Ein ungerichteter Graph ist ein Paar (V,E) mit V als Menge der Knoten und E als Menge der Kanten.
• Graphen können durch Adjazenzmatrix (O(∣V∣²)) oder Adjazenzliste (O(∣V∣ + ∣E∣)) dargestellt werden.
• In O(n^2) Schritten kann man zwischen diesen Darstellungen konvertieren.

Tiefensuche

• Die Tiefensuche wird verwendet, um einen gerichteten Tiefensuchwald berechnen, welcher bei einem ungerichteten Graphen ein Baum darstellt.
• Jeder Knoten bekommt eine Start- und Endzeit.
• Es gibt Baum-, Vorwärts-, Rückwärts- oder Querkanten.

Zusammenhangskomponenten

• U und V sind zusammenhängend, wenn es einen Pfad von u nach v gibt.
• Es gibt keine echte Obermenge davon.
• In einer Tiefensuche sind alle schwarzen Knoten eine Zusammenhangskomponente.

Finden von Kreisen

• Azyklisch = kein Kreis, dies geschieht, wenn es keine Rückwärtskante gibt.

Residualnetzwerke

• Ein Residualnetzwerk ist ein Netzwerk, dem Fluss.
• Es wird als G_f bezeichnet.

Augmentierende Pfade

• Ein s-t Pfad p in G_f ist ein Augmentierender Pfad.
• c_f(p) heißt Restkapazität von p.
• Das ist die kleinste Kapazität einer Kante im Augmentierenden Pfad.

Ford-Fulkerson-Methode

• Zur Bestimmung des maximalen Flusses.
• Wir wählen einen Augmentierenden Pfad.
• Wir wählen hierbei immer den kürzesten Weg.

Schnitte in Netzwerken

• Ein Schnitt teilt einen s-t-Netzwerk in S und T auf.
• f(S,T) ist der Fluss über (S,T), dass heißt, was von S nach T fließt.
• Die Kapazität ist c(S,T), dass heißt, was von S nach T fließen kann.

Bipartites Matching

• Wir haben einen ungerichteten Graphen gegeben, der der aus zwei Gruppen besteht.
• Wir wollen ein Matching (Paarung) maximaler Kardinalität, also möglichst viele.

Edmonds-Karp-Algorithmus

• Hierbei wird der kürzeste Pfad gewählt.
• Man sucht wieder einen Augmentierenden Pfad und versucht dann die Vorwärtskante zu erhöhen und die Rückwärtskanten zu verringern.

Bellman und Ford

• Dieser Algorithmus ermöglicht das Finden von kürzesten Pfaden auch mit negativen Gewichten.
• 1. Der Startknoten bekommt die Kosten 0, die anderen n ∞.
• 2. Danach wird geprüft, ob die Kosten für den Anfangsknoten der Kante plus den Wert der Kante.

All Pairs Shortest Paths

• Eingabe: gerichteter Graph mit Kiantengewichten, Ausgabe: Abstände und kürzester Weg zwischen allen Knotenpaaren.

Floyd Warshall

• Wir erstellen eine Matrix wie bei den Graphen, nur, dass wir dort das Kantengewicht eintragen.
• Wir versuchen nun den Pfad zu finden für die mit unendlich markierten Felder.

Breitensuche

• Breitensuche ist das Gegenteil von Tiefensuche.
• Eine Breitensuche enthält kürzeste Pfade.
• Hier gibt es nur die Discoverytime.

Netzwerkalgorithmen

• Netzwerkfluss: Ein Fluss hat eine Quelle s und eine Senke t.
• s-t-Netzwerke: In einem solchen Netzwerk hat jede Kante eine Kapazität > 0 und eine Quelle und eine Senke.

Flüsse

• Ein Fluss ist eine Funktion, die Paare von Knoten auf reelle Zahlen abbildet.
• 1. Zulässigkeit: Der Fluss kann maximal die Kapazität c erreichen.
• 2. Symmetrie: f(u,v) = -f(v,u).
• 3. Fluerhaltung: Das, was rein kommt, geht wieder raus, außer bei s und t.
• 4. |f| ist der Gesammtfluss.

Maximaler Fluss

• Wir haben ein s-t-Netzwerk gegeben und wollen einen Fluss mit dem maximalen Wert erhalten.