5 - Graph Matching 1

Question 1

What is the augmenting path algorithm used for?

Answer 1

Finding a maximum cardinality matching in a bipartite graph

Question 2

What is the Ford-Fulkerson algorithm used for?

Answer 2

Finding a maximum flow in a network

Question 3

What is the Gale / Shapley algorithm used for?

Answer 3

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

Question 4

What is the Floyd-Warshall algorithm used for?

Answer 4

Computing all-pairs shortest paths in a graph

Question 5

What is a bipartite graph?

Answer 5

• 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

Question 6

What is a matching in a graph G?

Answer 6

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

Question 7

What is a maximum (cardinality) matching in G?

Answer 7

A matching that contains the largest number of edges

Question 8

What is a perfect maximum cardinality matching?

Answer 8

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

Question 9

What is the naive approach to maximum matching problem?

Answer 9

• Try out all possible assignments
• n! possibilities

Question 10

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

Answer 10

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

Question 11

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

Answer 11

A vertex u is exposed if it is not matched

Question 12

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

Answer 12

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

Question 13

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

Answer 13

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