弦图
定义与性质
定义 1.1
弦是连接环上不相邻的两点的边。
弦图是无向图,满足任意 \(k(k>3)\) 元环都有至少一个弦。
性质 1.1
弦图的生成子图是弦图。
证明:若不是弦图,则加上剩余的点也不会让这个无弦环有弦。
定义 1.2
对于图 \((V,E),x,y\in V\),若 \(V'\subseteq V\) 满足 \(V-V'\) 的生成子图中 \(x,y\) 不连通,则称 \(V'\) 是 \(x,y\) 的一个点割集。
记 \(N(u)=\{x\mid (u,x)\in E\}\)。
性质 1.2
设 \(V'\) 是 \(x,y\) 的一个极小点割集,\(x,y\) 在 \(V-V'\) 生成子图的连通块是 \(V_x,V_y\),则 \(\forall v\in V'\),\(N(v)\cap V_x\neq \varnothing ,N(v)\cap V_y \neq \varnothing\)。
证明:否则,加上 \(v\) 之后 \(x,y\) 仍然不连通, \(V'-\{v\}\) 也是 \(x,y\) 的点割集,从而 \(V'\) 不是极小的。
定理 1.1
弦图上任意两点 \(x,y\) 的任意极小点割集 \(V'\) 的生成子图是完全图。
证明:首先认为 \(|V'|>1\)。
任取 \(u,v\in V'\),则 \(|N(u)\cap V_x|>0,|N(v)\cap V_x>0|\),那么 \(u,v\) 存在只经过 \(V_x\) 中点的路径,找到最短的一条。这条长度 \(\ge2\)。对于 \(V_y\) 同理。此时我们得到了一个长度 \(\ge 4\) 的环。弦不可能在 \(V_x,V_y\) 之间(不连通性质),也不可能在 \(V_x,V_y\) 内部或者和一端和 \(u\) 或者 \(v\) 相连(这样不是最短),那么弦就是 \((u,v)\)。
因此任意两点 \(\in V'\) 都有边,\(V'\) 是完全图。
定义 1.3
如果 \(x\cup N(x)\) 的生成子图是完全图,称 \(x\) 为图的一个单纯点。
性质 1.3
任何弦图都有至少一个单纯点,不是完全图的弦图至少有两个不相邻的单纯点。
证明:
归纳证明。
结论对完全图显然成立。
设 \((x,y)\not\in E\),\(V'\) 是一个极小点割集。设 \(L=V_x\cup V’\),\(G'\) 为 \(L\) 生成子图。
如果 \(G’\) 是完全图,显然 \(x\in V_x\) 是一 \(G'\) 单纯点。否则,由归纳假设,\(G'\) 有两个不相邻的单纯点;
由于 \(V'\) 是完全图,\(V_x\) 一定有 \(G'\) 单纯点(最多有一个在 \(V'\))。而 \(V_x\) 在 \(G'\) 的单纯点显然也是在 \(G\) 的单纯点。
同样,在 \(V_y\) 还有一个。证毕。
定义 1.4
设 \(p\) 为 \(1\sim n\) 的排列,若 \(\forall i\in[1,n]\cap\Z,p_i\) 在 \(\{p_i,p_{i+1},\dots,p_n\}\) 的 \(G\) 的生成子图上是单纯点,称 \(p\) 是 \(G\) 的完美消除序列。
以下的左、先代表下标更小。
定理 1.2
一个无向图具有完美消除序列当且仅当它是弦图。
证明:
如果一个无向图具有完美消除序列,假设其存在长度 \(\ge 4\) 的环,\(x\) 为在这个环上对应 \(p\) 最靠左的一个,则它在环上相邻的两点之间必有边,这就是一个弦。
如果一个无向图是弦图,可以先消除单纯点,再把剩下的点的生成子图(这也是弦图)归纳做。
算法 1.1 最大势算法
上面的构造过程朴素实现是 \(O(n^4)\) 的,自然无法满足需求。
最大势算法(MCS 算法)可以 \(O(n+m)\) 求出弦图的完美消除序列,当然可以判定一个图是否是弦图。
流程:
维护一个初始为空的序列;
每次把邻域已加入序列点最多的点加入序列,重复这样的操作直到所有点都被加入序列。
反转此序列。
最终得到的序列就是完美消除序列。
为了证明此算法正确性,我们需要知道一个引理。
以下设 \(\alpha(x)\) 为 \(x\) 在这个序列中的位置。
引理 1.1
若 \(\alpha(u)<\alpha(v)<\alpha(w)\),且 \((u,w)\in E,(v,w)\not\in E\),则 \(\exists x,\alpha(v)<\alpha(x),(v,x)\in E,(u,x)\not\in E\)。
证明:显然,必须得有一个补齐贡献。
引理 1.2
一个序列 \(v_0,v_1,\dots,v_k(k\ge 2)\) 不可能同时满足以下条件,其中 \(\alpha\) 是一个弦图 \((V,E)\) 的序列得出的:
\[\left\{\begin{matrix} (v_i,v_{i+1})\in E\\ (v_i,v_j)\not\in E(|i-j|>1) \\ \exists i\in (0,k)\cap \Z,\alpha(v_i)<\alpha(v_{i+1})<\dots<\alpha(v_k),\alpha(v_i) <\alpha(v_{i-1})<\dots<\alpha(v_1)<\alpha(v_k)<\alpha(v_0) \end{matrix}\right. \]证明:
根据引理 1.1 和 \(\alpha(v_1)<\alpha(v_k)<\alpha(v_0)\) 得到 \(\exists x,\alpha(v_k)<\alpha(x),(v_k,x)\in E,(v_1,x)\not\in E\)。
找到最小的 \(j>1\) 满足 \((v_j,x)\in E\),则 \((v_0,x)\not\in E\),否则得到一个无弦环 \((v_0,v_1,\dots,v_j,x)\),不符合弦图定义。
若 \(\alpha(x)<\alpha(v_0)\),则令当前序列为 \(v_0,\dots,v_j,x\),否则为 \(x,v_j,v_{j-1},\dots,v_0\)。
这样的操作可以无穷进行,而每次 \(\min(\alpha(v_0),\alpha(v_k))\) 会变大,而此项不超过 \(n\),矛盾。
定理 1.3
以上算法正确求出了弦图的完美消除序列。
标签:1.1,cap,子图,单纯,alpha,序列,Genshin From: https://www.cnblogs.com/british-union/p/xiantu.html