他妈的, 信息学竞赛真是太有意思了
二分图
一张图, 可以分成两组\(A, B\), 组内的点没有边相连
二分图的匹配
一组边, 边的端点互不相同
二分图的最大匹配
边数最多的一组边
求二分图最大匹配的匈牙利算法
每次找一条增广路, 这条路径满足: 起始边是未选边, 终止边是未选边, 中间的边选边与未选边交替存在, 且连接两个未选点
然后我们把这条增广路中选边和未选边置反(选边变为未选, 未选变为选, etc), 这样选边的数量就会+1, 依次进行下去, 直到找不到增广路, 我们就找到了二分图的最大匹配
点覆盖
规定一个点覆盖与他相连的所有边, 一个能覆盖所有边的点集称为点覆盖
最小点覆盖
点数量最少的点集称为最小点覆盖
独立集
一个点集, 内部的点没有边相连(二分图的一部就是一个独立集)
最大独立集
点数最多的独立集(易知二分图的独立集大小比两部中点数多的一部的点的数量要多)
好, 上面的都很简单, 下面我们开始了
König定理
二分图的最小点覆盖大小 = 二分图的最大匹配
证明:
对于一个已经完成最大匹配的二分图, 从他的右部每一个不与选边相连的点, 沿着 "未选边-选边-未选边-选边-..." 的顺序dfs, 易知此dfs路径的结尾一定是一个选边, 否则可以成为一条增广路进行增广, 与已知矛盾.
对每一条dfs路径经过的点进行标记.
从整张图来看, 左部标记的点 和 右部未被标记的点 即为最小点覆盖
step.1: 证明这个点集是一个点覆盖
运用反证法: 假设存在一条边, 他的左端点未被标记, 右端点被标记, 则说明该图存在增广路, 与已知矛盾(右端点被标记说明他的右端点是一条"未选边-选边-...-未选边"的结尾, 而左端点未被标记说明上一条路径无法继续延伸, 也就是右端点也是一个未选点, 可以作为结尾形成一条增广路)
step. 2: 证明这个点集的大小是最大匹配
对于每一条匹配边, 有且仅有一个端点属于上述点集(如果是dfs到的边就是左端点属于, 否则就是右端点属于)
step. 3: 证明这个点集是最小的点覆盖
首先我们很容易知道, 最大匹配一定\(\le\)最小点覆盖 (最大匹配比二分图左右两部最小的点数要小)
然后刚刚证明了最大匹配 = 我们刚刚的点集, 所以我们刚刚的点集就是最小点覆盖
好了完事了
最小边覆盖
一个边集, 所有的点都是这个边集中边的端点
最小边覆盖 = 点数 - 最大匹配
证明: 考虑选边加入边集, 显然可以先选最大匹配中边集, 可以保证选这个数量的边时可以覆盖更多的点. 然后对于剩下的点, 随便选与他相连的边即可
即: 最小边覆盖 = 最大匹配 + (点数 - 最大匹配 * 2) = 点数 - 最大匹配
最大独立集 = 点数 - 最大匹配
证明: 考虑从全体点集中删点得出独立集, 发现我们删掉的点组成一个点覆盖, 而要得到最大独立集, 我们要删掉的是一个最小点覆盖.
即: 最大独立集 = 点数 - 最小点覆盖 = 点数 - 最大匹配
DAG的最小不相交路径覆盖
用最少个数的不相交路径覆盖所有的点
拆点, 将每个点\(V\)分为\(\{V_x, V_y\}\), 对于原图的一条边\(U \to V\), 在新图连接\(U_y \to V_x\). 易知新图为二分图
DAG最小不相交路径覆盖 = 原图节点数 - 二分图最大匹配
证明: 开始时将原图每一个点都看作一条路径, 于是在二分图中每匹配一条边就是将两条路径连接在一起. 而二分图匹配的特点保证了一个点不会有两条出边, 也不会有两条入边
DAG的最小可相交路径覆盖
用最少可相交的路径覆盖所有的点
用floyd传递闭包之后用最小不相交路径覆盖就行了
考虑到两条路径在开头和结尾相交其实对答案是没有影响的, 所以对答案真正有影响的是在中间节点相交, 而floyd传递闭包后相当与可以跨过中间节点, 也就没有了不可相交的限制
By Cansult