Db6dae0f2d0ebb69bf1d00b57de8ea0a
匈牙利算法

1 二分图

  二分图:又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边<i, j>所关联的两个顶点i和j分别属于这两个不同的顶点集(i∈A, j∈B),则称图G为一个二分图。
  简单来说,如果图中所有顶点可以被分为两个集合,图中所有的边的头和尾不属于同一个顶点集合,而是跨越两个集合,则这个图是一个二分图。
  例如:图1.1所示的图,无论如何划分顶点集合,也不能保证所有边的头和尾隶属于不同集合,因此,图1.1所示的图不是二分图。
图1.1

图1.1

  例如:图1.2所示的无向图:

图1.2

图1.2

  将顶点a,b,c,d作为集合A,将e,f,g,h作为集合B,将图1.2转化为图1.3所示:
图1.3

图1.3

  可以看出,图中顶点可以划分为A,B两个集合,而任意一条边的头和尾又分别隶属于集合A和集合B,因此,此图为二分图。

2 匹配

  匹配:在图论中,一个匹配(matching)是指一个边的集合,其中任意两条边都没有公共顶点。
  例如:图2.1中红色的边,可以为图1.3所示图的一个匹配。
图2.1

图2.1

3 最大匹配

  最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。图 3.1是一个最大匹配,它包含4条匹配边。
图3.1

图3.1

4 完美匹配

  完美匹配:如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突),但并非每个图都存在完美匹配。

5 交替路径

  交替路径:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边...形成的路径称为交替路径。

6 增广路径

top Created with Sketch.