Java教程

关于最小路径覆盖

本文主要是介绍关于最小路径覆盖,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

首先最小路径覆盖问题的前提是 \(DAG\) ,并且有两种,一种是最小相交路径覆盖问题(一个点可以在多条路径中)又名最小边覆盖,另一种是最小不相交路径覆盖问题(一个点只能被覆盖在一条路径中)又名最小点覆盖。

最小不相交路径覆盖问题

这个东西的解的数量我不知道有没有什么数学上的解法,目前我只能用算法搞。首先用 \(n\) 条路径独立覆盖每一个点,然后为了让路径最少我们要想办法去合并,像这种合并会有贡献,但是又具有后效性,求最大贡献的题,自然想到网络流,简单的可以考虑二分图,这里我们考虑二分图。

将每个点拆成 \(X_i,Y_i\),然后如果两个点 \(u,v\) 之间有边,我们在二分图中给 \(X_u,Y_v\) 连边,然后跑最大匹配,最后方案根据匹配对象就可以确定是哪两个点合并了。

最小相交路径覆盖问题

解法是先用 \(floyd\) 传递闭包,然后继续跑最小不相交路径问题即可。

但值得一提的是,最小路径覆盖的解的数量在数学上,有 \(Dilworth\) 定理 :最小相交路径覆盖=最小边覆盖=最长反链长度

事实上 \(Dilworth\) 定理本身是偏序的定理,下面的证明源于《组合数学》

定义:

偏序集 \((X,\le)\) :两个数如果可比,那么关系满足自反性,传递性,反对称性

链:任意两个元素可比的子集

反链:任意两个元素不可比的子集

划分:将集合中的每个数都分到子集中,任意两个子集不存在公共元素。

最大元: \(x\) 是偏序集 \((X,\le)\) 中的最大元,当且仅当不存在 \(x'\in X,x\le x'\)

最小元: \(x\) 是偏序集 \((X,\le)\) 中的最小元,当且仅当不存在 \(x'\in X,x'\le x\)

\(Dilworth\) 定理:在偏序集 \((X,\le)\) 中若最长反链长度是 \(m\) ,那么偏序集最少且可以划分为 \(m\) 条链。

首先证明“最少”:由定义可得一条反链与一条链的交不超过 \(1\) ,由于鸽巢原理至少需要 \(m\) 条边。

再证明“可以”:首先,所有最大元构成一条反链,所有最小元也构成反链。对偏序集的大小进行归纳,设这个偏序集的最长反链的长度是 \(m\) ,分两种情况讨论:

如果存在一条反链不是最大元构成的反链也不是最小元构成的反链,那么设这条反链是 \(A\) ,考虑两个偏序集:

\(A^+=\{x:x\in X且对A中某个a,a\le x\}\)

\(A^-=\{x:x\in X且对A中某个a,x\le a\}\)

显然 \(A\) 是 \(A^+\) 中的最大元构成反链,同时也是 \(A^-\) 中的最小元构成的反链,那么根据归纳假设,这两个偏序集中都存在 \(m\) 条链的划分方案,而且 \(A\) 中每个元素都在不同的链中,于是我们把这两个集合中同一个 \(a\in A\) 所在的两条链拼起来,于是我们就形成了 \(m\) 条链的划分。

如果反链一定是最大元构成的反链或者最小元构成的反链,那么我们我们取出任何一个最大元 \(x\) ,一个最小元 \(y\) ,满足 \(x\le y\) ,则 \(X-\{x,y\}\) 的最长反链最长是 \(m-1\) ,然后 \(\{x,y\}\) 也是一条链,于是我们又构造了方案。

事实上这个定理有“对偶”的定理,若一个偏序集最长链的长度是 \(m\) ,那么最少划分为 \(m\) 条反链。

“最少”和上面一样,至于可行,我们每次去掉一层最小元,然后最长链是 \(m\) ,所以最多分为 \(m\) 层,每一层都是都是一个反链。

关于图中,因为可以相交,所以证明是类似的。

这篇关于关于最小路径覆盖的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!