AA Flashcards Maximum Matching and Flows

Q 2a6va
Was ist der Satz von Berge
? 57nc

Q 41fui
Welche Algorithm gibt es um ein Maximum Matching in einem Bipatiter Graph zu berrechen?
? 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 47k21
Wie reduziert man ein Maximum Matching auf ein Max Flow Problem
? 4otc

Q 26u2s
Was ist ein s-t-Cut?
? 6jcm

Q 1bl7g
Was ist das Max-Flow Min-Cut Theorem?
? 33v3

Q 7uiuu
Wie baut man einen Residualgraph?
? 1bv7

Q 2uhhj
Was ist ein Flow Augmenting Paths?
? 5l29

Q 5nl0b
Was ist die Flow Optimality criteria?
? 28fs

Q 54r5v
Was ist eine Blocking Flows und wie errechnet man ihn
? 3c5c

Q 3bl1d
Was ist die definition von einem Preflow?
? 5t67

Q qd6jt
Was ist der Excess bei einer Vertex vom Preflow?
? 46qj

Q pang5
Wie ist die Height function für Preflow definiert?
? 5ji4

Q 2odhc
Wie sind eligible edges für Preflow definiert?
? 7i76

Q 272d5
Wie sind active Vertices für Preflow definiert?
? 29bu

Q 1nrna
Wie lautet der allgemeine Preflow Push Algoritums und wie ist seine Laufzeit?
? 6dfk

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

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

Q 1ei90
Wie lautet die potential function für den Max-Height Algorithm?
? 7hku

Q 2dea9
Warum ist der Max-Height Algorithm besser als die allgemeine Lösung?
? 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 6ckn3
Welche Algorithm gibt es um ein Maximum Matching zu berrechen? (Non Bipatiter Graph)
? 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 2l9n7
Was ist symmetric Difference
? 5bqs

Q 3fkeq
Was ist ein M-alternating Path
? 4pa7

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

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

Q 3sn7a
Finde hier einen M-alternating Path

? 21dr

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

O(n * m)

Q 1q3jm
Wie berechnet man ein Matching in einem nicht Bipatiter Graph mit M-augmenting Path und wie ist die Laufzeit
? 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