二分图:将图中的顶点分为两个集合X和Y,X与Y集合没有交集,并且各自集合内的点没有边相连,X集合与Y集合形成边
二分匹配:在二分图的基础上,X Y两个集合所形成的边集中的子集M,M中的任意两条边没有公共的顶点
最大匹配:当M中的边数达到二分图的上限时称为最大匹配
完美匹配:二分图中的所有顶点都在匹配的边上,称为完美匹配
增广路:在图中的一条路径从未匹配的顶点开始到未匹配的顶点结束,其中路径是待匹配边与已匹配边交替出现
最小点覆盖:选取最少的点数(可以是X||Y集合),使这些点和所有的边都有关联(把所有的边的覆盖)
最小边覆盖:在图中找一些边,使之覆盖了图中所有顶点,且任何一个顶点有且只有一条边与之关联。
最大独立集:在集合中的任意两点没有边,并且集合中的顶点个数达到上限
最大团:在集合中的任意两点有边,并且集合中的顶点个数达到上限
匈牙利算法:每次寻找增广路,如果能寻到匹配加1
二分图的最小顶点覆盖数 = 二分图的最大匹配数
二分图的最大独立集数 = 节点数(n)- 最大匹配数(m)
最大团=节点数-补图的最大独立集
最小边覆盖数=节点数(n)- 最大匹配数(m)