二分图最大匹配算法：匈牙利、KM

基础定义

匹配

• 匹配：给定一个无向图$G=<V,E>$，一个匹配是一个边的子集合$M?E$，且满足对所有顶点$v\in V$，$M$中至多有一条边与$v$关联。对匹配$M$中的每条边$e=(u,v)$，其两端点$u$和$v$称为被匹配M所匹配，而$u$和$v$都称为是M饱和的。
• 最大匹配：图G中含边数最多的匹配称为G的最大匹配
• 完美匹配：如果G中每个点都是M饱和的，则称M是G的完美匹配

二分图

• 二分图(二部图)：G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边<i,j>所关联的两个顶点i和j分别属于这两个不同的顶点集，则称图G为一个二分图。
  满足下面的无向图 G = < V , E > 有非空集合 X , Y : X ∪ Y = V , X ∩ Y = ? 且每条边 { v i , v j } ∈ E 都有 : v i ∈ X ∧ v j ∈ Y 或者 v i ∈ Y ∧ v j ∈ X 称为二分图 ( b i p a r t i t e   g r a p h ) 可以用 G = < X , E , Y > 表示二分图 \begin{array}{l} 满足下面的无向图G=<V,E>\\ 有非空集合X,Y:X\cup Y=V,X\cap Y=\varnothing\\ 且每条边\{v_i,v_j\}\in E 都有:\\ v_i\in X\wedge v_j\in Y或者v_i\in Y\wedge v_j\in X\\ 称为二分图(bipartite\ graph)\\ 可以用G=<X,E,Y>表示二分图 \end{array} 满足下面的无向图G=<V,E>有非空集合X,Y:X∪Y=V,X∩Y=?且每条边{ vi?,vj?}∈E都有:vi?∈X∧vj?∈Y或者vi?∈Y∧vj?∈X称为二分图(bipartite graph)可以用G=<X,E,Y>表示二分图?

• 图G是二分图$\iff $图G至少有两个顶点，而且G中所有回路的长度都是偶数

  证明：
  必要性
  $$\begin{array}{l}只有一个点不够二分，故至少有两个顶点。回路的边数和顶点数相同\\ 不失一般性，设一回路从X部出发，则下一顶点在Y部，\\ 回路上的顶点X、Y部交替，故X部点的数量与Y部点数量相同。\\ 顶点数是偶数，边的数量也是偶数\end{array}$$

  充分性
  任意取顶点 v , 取 V 1 = { v i ∣ v i 与 v 的距离为偶数 } , V 2 = V ? V 1 , 证明 V 1 , V 2 内部顶点间没有边 ( 反证法 ) 如果有边 { v i , v j } ∈ E v i , v j ∈ V 1 那么 v 到 v i , v j 距离都是偶数 , v → v i → v j → v 这个 回路的长度是奇数 , 和条件矛盾 , V 2 同理 所以 G 是个二分图 < V 1 , E , V 2 > \begin{array}{l} 任意取顶点v,取V_1=\{v_i|v_i与v的距离为偶数\},\\ V_2=V-V_1,证明V_1,V_2内部顶点间没有边(反证法)\\ 如果有边\{v_i,v_j\}\in E\quad v_i,v_j\in V_1\\ 那么v到v_i,v_j距离都是偶数,v\rightarrow v_i\rightarrow v_j \rightarrow v这个\\ 回路的长度是奇数,和条件矛盾,V_2同理\\ 所以G是个二分图<V_1,E,V_2> \end{array} 任意取顶点v,取V1?={ vi?∣vi?与v的距离为偶数},V2?=V?V1?,证明V1?,V2?内部顶点间没有边(反证法)如果有边{ vi?,vj?}∈Evi?,vj?∈V1?那么v到vi?,vj?距离都是偶数,v→vi?→vj?→v这个回路的长度是奇数,和条件矛盾,V2?