最小点覆盖
定义：
一个点为一条边的任意顶点，则称它为一个点覆盖；用最少点覆盖二分图的所有匹配为二分图的最小点覆盖
一个二分图的最小点覆盖等于该二分图的最大匹配
证明：
反证，若一个二分图的最小点覆盖不等于该二分图的最大匹配，则存在一条边未被覆盖，该二分图存在更大的匹配，不存在，证毕。
DAG的最小不相交路径覆盖
定义：
在一个有向图中，找出最少的不相交路径，使得这些路径经过了所有的点。
把原图中的每个点V拆成Vx和Vy，如果有一条有向边A−>B，那么就加边(Ax,By)。这样就得到了一个二分图，最小路径覆盖=原图的节点数-新图最大匹配。
证明：
一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。
因为路径之间不能有公共点，所以加的边之间也不能有公共点，这就是匹配的定义。
DAG的最小可相交路径覆盖
定义：
在一个有向图中，找出最少的可相交路径，使得这些路径经过了所有的点。
用Floyd判断任意两点之间的连通性，若X与Y相连通，连接X,Y。然后将其转化为DAG的最小不相交路径覆盖
证明：
为了连通两个点，某条路径可能经过其它路径的中间点。比如1->3->4，2->4->5。但是如果两个点a和b是连通的，只不过中间需要经过其它的点，那么可以在这两个点之间加边，那么a就可以直达b，不必经过中点的，那么就转化成了最小不相交路径覆盖。
偏序集的最大反链
定义：在偏序集X中。链是指一个集合SS，SS中的元素互相都有偏序关系。而反链则是指元素相互之间都没有关系的集合。偏序集中的最大反链，其实也就是偏序集中的最大独立集（只要能够到达都算相连）。
定理：DilworthDilworth定理，对于任何偏序集，都有最大反链=最小链的划分，最大链=最小反链的划分。
通过DilworthDilworth定理，我们可以把偏序集中的最大反链问题转化为最小可相交路径覆盖问题。
无向图的最大独立数：
从V个顶点中选出k个顶，使得这k个顶互不相邻。那么最大的k就是这个图的最大独立数
无向图的最大团：
从VV个顶点选出kk个顶点，使得这kk个顶构成一个完全图，即该子图任意两个顶都有直接的边
最小路径覆盖(原图不一定是二分图，但必须是有向无环图，拆点构造二分图)：
在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联
最小路径覆盖 = |V||V| −− 最大匹配数
最小边覆盖(原图是二分图)：
在图中找一些边，使之覆盖了图中所有顶点，且任何一个顶点有且只有一条边与之关联。
最小边覆盖 = 最大独立集 = |V||V| - 最大匹配数
最小顶点覆盖：
用最少的点（左右两边集合的点）让每条边都至少和其中一个点关联
一些转换
最大团 = 补图的最大独立集
最小边覆盖 = 二分图最大独立集 = |V||V| - 最小路径覆盖 最大匹配
最小路径覆盖 = |V||V| - 最大匹配数
最小顶点覆盖 = 最大匹配数
最小顶点覆盖 + 最大独立数 = |V||V|
最小割 = 最小点权覆盖集 = 点权和 - 最大点权独立集 = 最大流
本文转载：https://blog.csdn.net/u013043514/article/details/48206577
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/1effb282.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！