Graphenalgorithmen Flashcards
Wie ist ein ungerichteter Graph definiert?
Wie ist ein gerichteter Graph definiert?
Wie ist ein Multigraph definiert?
Wie ist ein Hypergraph definiert?
Wie ist Adjazenz definiert?
Wie ist Inzidenz definiert?
Wie bestimmt man den Grad eines Knotens in einem ungerichteten Graphen?
Wie bestimmt man den Grad eines Knotens in einem gerichteten Graphen?
Wie nennt man Graphen ohne Zyklen?
azyklisch
Wann ist ein ungerichteter Graph verbunden?
Wenn zwischen allen Knoten eine Verbindung besteht
Wann ist ein gerichteter Graph stark verbunden?
Wenn zwischen allen Knoten in beiden Richtungen eine Verbindung besteht
Was ist die Zusammenhangskomponente?
maximal zusammenhängender Subgraphen eines ungerichteten Graphen
Was ist eine starke Zusammenhangskomponente?
maximal zusammenhängender Subgraphen eines ungerichteten Graphen
Wann sind zwei Graphen isomoprh?
Wie ist ein Baum anhand von Graphen definiert?
Wie ist ein Wald anhand von Graphen definiert?
Wie ist ein DAG definiert?
Wie ist ein vollständiger Graph definiert?
Wie ist ein bipartiter Graph definiert?
Wie ist ein planarer Graph definiert?
Graph lässt sich ohne Kantenüberschneidungen zeichnen
Wie lassen sich Graphen repräsentieren?
- Adjazenzmatrix
- Ajazenzlisten
Was ist der Vorteil an einer Adjazenzmatrix?
Effizienter Test auf das Vorhandensein einer Kante
Was ist der Nachteil an einer Adjazenzmatrix?
Speicherbedarf von Θ(N^2)
Was sind die Vorteile von Ajazenzlisten?
Beschreib die Breitensuche
1
Was ist ein BFS-Baum?
Welche Laufzeit hat BFS()?
Baum, der bei der Breitensuche entsteht
Θ(V+E)
Was bestimmt man durch die Breitensuche?
Den kürzesten Pfad von s nach u
1
Beschreib die Tiefensuche
Was ist die Laufzeit?
Θ(V+E)
Was bedeutet DFS-Wald?
Was besagt das Klammerungstheorem?
Beschreib das Theorem der weißen Pfade
Was sind Baumkanten?
Baumkante: wird durchlaufen beim ersten Besuch von v
[dicke rote Kanten]
Was sind Rückkanten?
Rückkante: zeigt auf einen Vorgänger im DFS-Baum [Typ B]
Was sind Vorwärtskanten?
Vorwärtskante: zeigt auf einen Nachfolger im DFS-Baum
[Typ F]
Was sind Querkanten?
Querkante: nicht von anderem Typ [Typ C]
Beschreib die Kantenklassifikation während der Tiefensuche
In einem ungerichteten Graphen, was gilt für (v, u), wenn Type[(u, v] = TREE ist?
TYPE[v, u] = BACK
In einem ungerichteten Graphen, was gilt für (v, u), wenn Type[(u, v] = BACK ist?
TYPE[(v, u)] = FORWARD
Beschrieb topologisches Sortieren
Wie ist eine starke Zusammenhangskomponente definiert?
Was ist ein transponierter Graph?
Alle Pfadrichtungen umgekehrt
Was ist ein Komponentengraph?
ist ein DAG
Wie kann man die Starken Zusammenhangskomponenten von einem Graphen bestimmen?
- Tiefensuche
- Kanten invertieren
- Knoten besuchen in absteigender Reihenfolge nach der finishing time
- Tiefensuche für Knoten und speichern der SCC Information
In welcher Reihenfolge werden die Kompontenten bei der Suche von SCCs ausgegeben?
In einer Reihenfolge einer topologischen Sortierung
Was ist das MST-Problem?
Was sind Greedy Algorithmen?
Wie sind sichere Kanten im Kontext von MSTs definiert?
Definiere eine leichte Kante im Kontext von MSTs
Was gilt für eine leichte Kante, die einen Schnitt eines Graphens kreuzt?
Sie ist eine sichere Kante
Beschreib den Kruskals Algorithmus
- A beschreibt einen Wald, mit jeder Kante werden zwei Bäume zu einem verschmolzen.
- Zu Beginn haben wir |V| Bäume mit je einem Knoten.
- Kanten werden mit aufsteigendem Gewicht eingefügt.
- Schnitt trennt jeweils einen Baum vom Rest des Graphen.
Was ist die Idee der Union-Find Datenstruktur?
Bschreib union-by-rank
(UNION-Operation)
hänge den flacheren Baum unter den tieferen
Beschreib path-compression
(FIND-SET-Operation)
hänge alle Teilbäume auf dem Pfad zur Wurzel unter die Wurzel
Was löst der Ford-Fulkerson Algorithmus?
Das Max-Flow-Problem
Wie geht der Ford Fulkerson Algorithmus vor?
- findet wiederholend argumentierende Pfade durch den residualen Graphen
- argumentiert den Flow
bis keine AP mehr gefunden werden können - addiert dann die bottleneck-values
Was ist ein argumentierender Pfad?
ein Pfad mit einer ungenutzen kapazität größer als 0 von s zu t
Wie argumentiert man den Flow?
Man aktualisiert die Flow Daten der Kanten in einem argumentierenden Pfad, indem man den kapazitätswert-flowwert der kleinsten Kante hinzuaddiert.
Dannach verringert man den flow der Backwards-Kanten
Wie funktioniert der Edmonds-Karp Algorithmus?
wie ford fulkerson method, aber:
Wähle als augmentierenden Pfad den kürzesten Pfad (uniformes Kantengewicht von 1) von s nach t
Was ist Maximales bipartites Matching?
