26.3 Maximum bipartite matching

26.3-1

Run the Ford-Fulkerson algorithm on the flow network in Figure 26.8 \(c\) and show the residual network after each flow augmentation. Number the vertices in \(L\) top to bottom from \(1\) to \(5\) and in \(R\) top to bottom from \(6\) to \(9\). For each iteration, pick the augmenting path that is lexicographically smallest.

First, we pick an augmenting path that passes through vertices 1 and 6. Then, we pick the path going through 2 and 8. Then, we pick the path going through 3 and 7. Then, the resulting residual graph has no path from \(s\) to \(t\). So, we know that we are done, and that we are pairing up vertices \((1, 6)\), \((2, 8)\), and \((3, 7)\). This number of unit augmenting paths agrees with the value of the cut where you cut the edges \((s, 3)\), \((6, t)\), and \((7, t)\).

26.3-2

Prove Theorem 26.10.

We proceed by induction on the number of iterations of the while loop of Ford-Fulkerson. After the first iteration, since \(c\) only takes on integer values and \((u, v).f\) is set to \(0\), \(c_f\) only takes on integer values. Thus, lines 7 and 8 of Ford-Fulkerson only assign integer values to \((u, v).f\). Assume that \((u, v).f \in \mathbb Z\) for all \((u, v)\) after the \(n\)th iteration. On the \((n + 1)\)th iteration \(c_f(p)\) is set to the minimum of \(c_f(u, v)\) which is an integer by the induction hypothesis. Lines 7 and 8 compute \((u, v).f\) or \((v, u).f\). Either way, these the the sum or difference of integers by assumption, so after the \((n + 1)\)th iteration we have that \((u, v).f\) is an integer for all \((u, v) \in E\). Since the value of the flow is a sum of flows of edges, we must have \(|f| \in \mathbb Z\) as well.

26.3-3

Let \(G = (V, E)\) be a bipartite graph with vertex partition \(V = L \cup R\), and let \(G'\) be its corresponding flow network. Give a good upper bound on the length of any augmenting path found in \(G'\) during the execution of \(\text{FORD-FULKERSON}\).

(Removed)

26.3-4 \(\star\)

A perfect matching is a matching in which every vertex is matched. Let \(G = (V, E)\) be an undirected bipartite graph with vertex partition \(V = L \cup R\), where \(|L| = |R|\). For any \(X \subseteq V\), define the neighborhood of \(X\) as

\[N(X) = \\{y \in V: (x, y) \in E \text{ for some } x \in X\\},\]

that is, the set of vertices adjacent to some member of \(X\). Prove Hall's theorem: there exists a perfect matching in \(G\) if and only if \(|A| \le |N(A)|\) for every subset \(A \subseteq L\).

First suppose there exists a perfect matching in \(G\). Then for any subset \(A \subseteq L\), each vertex of \(A\) is matched with a neighbor in \(R\), and since it is a matching, no two such vertices are matched with the same vertex in \(R\). Thus, there are at least \(|A|\) vertices in the neighborhood of \(A\).

Now suppose that \(|A| \le |N(A)|\) for all \(A \subseteq L\). Run Ford-Fulkerson on the corresponding flow network. The flow is increased by \(1\) each time an augmenting path is found, so it will suffice to show that this happens \(|L|\) times. Suppose the while loop has run fewer than \(L\) times, but there is no augmenting path. Then fewer than \(L\) edges from \(L\) to \(R\) have flow \(1\).

Let \(v_1 \in L\) be such that no edge from \(v_1\) to a vertex in \(R\) has nonzero flow. By assumption, \(v_1\) has at least one neighbor \(v_1' \in R\). If any of \(v_1\)'s neighbors are connected to \(t\) in \(G_f\) then there is a path, so assume this is not the case. Thus, there must be some edge \((v_2, v_1)\) with flow \(1\). By assumption, \(N(\\{v_1, v_2\\}) \ge 2\), so there must exist \(v_2' \ne v_1'\) such that \(v_2'\in N(\\{v_1, v_2 \\})\). If \((v_2', t)\) is an edge in the residual network we're done since \(v_2'\) must be a neighbor of \(v_2\), so \(s\), \(v_1\), \(v_1'\), \(v_2\), \(v_2'\), and \(t\) is a path in \(G_f\). Otherwise \(v_2'\) must have a neighbor \(v_3 \in L\) such that \((v_3, v_2')\) is in \(G_f\). Specifically, \(v_3 \ne v_1\) since \((v_3, v_2')\) has flow \(1\), and \(v_3 \ne v_2\) since \((v_2, v_1')\) has flow \(1\), so no more flow can leave \(v_2\) without violating conservation of flow. Again by our hypothesis, \(N(\\{v_1, v_2, v_3\\}) \ge 3\), so there is another neighbor \(v_3' \in R\).

Continuing in this fashion, we keep building up the neighborhood \(v_i'\), expanding each time we find that \((v_i', t)\) is not an edge in \(G_f\). This cannot happen \(L\) times, since we have run the Ford-Fulkerson while-loop fewer than \(|L|\) times, so there still exist edges into \(t\) in \(G_f\). Thus, the process must stop at some vertex \(v_k'\), and we obtain an augmenting path

contradicting our assumption that there was no such path. Therefore the while loop runs at least \(|L|\) times. By Corollary 26.3 the flow strictly increases each time by \(f_p\). By Theorem 26.10 \(f_p\) is an integer. In particular, it is equal to \(1\). This implies that \(|f| \ge |L|\). It is clear that \(|f| \le |L|\), so we must have \(|f| = |L|\). By Corollary 26.11 this is the cardinality of a maximum matching. Since \(|L| = |R|\), any maximum matching must be a perfect matching.

26.3-5 \(\star\)

We say that a bipartite graph \(G = (V, E)\), where \(V = L \cup R\), is \(d\)-regular if every vertex \(v \in V\) has degree exactly \(d\). Every \(d\)-regular bipartite graph has \(|L| = |R|\). Prove that every \(d\)-regular bipartite graph has a matching of cardinality \(|L|\) by arguing that a minimum cut of the corresponding flow network has capacity \(|L|\).

We convert the bipartite graph into a flow problem by making a new vertex for the source which has an edge of unit capacity going to each of the vertices in \(L\), and a new vertex for the sink that has an edge from each of the vertices in \(R\), each with unit capacity. We want to show that the number of edge between the two parts of the cut is at least \(L\), this would get us by the max-flow-min-cut theorem that there is a flow of value at least \(|L|\). The, we can apply the integrality theorem that all of the flow values are integers, meaning that we are selecting \(|L|\) disjoint edges between \(L\) and \(R\).

To see that every cut must have capacity at lest \(|L|\), let \(S_1\) be the side of the cut containing the source and let \(S_2\) be the side of the cut containing the sink. Then, look at \(L \cap S_1\). The source has an edge going to each of \(L \cap (S_1)^c\), and there is an edge from \(R \cap S_1\) to the sink that will be cut. This means that we need that there are at least \(|L \cap S_1| - |R \cap S_1|\) many edges going from \(L \cap S_1\) to \(R \cap S_2\). If we look at the set of all neighbors of \(L \cap S_1\), we get that there must be at least the same number of neighbors in \(R\), because otherwise we could sum up the degrees going from \(L \cap S_1\) to \(R\) on both sides, and get that some of the vertices in \(R\) would need to have a degree higher than \(d\). This means that the number of neighbors of \(L \cap S_1\) is at least \(L \cap S_1\), but we have that they are in \(S_1\), but there are only \(|R \cap S_1|\) of those, so, we have that the size of the set of neighbors of \(L \cap S_1\) that are in \(S_2\) is at least \(|L \cap S_1| - |R \cap S_1|\). Since each of these neighbors has an edge crossing the cut, we have that the total number of edges that the cut breaks is at least

Since each of these edges is unit valued, the value of the cut is at least \(|L|\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用