二分图相关定理

最小点覆盖

概念:
  • 用一个点集(点集的数量尽可能小),让每条边都至少和其中一个点关联(边的两端有一端在点集里就算有关联)
  • 最小点覆盖是覆盖所有的边

最小点覆盖==最大边匹配(匈牙利算法)

最小边覆盖

概念:
  • 用一个边集(边集的数量尽可能小),让每一个点最少于其中的一条边有关联(点是边的一端就算有关联)
  • 最小边覆盖是覆盖所有的点

最小边覆盖==总点数-最大边匹配

最大(点)独立集

概念:
  • 用一个点集(点集的数量尽可能大),在集合中的任何两点之间没有直接相连的边

最大(点)独立集总点数-最大边匹配最小边覆盖

最小的点覆盖+最大(点)独立集==总点数

证明1:
  • 最小点覆盖最大边匹配,最大(点)独立集总点数-最大边匹配
    所以最小点覆盖+最大(点)独立集==总点数
证明2:
  • 根据概念最小点覆盖是最少的点关联了所有的边,因此在最小点覆盖的点集中的点最少与一条边有关联。所有边的至少一端都在最小点覆盖的点集里,剩下的点直接一定没有直接相连的边要不然最小的点覆盖的点集就没有覆盖全部的边。所以留下的就是最大的点独立集。

最小路径覆盖

1.DAG(有向无环图)的最小不相交路径覆盖

概念:
  • 路径覆盖就是在图中找一些路径,使之覆盖了图DAG中的所有顶点,且任何一个顶点有且只有一条路径与之关联(每个顶点只出现在一条路径中);(如果把这些路径中的每条路径从它的起始点走到它的终点,标记中途经过的点,图中每个点都可以被标记且只标记一次)路径数量尽可能小
    DAG
    一个单独点是一条独立的路径

A:(<1,2>,<3,4>,<5>,<6>)
B:(<1,2,3,4>,<5>,<6>)
C:(<1,2,3,4>,<5,2,3,6>)
其中A,B是图DAG的路径覆盖,然而C是不是,因为节点2,3出现了两次,出现在两条路上
最小不相交路径覆盖==DAG中节点数-对应二分图的最大匹配

由原图DAG构造对应的二分图S,将原图DAG中的每个点(x)拆成两个点(x_1)(x_2)(x_1)(x_2)属于S。DAG(x_1)组成二分图的左集合,(x_2)组成右集合。若原图DAG中有边(<x,y>),则在S中有边(<x_1,y_2>),则上面的图可以得到如下二分图
S

2.DAG的最小可相交路径覆盖

概念:
  • 路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点.节点可以出现在不同的路径中,但是在一条路径中不能出现相同的节点

C:(<1,2,3,4>,<5,2,3,6>)就是图DAG的最小可相交的路径覆盖

如何求最小可相交路径呢?通过加边将最小可相交的路径覆盖变成最小不可相交的路径。要如何加呢?假如节点(x)到节点(y)有路(节点(x)可以借助一条以上的边到达节点(y)),那么就添加一条边(<x,y>)

如图就是所示彩边就是每个点添加的边

void warshell( )
{
//由于前提的DAG(有向无环图)所以不用担心edge[i][i]=1的出现
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=n;j++)
       {
           if(!edge[i][j])//i与j不连通
           {
               for(int k=1;k<=n;k++)
               {
                   if(edge[i][k]&&edge[k][j])//i与k并且k与j连通
                   {
                       edge[i][j]=1;//那么i,j连通
                   }
               }
           }
       }
   }
}

偏序集的最大反链

概念:
  • 在有向无环图(DAG)中,有如下的一些定义和性质:
  1. 链:一条链是一些点的集合,链上任意两个点(x, y),满足要么 (x)能到达 (y),要么(y)能到达(x)

  2. 反链:一条反链是一些点的集合,链上任意两个点(x, y),满足 (x)不能到达 (y),且 (y)也不能到达(x)

  • 最大反链就是一个点集合中的任意两个点(x, y),满足 (x)不能到达 (y),且 (y)也不能到达(x)。尽可能的使集合中的点多(区别最大点独立集)

链覆盖可以多条链可以经过同一节点(类似与最小可相交路径覆盖)
Dilworth定理:对于任意偏序集都有,最大独立集(最大反链)=最小链的划分(最小可相交路径覆盖)

原文地址:https://www.cnblogs.com/lcbwwy/p/13125315.html