当前位置: 代码迷 >> 综合 >> 【二分图匹配】
  详细解决方案

【二分图匹配】

热度:19   发布时间:2024-01-18 01:41:57.0

1、一个二分图中的最大匹配数等于等于这个图的最小点覆盖数。

      什么叫最小点覆盖:假如你选了一个点就相当于覆盖了以它为端点的所有边,你需要选择最少的点来覆盖所有的边。

2、最小路径覆盖=|G|-最大匹配数。

在一个N*N的有向图中,路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之相连;(如果把这些路径中的每条路径从它的起点走到终点,那么恰好可以经过图中的每个顶点一次且仅一次);如果不考虑图中存在回路,那么每条路径就是一个弱联通子集。

由上面可以得出:

1、一个单独的顶点是一条路径。

2、如果存在一路径p1,p2......pk,其中p1为起点,pk为终点,那么在覆盖图中,顶点p1,p2......,pk不再与其他的顶点之间存在有向边。

最小路径覆盖是指找出最小的路径条数,使之成为G的一个路径覆盖。

3、最大独立集=顶点数-最大匹配数。

独立集:图中任意两个顶点都不相连的顶点集合。


  相关解决方案