Section-6 BinaryMatch 第6节 二分匹配

Section-6 Binary Match

第6节 二分匹配

  1. Hungarian - 匈牙利算法

  2. HopcroftKarp - Hopcroft-Karp算法

  3. MatchToMaxflow - 二分匹配转化为最大流

  4. KuhnMunkres - Kuhn-Munkres算法

  5. Introduction-Domination_Independent_Covering_Clique - 支配集、独立集、覆盖集、团的介绍

  6. WeightedCoveringAndIndependentSet - 最小点权覆盖和最大点权独立集

  7. MinDisjointPathCovering - 最小不相交路径覆盖

  8. MinJointPathCovering - 最小可相交路径覆盖

  9. Coloring - 染色问题

二分图（Bipartite Graph）

二分图（Bipartite Graph）是一类特殊的无向图G=<V,E>G = <V,E>，图中的顶点可以被划分为两个子集V1,V2V_{1}, V_{2}（满足V1⋂V2=∅,V1⋃V2=VV_{1} \bigcap V_{2} = \varnothing, V_{1} \bigcup V_{2} = V），且使所有边ei,je_{i,j}的两端点分别属于两个顶点子集vi∈V1,vj∈V2v_i \in V_{1}, v_j \in V_{2}。二分图可以表示为G=(V1,V2,E)G = (V_{1}, V_{2}, E)。二分图中的两个顶点子集也可用这样的染色方法描述：二分图中的顶点染成红色或蓝色，且任意两相邻顶点的颜色不同。如下图所示：

二分图中存在的边的子集EmatchE_{match}，其中任意两条边都没有公共/相同顶点。称这样的边子集是一个二分匹配（Binary Match）。

Introduction To Algorithms

图论术语

PreviousMultipleSourceMultipleSinkMaxflow - 多源点多汇点最大流NextHungarian 匈牙利算法

Last updated