minimum point coverage
Similarly transformed into the graph G=(V,E), the problem is transformed into:
Select as few points as possible in the graph G so that at least one endpoint of each edge in the graph is selected.
This problem is called the minimum point covering problem in bipartite graph problems. That is, use the fewest points to cover all edges.
Conclusion: byKönig's theorem可知The number of points covered by the minimum point = the maximum matching of the bipartite graph
maximum independent set
Still transformed into the graph G=(V,E), the problem is transformed into:
Select as many points as possible in graph G so that there are no edges between any two points.
This problem is called the maximum independent set problem in bipartite graph problems.
in conclusion:The number of points in the maximum independent set = the total number of points – the maximum matching of the bipartite graph
Prove:
Assume that the number of points in the maximum independent set is |U|, the number of matches in the maximum matching of the bipartite graph is |M|, and the set of all vertices in the maximum matching is EM
First prove that |U|≤|V|-|M|
The two endpoints of any edge in M are connected. All edges in M must have an endpoint that is not in the |U| set, so |M|≤|V|-|U|
Prove again that |U|≥|V|-|M|
First of all, we know that there must be |U|≥|V|-|EM|, that is, after deleting the maximum matching point, the remaining points must not be connected.
Next we consider whether we can put an endpoint in the M set into U:
Assume (x, y) belongs to M, there are (a, x), (b, y), and a, b are both in U, then two situations will occur: If (a, b) is connected, there is a more A large matching and contradiction exists. If (a, b) is not connected, a->x->y->b has a new augmenting path, so there is a larger matching and contradiction.
Therefore, at most one point among the two points a and b belongs to U, then we can always choose one point from x or y and put it into the set U
So |U|≥|V|-|EM|+|M|=|V|-|M|
To sum up, there are|U|=|V|-|M|