Exercise 3.

One way you might check to see whether a partial matching is maximal is to construct an alternating path. This is a sequence of adjacent edges, which alternate between edges in the matching and edges not in the matching (no edge can be used more than once). If an alternating path starts and stops with an edge not in the matching, then it is called an augmenting path.

  1. Find the largest possible alternating path for the partial matching of your friend's graph. Is it an augmenting path? How would this help you find a larger matching?

    A bipartite graph with ten vertices in two sets of five. Call the top vertices a, b, c, d, e and the bottom vertices 1, 2, 3, 4, 5. Then the graph has the following edges: a-1, a-3, b-1, b-2, c-1, c-2, c-4, d-5, e-4, and e-5. Of these, the edges a-1, b-2, c-4, and e-5 are highlighted bold.

  2. Find the largest possible alternating path for the partial matching below. Are there any augmenting paths? Is the partial matching the largest one that exists in the graph?

    A bipartite graph with 12 vertices in two sets of six. Call the top vertices a to f and the bottom vertices 1 to 6. Then the graph has the following edges: a-2, a-3, b-1, b-3, c-1, c-2, c-4, c-5, d-3, d-5, e-3, e-4, e-5, e-6, f-5 and f-6. Of these, the edges a-3, b-1, c-2, e-4, and f-5 are highlighted bold.
in-context