图论定理相关

图论定理相关

———定义———–
DAG上的最小路径覆盖：在DAG上找出最少的路径，使得这些路径经过了所有的点。
最小路径覆盖又分为两种：
1.最小不相交路径覆盖，每一条路径经过的节点必须不同。
2.最小相交路径覆盖，每一条路径经过的节点可能相同。

将DAG转化为二分图：首先Floyd传递闭包，求出两点之间的连通性。然后把每个点复制为x和x’。如果x与y是连通的，就在x和y’上连一条边。
最小不相交路径覆盖就等于，n-最大匹配数。
证明：
根据定义，一个点只可以属于一条路径，求二分图的时候就避免了这样的交叉的路径，问题转化为最小边覆盖。

二分图上的定义：

团：一个顶点集合，由该顶点诱导的子图是一个完全图。
二分图的最大团：在x中找一个子集，在y中找一个子集，使得x的子集中的每个点到y的子集都有连边。
最小点权覆盖集：带点权的无向图中，点权之和最小的点覆盖集
最大点权独立集：带点权无向图中，点权之和最大的点独立集

二分图的性质：
最小点覆盖=最大匹配数。
最小边覆盖=最大独立点集=n-最大匹配数。
最大团 = 补图的最大独立集。
最小顶点覆盖 + 最大独立点集=n。
最小割=最小点权覆盖集=点权和-最大点权独立集