术语

A Bipartite-Graph (二分图) is a undirected-graph whose all points can be divided into two sets: $L$-Set and $R$-Set, all edges $a-b$ such that one of its endpoint belongs to $L$ and the another belongs to $R$;
+ For any $a\in L,b\in R$, it always has $a\ne b$; (for the definition, all points divided into two kinds.

--

A Match (匹配) is a set of edges $\{(l1,r1),(l2,r2),...\}$ such that $li\ne lj$ and $ri\ne rj$.

Given a match $\{(l1,r1),...\}$, a point $a$ is called Matched-Point (匹配点) if $a=li$ or $a=rj$; otherwise, it is called Unmatched-Point (非匹配点);

--

A Point-Coverage (点覆盖) $S$ is a set of points which involves all edges; (i.e., for any edge $a1-a2$, at least one point $ai\in S$)

The Minimum Point Coverage (最小点覆盖) is a Point-Coverage with the minimal $|S|$;
__. (it usually occurs in the context of Bipartite-Graph)

--

A Independent-Set (独立集) $S$ is a set of points such that $(a-b)\notin E,\forall a,b\in S$.

The Maximum Independent Set (最大独立集) is a Independent-Set with the maximal $|S|$;

二分图

Given a Bipartite-Graph $(L,R,E)$ where $E$ is undirected, in the algorithm, it would be stored in the form $(L,R,E1)$ where a undirected-edge $\forall (a-b)\in E$ (let $a\in L$, if not swap(a,b)) corresponding to a directed-edge $(a\to b)\in E1$; we call such a graph be Standard-Bipartite-Graph;
+ An edge $a\to b$ in Standard-Bipartite-Graph, corresponds to an Undirected-Edge $(a-b)$ in the normal Bipartite-Graph; (note that, the Bipartite-Graph is always Undirected (even although for the Standard-Bipartite-Graph), it is just the storage-form in computer which seems like a directed-graph, but in essence, it is undirected.
+ An usual (special) technique for transforming a Bipartite-Graph to a Standard-Bipartite-Graph
. Given you a Bipartite, you don’t need to using Flag-Coloring to transform the Bipartite to be Standard; If the graph is a Grid, and all edges are between two cells; a usual method is to dividing all cells into $L,R$-Sets in the below way:

0 1 0 1 0
1 0 1 0
0 1 0
1 0
0

if( (x + y) & 1){ belongs to one-set}
else{ belongs to anothe-set}

. For instance, if all edges are $a-b$ where let $a=(x,y)$ then $b$ must be the endpoint in the direction $(1,0)(-1,0)(0,1)(0,-1)$; the endpoints of such edges are located in two-sets in the coloring-strategy above;
. Or if the direction is $(2,1)(1,2)(-2,1)(-1,2)(2,-1)(1,-2)(-2,-1)(-1,-2)$, it also satisfies.

旧解释

Bipartite-Graph is a undirected graph with certain properties (not two graphs).

Satisfying:

• All points can be marked into two flags (let’s call flag $A,B$), for any edge $(a,b)$, their flags must be distinct.
  (e.g., 1-2-3-4-1 it can be marked $13:A,24:B$ or $13:B,24:A$. but 1-2-3-1 is not a Bipartite-Graph)

Visually, you can put all points that are marked $A$ into a Set-A, and the same process for $B$, then the Graph is absolutely same to the Original-Graph (we just change its appearance)
A:( ...) B: ( ...), then there are no edge within $A$ or $B$, alternatively, all edges of $G$ are the form of connecting one point of $A$ to one point of $B$.
This form is not unique (e.g., for a isolated point, it can belongs to $A$ or $B$)

There are some kinds of Sub-Graphs in a undirected graph:

• A isolated point. (it can marked arbitrarily, so it is a Bipartite)
• A chain 1-2-3-4-5. (it is also a Bipartite)
• A loop 1-2-3-...-1
  • With even number of points. 1-2-3-4-1 (it is OK)
  • With odd number of points. 1-2-3-1 (it is NOT)

So, $p=(GisBipartite),q=(noodd\_loopinG)$, then we have $p\to q$, moreover, $\neg q\to \neg p$

This is just a property (the algorithm for checking whether a graph is a Bipartite, will not use this property) , and we don’t know whether $q\to p$ is true.

染色法判定二分图

Given a undirected and unweighted graph, check whether it is a Bipartite-Graph.

The algorithm is based on the Flag-Marking principle as mentioned above.

There are some lemmas that are used in the algorithm:

• Due to $G$ maybe not connected, suppose that $G$ has several connected Sub-Graphs $G1,G2,G3$.
  G is Bipartite $\leftrightarrow$ G1, G2, G3 are both Bipartite
• For a connected graph which is a Bipartite, it has two marking schemes (e.g. (abc): A, (de): B or (abc): A, (de): B.

According to these lemmas, we use $Flag[]$ (-1 is not visited by DFS, 0 is one flag, 1 is another flag) to denote the flag of every point, use DFS to iterate every point in a connected Graph.

void Dfs( int _cur, int _fa, int _flag){
    Flag[ _cur] = _flag;
    for( int nex, e = G.Head[ _cur]; ~e; e = G.Next[ e]){
        nex = G.Vertex[ e];
        if( Flag[ nex] == -1){
            Dfs( nex, _cur, _flag ^ 1);
        }
        if( Flag[ nex] == _flag){
            Succ = false;
            break;
        }
    }
}

int main(){
	Succ = true;
    memset( Flag, -1, sizeof( Flag));
    for( int i = 0; i < n; ++i){
        if( Flag[ i] == -1){
            Dfs( i, -1, 0);
        }
    }
}

经验总结

+ $G$ must be a Undirected-Graph; (i.e., any edge $a\to b$ must has a corresponding edge $b\to a$)
__. for any edge (whatever it is directed or not) $a-b$, it always shows that $a,b$ must be in different set (i.e., the color of them are distinct); but the Algorithm requires that the edge must be Undirected (due to the store for graph of Linked-List, i.e., any edge $a\to b$ must has a corresponding edge $b\to a$);
__. if not, e.g., $G=(a\to b)$; the function $dfs(a)$ would always force the color of $a$ by $0$ (cuz the color solution of a Bipartite has two choices, i.e., swap the points in two sets would still be a Bipartite); so, $dfs(b)$ would force $color[b]=0$, and $dfs(a)$ would also force $color[a]=0$ which causes a contradiction.

+ Dfs( 0, -1, 0) is Wrong, because $G$ maybe not connected.
so, you just iterate its one Sub-Connected-Graph. But, we need iterate its all Sub-Connected-Graph.

匈牙利算法计算最大匹配

Given a unweighted Bipartite-Graph $L,R,E$, means that all points divide into two sets $L,R$, and all edges which are connecting $L,R$ are denoted by $E$, e.g., a edge $(a,b)$ denotes a undirected edge between a point $a\in L$ and $b\in R$

A Match is a set of disjoint edges, that is $\{(l_1,r_1),(l_2,r_2),...\}$ satisfying $l_i\ne l_j,and,r_i\ne r_j$, it is somewhat like a bijection (every point whatever within $L$ or $R$, either being non-matched (no edge associates it) or it has just one match (only one edge associates it) )

A Maximum-Match is a Match with the greatest cardinality.

Due to $|aMatch|\le min(|L|,|R|)$, and given a Match, for any point of $L$, it has at most one edge in the Match. We iterate on $L$

Suppose $L=[l_1,l_2,l_3,...,l_m]$, we stipulate that $L_i$ be a prefix of $L$ (e.g., $L_1=[l_1],L_2=[l_1,l_2]$), and $G_i$ be a Bipartite-Graph consists of points $L_i,R$ and edges connecting $L_i$ and $R$, and $M(G_i)$ denotes all its Maximum-Matches of $G_i$, $|M(G_i)|$ is the size of any one Maximum-Match (the number of edges in a Maximum-Match).
(notice that, $M(G_m)$ is not unique, but their size are the same)

Our goal is to get $|M(G_m)|$.

The standard approach is Greedy-Algorithm (it somewhat likes DP) ,that is, we get $|M(G_1)|$, and then used to updated the $|M(G_2)|$, until to get the final goal $|M(G_m)|$.

• $|M(G_1)|$ is available.
• If we got $|M(G_i)|$, then $|M(G_{i+1})|$ either equals to it or one more than it.
  The former case means whichever the graph of $M(G_i)$ is, and whatever the edge $(l_{i+1},R)$ you choose, they will always contradicts each other.

  The graph is (l1, r1) (l1, r2) (l2, r1) (l2, r2) (l3, r1) (l3, r2)
  
  |M( G_2)| is `2`, M( G_2) is either `l1-r1, l2-r2` or `l1-r2, l2-r1`.
  |M( G_3)| is also `2`, whatever the M( G_2) is (two possibles) and whatever the (l3,R) is (tow possibles), the combination of them is always contradictory.
  ... so, M( G_3) has 6 cases: M( G_2) or `l1-r1, l3-r2` or `l1-r2, r3-r1` or `l2-r1, l3-r2` or `l2-r2, l3-r1`
  

  While the latter case means that, there exists a edge $(l_{i+1},R)$ and a Match (set of edges, because $M(G_i)$ has multiple specific Match) of $M(G_i)$, the combination of them is not contradictory.

  The graph is (l1, r1) (l1, r2) (l2, r1) (l2, r2)
  
  |M( G_1)| is `1`, M( G_1) is either `l1-r1` or `l1-r2`.
  |M( G_1)| is `2`, if we choose `M( G_1) is `l1-r1 and (l2,r2)` or `M( G_1) is `l1-r2` and (l2,r1)`.
  

pseudocode

for( g : M( G_i)){
	for( e : E( l_i+1, R)){
		if( e not contradicts g){
			|M( G_i+1)| = |M( G_i)| + 1;
			return;
		}
	}
}

//> otherwise
|M( G_i+1)| = |M( G_i)|;

But in practice, to storing $M(G_i)$ is infeasible. We should analysis further. The thought is that can we replace for( g : M( G_i)) by just a $g$, that is, we use one Match instead of iterating all Matches, to get the same effect.

Supposing now we got $M(G_i)$ and need to calculate $M(G_{i+1})$

l1    r1
l2    r2
l3    r3
.     .
.     .
li    ri
li+1  ri+1
.     .
.     .

For a Match $m$ in $M(G_i)$, the total points under consideration is $\{l_1,...,l_i,\}\cup R$, a point is called free if it is not within $m$ (i.e., no edge in $m$ connects it), otherwise a point is called matched.

A Semi-Augmented-Path of $m$ is a path of the form $a_s,b,a,b,....a,b,a_e$ ($a$ has two choices $lorr$ and then $b$ is $rorl$ respectively), satisfying every adjacent pair $(a,b)$ is a edge of $m$, $a_e$ is free and all $a$ are pairwise distinct. (if the length is greater than $1$, $a_s$ is matched)

It’s meaning is that, if we use the edge $b_i,a_i$ to replace this preceding $a_{i-1},b_i$, then we have get a distinct Match which has the same cardinality with $m$.
In the other words, the symmetric difference of $m$ (a set of edges) and a S-A-Path (set of all adjacent edge in the path) means a new Match. In the new-Match, $a_s$ becomes free and $a_e$ becomes matched.

It also called $a_s$ has a Semi-Augmented-Path $a_s-...$.

• Two matches in $M(G_i)$ are distinct, if their point-set are distinct.
• Two distinct matches in $M(G_i)$ can be transformed to each other by a series of Semi-Augmented-Path .
• A matched point maybe not exists a Semi-Augmented-Path or multiple.
• Usually, $a_s$ belongs to $R$; and specially if $a_s$ is free, then $(a_s)$ is also a Semi-A-Path

Match: (l1-r1, l2-r2) and (l1-r2, l2-r1) are same (the point-set are same)

For a Graph (l1-r1, l1-r2, l2-r2, l2-l3), there are 3 matches in M(G): 
+ m1: (l1-r1, l2-r2)
+ m2: (l1-r1, l2-r3)
+ m3: (l1-r2, l2-r3)

For `m1` (only `r3` is free):
+ there is a `Semi-Augmented-Path` (r2-l2-r3), this path means the Match `m2` (if you use `l2-r3` to replace `r2-l2`)
+ there is a `Semi-Augmented-Path` (r1-l1-r2-l2-r3), this path means the Match `m3` (if you use `l1-r2` to replace `r1-l1`, and `l2-r3` replace `r2-l2`)

Property-1:
For a $M(g)$, a Match $m$ of $M(G)$, and its points set is $\{a,b,c....\}$, and another Match $n$ of $M(G)$ and its points set is not contains $a$. Then suppose the set of Transform-S-A-Path is $p1,p2,p3$ (i.e., if $m$ is operated by these path, it will becomes $n$), then, these must exists a $pi$ which starts at $a$.

Property-11:
For a Semi-A-Path $a_1-b_1-a_2-b_2-a_3-b_3-a_4$ in $m$ (every $a_i-b_i$ is contained in $m$ will be replaced by $b_i-a_{i+1}$ , $a_4$ is free, once $a_i$ is fixed, then $b_i$ is unique, so $b_i$ is totally depended on $a_i$)
$a_2-b_2-a_3-b_3-a4$, and $a_3-b_3-a_4$ and $a_4$ are also Semi-A-Path.

A Augmented-Path of $m$ is a path of the form $b_s,(a_1,b,...,a,b,a_e)$ where the tail $(a_1,b,..,a_e)$ is a Semi-Augmented-Path , $b_s$ belongs to $L$, and $b_s$ is a new-point.
A new-point is different from total-point, for example, for a Sub-Graph $G(3)$ (l1, l2, l3, R), a Match $m$ of its Maximum-Matching $M(G(3))$ (e.g., $(l1,r1),(l2,r2)$)
Then, $l1,l2,l3,R$ is total-points of $m$, $l1,l2$ is matched, $l3,r3,r4,r5,...$ is free. A new point is a point not $l1,l2,l3$ (e.g., $l4$)

It means that $m$ transformed to $m1$ by $(a1,b,...,a_e)$ ($a1$ is matched in $m$ and free in $m1$), and then the edge $b_s,a1$ is not contradicts with $m1$ (because $a1$ is free in $m1$, $b_s$ is new-point)

Graph: (l1-r1, l1-r2, l2-r2, l2-r3, l3-r1, l3-r4)

|M(G_2)| has  Matches: (l1-r1, l2-r2), (l1-r1, l2-r3), (l1-r2, l2-r3)
Let m be a Match of M(G_2) is (l1-r1, l2-r2), the Augmented-Path of `l3`:
+ `l3-r4` is a Augmented-Path
+ `l3-r1-l1-r2-l2-r3` is also, it means `m` transforms to (l1-r2, l2-r3), then `r1` becomes free, so `l3-r1` is not contradictory to the new Match.

Property-2:
$|M(G_{i+1})|=|M(G_i)|+1\iff l_{i+1}$ exists a Augmented-Path in any Match of $M(G_i)$.
$|M(G_{i+1})|=|M(G_i)|\iff l_{i+1}$ not exists a Augmented-Path in any Match of $M(G_i)$.

$p:|M(G_{i+1})|=|M(G_i)|+1$, $q:letmbeanyMatchofM(G_i),then{l}_{i+1}hasaAugmented-Pathinm$
$p\to q$: according to the definition of $p$, there exist a Match $m1$ of $M(G_i)$ and a edge $(l_{i+1},r_k)$ ($r_k$ is free)
Let $m$ be any Match of $M(G_i)$, if $r_k$ is free in $m$, then $l_{i+1},r_k$ is Augmented-Path; otherwise, there must exists Semi-A-Path of $r_k$ in $m$ (according to Property-1), to transform $m$ to $m2$ ($m2$ maybe equals to $m1$, also may not) where $r_k$ is free, then $l_{i+1}-$Semi-A-Path of $r_k$ forms a A-Path in $m$.
$q\to p$: if the Augmented-Path is the form $l_{i+1},r_k$, then $r_k$ is free, so $m$ is not contradictory to edge $l_{i+1},r_k$, so $|M(G_{i+1})|=xx+1$
otherwise, $l_{i+1},(r_k,l,...,r_e)$, then $m$ can be transformed to $m1$ where $r_k$ is free according to Semi-A-Path $(r_k,...,r_e)$.

Same proof for $|M(G_{i+1})|=|M(G_i)|\iff l_{i+1}$ not exists a Augmented-Path in any Match of $M(G_i)$.

So now, we need not to store all Matched of $M(G_i)$, but only one Match of it is enough.

Pseudocode

//* points in `L` is [0, m-1], [0, n-1] of `R`.
`M` be a Match.
for( int i = 0; i < m; ++i){
	if( `i` has a Augmented-Path in `M`){
		modify `M` according to the Augmented-Path
	}
}
answer is in `M`

More specifically, we use $Match[R]$ to present $M$ ($Match[r]=l$ means there has a edge $(l,r)$ in $M$)
when i has a A-Path:

• either the form is $i-r$, then $r$ is free, r has a Semi-A-Path
• or the form if $i-(r_1-l_1-r2-...r_c-l_k-r_k-l_e-r_e)$, then $r_1$ is matched, so we need find a Semi-A-Path of $r_1$ in $M$, it means use l1-r2 to replace r1-l1, … use le-re to replace rk-le, now r1 is free so i-r1 can be added to the Match.
  We use DFS( r1) to find whether $r_1$ has a Semi-A-Path, once we arrive at r_k (DFS(rk)) which has already matched to $l_e$, we iterate all adjacent points $r$ of $l_e$, once $r$ has Semi-A-Path, then modify $Match[r]=l_e$. the modifying $Match[r_k]=l_k$ will be happened in $DFS(r_c)$.

set< int> S; //< all `r` points in the Semi-A-Path, because we need to make sure all `r` are distinct in the path.
bool Has_semiAugmentedPath( int _cur){
	if( Match[ _cur] == -1){ //< free
		return true;
	}
	S.insert( _cur);
	int l = Match[ _cur]; //< (_cur,l) has also matched
	for( r : Adjacent-Points( l)){
		if( (r not in S) && Has_semiAugmentedPath( r)){
            Match[ r] = l; //< (l-r) replace (_cur,l), it is the form (_cur-l-r) in the whole Semi-A-Path.
            return true;
        }
	}
	S.remove( _cur);
	return false;
}

for( int i = 0; i < m; ++i){
	for( j : Adjacency-Points( i)){
		if( Has_semiAugmentedPath( Match[ j])){
            Match[ j] = i;
            break;
        }
	}
}

But DFS is an Endless-Loop, (e.g., $r1-l1-r2-l2-r1$)
We need to prove, for a Match, if $r_i$ has no Semi-A-Path in one DFS-Prefix-Tree, $r_i$ is also no Semi-A-Path in all DFS-Prefix-Tree.
e.g., Given a Match, when a DFS-Path is $r1-l1-r2-l2-r3-l3$, and $l3$ has adjacent-points $r1,r2,r3$, due to the prefix-path contains $r1,r2,r3$, so $l3,r3$ has no Semi-A-Path under the prefix $r1-l1-r2$ (we call it that $l3,r3$ has no S-A-Path under $r1,r2$).

• Now DFS failed at (r3), we have $r3$ has no S-A-Path under $r1,r2$ (because $l3$ can only choose $r1,r2$ which has already occurred) ($r3$ may have S-A-Path if the prefix not contains $r1,r2$, e.g., $r3-l3-l1-r4$ where $r4$ is free. it shows that DFS process firstly choose $l1-r2$ edge not $l1-r4$.)

  A Match:
  l1---r2
  l2---r1
  other edges that are non in the Match is (l1-r1, l2-r2, l1-r3)
  
  r2-l1-r1-l2:  now because `l2` can only choose `r2` which has occurred in the prefix-path, so we have `l2,r1` has no S-A-Path under `r2`.
  but `l2,r1` may have S-A-Path if not under `r2`, e.g., `r1-l2-r2-l1-r3` is a valid S-A-Path.
  

• When DFS failed at (r2) (return back from (r3)), we have $r2,r3$ has no S-A-Path except $r1$ where the $r2$ is reasonable (because its prefix has $r1$), but why $r3$ is also the same as $r2$?
  for mentioned above, we know $r3$ has no S-A-Path under $r1,r2$, but why it becomes under $r1$??
  Proof: if $r3$ has S-A-Path under $r1$, i.e., $(r1)-r3-l3$, now $l3$ can only choose $r2$, but now, we know $r2$ has no SA-Path under $r1$, so this is not feasible.
• When DFS failed at (r1) (return back from (r2)), we have $r1,r2,r3$ has no S-A-Path.
  The proof is similar as above.

We can set a $Vis[R]$ to denote whether a point of $R$ had been visited by DFS. if we found a point is visited, then it has no S-A-Path.
This bool-array is the most vital and sophisticated part of the algorithm.

Given a Match of $M(G_i)$, we need to check whether $l_{i+1}$ has a A-Path, assume that there are edges $(l_{i+1},r1/r5)$

• Find whether $r1$ has a S-A-Path, if DFS(r1) has visited $r2,r3,r4$, then when $DFS(r1)$ has ended, we have $r1,r2,r3,r4$ has no S-A-Path (corresponds to their $Vis[]$ is True)
• Find whether $r5$ has a S-A-Path, if DFS(r5) find a Path that is $r5,r6,r7$ (but DFS has visited some other points that are failed, e.g., $r8,r9$)
  now, we have $r8,r9$ has no S-A-Path under $r5,...$ (also, their $Vis[]$ is true), but if the next step (check whether $l_{i+2}$ has a A-Path), the $Vis[r8,r9]$ should be false. (more detailed, $Vis[r8]=true$ means $r8$ has no S-A-Path under $r5,...$, when we at the next $DFS(r10)$ where $l_{i+2}\to r10$, when $r10$ visits $r8$, it would thought that $r8$ has no S-A-Path (due to $Vis[r8]=true$), but $Vis[r8]=true$ not meaning its has no path under $r10,..$, it just means no S-A-Path under $r5,...$, so you should reset $Vis[r8]=false$ when you go to the next $l_{i+2}$)
  Also, $Vis[r5,r6,r7]$ also should be false (as they already found a S-A-Path)
  But these points are both $Vis[]=true$ (means no S-A-Path) at present, so we need to reset them to $false$

So, if current-loop has a A-Path, then we need reset all $Vis$ to $false$; otherwise, $Vis$ can be inherited.

Lets proceed to discuss reset $Vis[r8]=false$ as mentioned above.
Find that whether there is a A-Path of $l_i$, if there has edges $l_i\to r5$ $l_i\to r9$
... when we are finding S-A-Path of $r5$, it involves $r5,r4,r3$, and failed then. that means $r5,r4,r3$ has no S-A-Path.
... then we will find whether a S-A-Path of $r9$, it involves (involve means that those points which are $Vis=false$ before the operation $DFS(r9)$, then becomes $Vis=true$ after the DFS) $r9,r8,r7,r6,r1$ where the S-A-Path is $r9,r8,r7$ , now the $Vis$ of them are both $true$. according to discussed above, they should reset to $false$.
But, the approach introduces above, will reset all $Vis[R]=false$ (including $r5,r4,r3$), because the Match-Graph has been modified once we found a S-A-Path.
We need to prove that, we could only modify $r9,r8,r7,r6,r1$, not necessary All R.
($r5,r4,r3$ must be matched, let $l1,l2,l3$ be the matched-points of them), the A-Path $l_i,r9,l4,r8,l5,r7$ (this path would modify the previous Match-Graph, we need to prove the modification will not cause that there would be a S-A-Path for $r5,r4,r3$ in the new Match-Graph)
+ any point $l,r$ in the A-Path, will not contains any point of $l1-r5,l2-r4,l3-r3$
+ any adjacent point of $l1,l2,l3$, will not involves ant $r$ of the A-Path.
That is, the sub-graph of $r5,r4,r3,l1,l2,l3$ (and all edges that connects $l1,l2,l3$) and the sub-graph of $l_i,r9,l4,..$ (the A-Path), are totally separated. So, the modification on one sub-graph, will not effect the another sub-graph.

So, we just need to reset $r9,...$ without $r3,..$, we could use a Queue to store all visited R points (i.e., any points $Vis=true$ will be store in the queue)

例题

+ link

经验总结

We call a bipartite-graph is Full-Matched that the maximal-match equals $min(|L|,|R|)$;
We call a bipartite is connected that there exists a path $l-r1-l1-r2-...-r\forall l,r$
As a result, a bipartite is $connected\to FullMatched$ (converse is not correct)
Proof
Now, we are at $li$, and there has matched $x$; if $x<|R|$, then there must exists a unmatched point $r$; subsequently, $li$ has a A-Path cuz there is a path $li-...-r$.

If $li$ has no A-Path (not be matched), then it will not be matched forever. That is, after the whole algorithm, $li$ is not be matched.
Proof:
When we are finding A-Path for any $Lj$ where $j>i$, essentially finding a S-A-Path $r-l-r-l-...-r$ where every edge $r-l$ is be matched. Because $li$ not be matched, it will never occurs in any S-A-Path. Therefore, $li$ would be matched forever.

点覆盖

+ A Point-Coverage $S$, its complementary-set $V-S$ is always be a Independent-Set;
. If not, then there is a contradiction: $\exists (a-b)\in E,a\in (V-S)\wedge b\in (V-S)\to \exists (a-b)\in E,a\notin S\wedge b\notin S\to S\text{ is not a Point-Coverage}$
. As a consequence, the complementary-set $V-S$ of a Minimum-Point-Coverage $S$, is always be a Maximum-Independent-Set;

在二分图中

let $m$ be the maximal-match, cuz these $m$ edges are disjoint, $|S|$ must $\ge m$.
Conclusion: $|S|=m$ where $S$ is the Minimum-Point-Coverage; and the process for constructing $S$ showed below:

ASSUME( `(l1-r1),...,(ln-rn)` are the Maximum-Matches); //< i.e., `l1,...,ln; r1,...,rn` are all Matched-Points;
ASSUME( `ll1,...,llm; rr1,...,rrk` are all Unmatched-Points);
vector ans := the Minimum-Point-Coverage;
set lef := see below;
for( l : {ll1,...,llm}){
	for( r : the adjacent-points of `l`){
		ASSERT( `r` is a Matched-Point);
		ans.push_back( r);
		lef.insert( $(the corresponding Left-Point of `r` in the Maximum-Matchs));
	}
}
for( l : {l1,...,ln}){
	if( l \in lef){
		continue;
	}
	ans.push_back( l);
}
ASSERT( ans.size() == n);

例题

+ link

独立集

+ A Independent-Set $S$, its complementary-set $V-S$ is always be a Point-Coverage;
. If not, then there is a contradiction: $\exists (a-b)\in E,a\notin (V-S)\wedge b\notin (V-S)\to \exists (a-b)\in E,a\in S\wedge b\in S\to S\text{ is not a Independent-Set}$
. As a consequence, the complementary-set $V-S$ of a Maximum-Independent-Set $S$, is always be a Minimum-Point-Coverage;
+ $\forall a\in S$, $a$ may have a adjacent-edge $(a-b)$ ($b$ must $\notin S$);
. $\forall a,b\in S$, although there is no edge (not path) between them, they maybe accessible by a path, e.g., a path $a-c-b$ where $c\notin S$ is possible;

二分图中

Let the Bipartite $(L,R,E)$, $m$ be its maximal-match; for the theorem of Minimum-Point-Coverage, we have $m=|S|$ where $S$ is the Minimum-Point-Coverage; therefore, we have $|L|+|R|-m$ is the size of Maximum-Independent-Set; (that is, once you got the Minimum-Point-Coverage, its complementary-set is the answer)

例题

+ link

延伸阅读

+ DAG的(最小路径点覆盖) link