二分图大讲堂――彻底搞定最大匹配数（最小覆盖数）、最大独立数、最小路径覆盖、带权最优匹配
文本内容框架：
§1图论点、边集和二分图的相关概念和性质
§2二分图最大匹配求解
匈牙利算法、Hopcroft-Karp算法
§3二分图最小覆盖集和最大独立集的构造
§4二分图最小路径覆盖求解
§5二分图带权最优匹配求解
Kuhn-Munkers算法
§6小结
每章节都详细地讲解了问题介绍，算法原理和分析，算法流程，算法实现四部分内容，力求彻底解决问题。
§1图论点、边集和二分图的相关概念和性质
点覆盖、最小点覆盖
点覆盖集即一个点集，使得所有边至少有一个端点在集合里。或者说是"点" 覆盖了所有"边"。。极小点覆盖(minimal vertex covering)：本身为点覆盖，其真子集都不是。最小点覆盖(minimum vertex covering)：点最少的点覆盖。点覆盖数(vertex covering number)：最小点覆盖的点数。
边覆盖、极小边覆盖
边覆盖集即一个边集，使得所有点都与集合里的边邻接。或者说是"边" 覆盖了所有"点"。极小边覆盖(minimal edge covering)：本身是边覆盖，其真子集都不是。最小边覆盖(minimum edge covering)：边最少的边覆盖。边覆盖数(edge covering number)：最小边覆盖的边数。
独立集、极大独立集
独立集即一个点集，集合中任两个结点不相邻，则称V为独立集。或者说是导出的子图是零图（没有边）的点集。极大独立集(maximal independent set)：本身为独立集，再加入任何点都不是。最大独立集(maximum independent set)：点最多的独立集。独立数(independent number)：最大独立集的点。
团
团即一个点集，集合中任两个结点相邻。或者说是导出的子图是完全图的点集。极大团(maximal clique)：本身为团，再加入任何点都不是。最大团(maximum clique)：点最多的团。团数(clique number)：最大团的点数。
边独立集、极大边独立集
边独立集即一个边集，满足边集中的任两边不邻接。极大边独立集(maximal edge independent set)：本身为边独立集，再加入任何边都不是。最大边独立集(maximum edge independent set)：边最多的边独立集。边独立数(edge independent number)：最大边独立集的边数。
边独立集又称匹配(matching)，相应的有极大匹配(maximal matching)，最大匹配(maximum matching)，匹配数(matching number)。
支配集、极小支配集
支配集即一个点集，使得所有其他点至少有一个相邻点在集合里。或者说是一部分的"点"支配了所有"点"。极小支配集(minimal dominating set)：本身为支配集，其真子集都不是。最小支配集(minimum dominating set)：点最少的支配集。支配数(dominating number)：最小支配集的点数。
边支配集、极小边支配集
边支配集即一个边集，使得所有边至少有一条邻接边在集合里。或者说是一部分的"边"支配了所有"边"。极小边支配集(minimal edge dominating set)：本身是边支配集，其真子集都不是。最小边支配集(minimum edge dominating set)：边最少的边支配集。边支配数(edge dominating number)：最小边支配集的边数。
最小路径覆盖
最小路径覆盖(path covering)：是"路径" 覆盖"点"，即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点，即每个顶点严格属于一条路径。路径的长度可能为0(单个点)。
最小路径覆盖数＝G的点数－最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。拆点：将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息，从X部往Y部引边。所有边的方向都是由X部到Y部。因此，所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数＝原图G的顶点数－二分图的最大匹配数便可以得解。
Read full article from 二分图大讲堂――彻底搞定最大匹配数（最小覆盖数）、最大独立数、最小路径覆盖、带权最优匹配 - One thing I know,that is I know nothing.(Socrates Greek) - ITeye技术网站
No comments:
Post a Comment