dwjshift's Blog

最大势算法的证明

| Comments

到处都找不到证明,于是跑去翻了一下tarjan老爷子当年的论文
然而看了半天并没有看懂他在说什么,只好自己瞎证了一下……

表示最大势算法得到的序列,我们要证明当是弦图的时候倒序是一个完美消除序列。
表示节点中的位置。

引理1

,那么必然存在满足
Proof.
若不存在这样的,那么在标记的时候相邻的已标记点必定多于,矛盾。

引理2

若存在路径满足,那么必然存在路径满足之间有边。
Proof.
使用数学归纳法,当分别为最早标记的两个点时显然成立。
不是最早标记的两个点时,根据引理1可得必然存在满足。此时要么,要么满足引理2,均能得证。

定理

在最大势算法中,某个点被标记时,它在与已标记点形成的诱导子图中必然是一个单纯点。
Proof.

根据引理2,此时要么之间有边,要么能通过已标记的点连通。
之间没有边,说明图中存在至少四元的无弦环,矛盾。

于是就证完辣!

Comments

comments powered by Disqus