弦图

定义与性质

定义 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\)，矛盾。