二分图相关定理

最小点覆盖

概念：

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

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

最小边覆盖

概念：

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

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

最大(点)独立集

概念：

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

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

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

证明1：

• 最小点覆盖==最大边匹配，最大(点)独立集==总点数-最大边匹配
  所以最小点覆盖+最大(点)独立集==总点数

证明2：

• 根据概念最小点覆盖是最少的点关联了所有的边，因此在最小点覆盖的点集中的点最少与一条边有关联。所有边的至少一端都在最小点覆盖的点集里，剩下的点直接一定没有直接相连的边。要不然最小的点覆盖的点集就没有覆盖全部的边。所以留下的就是最大的点独立集。

最小路径覆盖

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

概念：

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

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

由原图DAG构造对应的二分图S，将原图DAG中的每个点拆成两个点和，和属于S。DAG组成二分图的左集合，组成右集合。若原图DAG中有边，则在S中有边，则上面的图可以得到如下二分图

S

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

概念：

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

C:就是图DAG的最小可相交的路径覆盖

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

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

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. 链：一条链是一些点的集合，链上任意两个点，满足要么 能到达 ，要么能到达 。

2. 反链：一条反链是一些点的集合，链上任意两个点，满足 不能到达 ，且 也不能到达。

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

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