中国建设网官方网站app,正规seo关键词排名网络公司,网页设计制作表格代码,手机网站生成app客户端文章目录 基础定义匹配二分图二分图的矩阵覆盖交错路与增广路匈牙利算法饱和X的匹配不管X、Y求最大匹配KM算法可行顶点标号、相等子图相等子图的若干性质KM算法的正确性基于以下定理：算法流程描述1描述2基础定义
匹配 匹配：给定一个无向图 G = V , E G=V,E V , E G=V,E G=V,E，一个匹配是一个边的子集合 M ⊆ E M\subseteq E M⊆E，且满足对所有顶点 v ∈ V v\in V v∈V， M M M中至多有一条边与 v v v关联。对匹配 M M M中的每条边 e = ( u , v ) e = (u,v) e=(u,v)，其两端点 u u u和 v v v称为被匹配M所匹配，而 u u u和 v v 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称为二分图(bipartitegraph)可以用G=X,E,Y表示二分图 图G是二分图$\iff $图G至少有两个顶点，而且G中所有回路的长度都是偶数 证明： 必要性 只有一个点不够二分，故至少有两个顶点。回路的边数和顶点数相同 不失一般性，设一回路从 X 部出发，则下一顶点在 Y 部， 回路上的顶点 X 、 Y 部交替，故 X 部点的数量与 Y 部点数量相同。 顶点数是偶数，边的数量也是偶数 \begin{array}{l} 只有一个点不够二分，故至少有两个顶点。回路的边数和顶点数相同\\ 不失一般性，设一回路从X部出发，则下一顶点在Y部，\\回路上的顶点X、Y部交替，故X部点的数量与Y部点数量相同。\\ 顶点数是偶数，边的数量也是偶数 \end{array} 只有一个点不够二分，故至少有两个顶点。回路的边数和顶点数相同不失一般性，设一回路从X部出发，则下一顶点在Y部，回路上的顶点X、Y部交替，故X部点的数量与Y部点数量相同。顶点数是偶数，边的数量也是偶数 充分性 任意取顶点 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
