# 5 - Graph Matching 1 Flashcards

What is the augmenting path algorithm used for?

Finding a maximum cardinality matching in a bipartite graph

What is the Ford-Fulkerson algorithm used for?

Finding a maximum flow in a network

What is the Gale / Shapley algorithm used for?

Finding a stable matching in an instance of the stable marrige problem

What is the Floyd-Warshall algorithm used for?

Computing all-pairs shortest paths in a graph

What is a bipartite graph?

- A graph G=(V,E)
- where V is partitioned into a left hand side U and a right hand side W
- so that every edge in E joins a vertex in U to a vertex in W

What is a matching in a graph G?

- A matching in G is a subet M of E
- such that no two edges in M have a vertex in common

What is a maximum (cardinality) matching in G?

A matching that contains the largest number of edges

What is a perfect maximum cardinality matching?

- |M| = |V|/2
- i.e. if every vertex is incident to an edge in M

What is the naive approach to maximum matching problem?

- Try out all possible assignments
- n! possibilities

Given a matching M in a graph bipartite G, what is a matched vertex?

A vertex u is matched if {u,v} for some vertex v - in this case u and v are mates

Given a matching M in a graph bipartite G, what is an exposed vertex?

A vertex u is exposed if it is not matched

Given a matching M in a graph bipartite G, what is an alternating path?

An alternating path comprises edges in M and edges not in M alternatively

Given a matching M in a graph bipartite G, what is an augmenting path?

An augmenting path for M is an alternating path which starts and ends at exposed vertices