AA Flashcards Maximum Matching and Flows

q aosr/2a6va
Was ist der Satz von Berge
? aosr/2a6va/m/57nc

q aosr/41fui
Welche Algorithm gibt es um ein Maximum Matching in einem Bipatiter Graph zu berrechen?
? aosr/41fui/m/3h1v
Reduktion Maximum Matching auf Max-Fluss Problem
-> Ford & Fulkerson $O (m \cdot M)$
-> Edmonds and Karp Algoritums $O (m^{2} \cdot n)$
-> Dinitz’ Algorithm $O (m \cdot n)$
oder Satz von Berge nutzen
Bipartite matching via Alternating Paths $O (n \cdot m)$

q aosr/47k21
Wie reduziert man ein Maximum Matching auf ein Max Flow Problem
? aosr/47k21/m/4otc

q aosr/26u2s
Was ist ein s-t-Cut?
? aosr/26u2s/m/6jcm

q aosr/1bl7g
Was ist das Max-Flow Min-Cut Theorem?
? aosr/1bl7g/m/33v3

q aosr/7uiuu
Wie baut man einen Residualgraph?
? aosr/7uiuu/m/1bv7

q aosr/2uhhj
Was ist ein Flow Augmenting Paths?
? aosr/2uhhj/m/5l29

q aosr/5nl0b
Was ist die Flow Optimality criteria?
? aosr/5nl0b/m/28fs

q aosr/54r5v
Was ist eine Blocking Flows und wie errechnet man ihn
? aosr/54r5v/m/3c5c

q aosr/3bl1d
Was ist die definition von einem Preflow?
? aosr/3bl1d/m/5t67

q aosr/qd6jt
Was ist der Excess bei einer Vertex vom Preflow?
? aosr/qd6jt/m/46qj

q aosr/pang5
Wie ist die Height function für Preflow definiert?
? aosr/pang5/m/5ji4

q aosr/2odhc
Wie sind eligible edges für Preflow definiert?
? aosr/2odhc/m/7i76

q aosr/272d5
Wie sind active Vertices für Preflow definiert?
? aosr/272d5/m/29bu

q aosr/1nrna
Wie lautet der allgemeine Preflow Push Algoritums und wie ist seine Laufzeit?
? aosr/1nrna/m/6dfk

$O (n^{2} \cdot m)$

q aosr/13l9v
Wie kann man den allgemeinen Preflow Push Algoritums verbessern?
? aosr/13l9v/m/7r1c
Mit dem Max-Height Algorithm

q aosr/1ei90
Wie lautet die potential function für den Max-Height Algorithm?
? aosr/1ei90/m/7hku

q aosr/2dea9
Warum ist der Max-Height Algorithm besser als die allgemeine Lösung?
? aosr/2dea9/m/50n3
Mit der potential function kann argumentiert werden, dass
-> Number of non saturating Pushes ist at most $O (n^{2} m)$
allgemein gilt
-> Number of saturating Pushes ist at most $O (2 nm) \leq O (n^{3})$
und die active und maximum height kann mit cleveren datenstrukturen auch immer schnell gefunden werden.
So ist die Laufzeit $O (n^{2} m)$

q aosr/6ckn3
Welche Algorithm gibt es um ein Maximum Matching zu berrechen? (Non Bipatiter Graph)
? aosr/6ckn3/m/21q9
Reduktion Maximum Matching auf Max-Fluss Problem
geht nicht (nur für Bipartite)
-> Satz von Berge nutzen
Non-Bipartie Matching via M-Alternating Paths

q aosr/2l9n7
Was ist symmetric Difference
? aosr/2l9n7/m/5bqs

q aosr/3fkeq
Was ist ein M-alternating Path
? aosr/3fkeq/m/4pa7

q aosr/337he
Was ist eine exposed Vertex in $M$
? aosr/337he/m/7rf6
Wenn keine Kante in $M$ zu oder von der Vertex geht.

q aosr/2b6ri
Was ist eine M-augmenting Path
? aosr/2b6ri/m/2ljc
Ein M-alternating Path bei dem beide Entpunkte exposed sind.

q aosr/3sn7a
Finde hier einen M-alternating Path

? aosr/3sn7a/m/21dr

q aosr/698ik
Wie berechnet man ein Matching in einem Bipatiter Graph mit M-augmenting Path und wie ist die Laufzeit
? aosr/698ik/m/58c1

O(n * m)

q aosr/1q3jm
Wie berechnet man ein Matching in einem nicht Bipatiter Graph mit M-augmenting Path und wie ist die Laufzeit
? aosr/1q3jm/m/2rbp

Create Neighbor Graph
Finde einen Weg von einer exposten Vertex zu einem exposetem neigbor

Non-Bipartie Matching via M-Alternating Paths
Es kann Graph Flower geben
Laufzeit