Matchings · Vertex Cover

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Let's give one more example. Consider the following graph:

To find a maximum matching in it, we will construct a network based on this graph.

Let's find the maximum flow in it.

This flow yields a maximum matching in the original graph: \[\{\{a_{1}, c_{1}\}, \ \{a_{2}, c_{2}\}\} \ .\] Let's construct the residual network for the given network and flow.

To get the minimum capacity cut, we take all vertices reachable from \(s\) in the residual network: \(S=\{s, a_{0}, c_{1}, a_{1}\}\). This indeed gives a cut of capacity two (in the original network the edges \((s, a_{2})\) and \((c_{1},t)\) are cut). To get the vertex cover from the cut, we take left side vertices not in the cut, and right side vertices that are in the cut: \(C=\{a_{2}, c_{1}\}\).