# 5 - Graph Matching 1 Flashcards

1
Q

What is the augmenting path algorithm used for?

A

Finding a maximum cardinality matching in a bipartite graph

2
Q

What is the Ford-Fulkerson algorithm used for?

A

Finding a maximum flow in a network

3
Q

What is the Gale / Shapley algorithm used for?

A

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

4
Q

What is the Floyd-Warshall algorithm used for?

A

Computing all-pairs shortest paths in a graph

5
Q

What is a bipartite graph?

A
• 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
6
Q

What is a matching in a graph G?

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

What is a maximum (cardinality) matching in G?

A

A matching that contains the largest number of edges

8
Q

What is a perfect maximum cardinality matching?

A
• |M| = |V|/2
• i.e. if every vertex is incident to an edge in M
9
Q

What is the naive approach to maximum matching problem?

A
• Try out all possible assignments
• n! possibilities
10
Q

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

A

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

11
Q

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

A

A vertex u is exposed if it is not matched

12
Q

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

A

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

13
Q

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

A

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