【定义】

弦：类比圆上的弦。在一个 \(\ge 4\) 阶的简单环中，一条边如果连接了两个不相邻的点，就称作一条弦。
诱导子图：一张图 \(G\) 对于一个点集 \(S\subseteq V\) 的诱导子图，就是取出 \(S\) 中所有点和 \(E\) 中连接 \(S\) 中点的边构成的子图。
弦图：图中任意 \(\ge 4\) 的环都有弦。
等价定义：任意诱导子图非 \(k\ge 4\) 阶环。

一个简单的性质：弦图的任意诱导子图都是弦图。
邻域。一个点 \(x\) 的邻域用 \(N(x)\) 表示，指所有与 \(x\) 相邻的点。
单纯点：\(x\) 是单纯点 \(\iff\) \(G\) 对 \(N(x)\) 的诱导子图为团。
完美消去序列（缩写 PEO）：是一个点的排列 \(v_1\sim v_n\)，满足 \(v_i\) 在 \(\{v_i\sim v_n\}\) 的诱导子图里是单纯点。
点割集。这是定义在一张图 \(G\) 和两个点 \(u,v\) 上的概念。对于一个点集 \(A\)，若 \(A\) 为 \(u,v\) 的点割集，当且仅当 \(G\) 对 \(V-A\) 的诱导子图中 \(u,v\) 不连通。显然 \(u,v\) 相邻时没有点割集。

【一个重要定理】

\(G\) 是弦图 \(\iff\) \(G\) 有 PEO。

证明：

先证明如果 \(G\) 非弦图就没有 PEO。（\(\Leftarrow\) 的逆否命题）

若 \(G\) 非弦图，必然存在一个诱导子图是 \(\ge 4\) 阶环。假设有 PEO，取环上在 PEO 中排序最靠前的点 \(x\)，\(x\) 在对应诱导子图里不是单纯点，矛盾。所以不存在 PEO。
再证明若 \(G\) 是弦图就有 PEO。考虑一个引理。

引理：弦图必有单纯点。

如果引理得证，那么每次取 \(G\) 的一个单纯点，不断删除。注意 \(G\) 的诱导子图也是弦图。那么定理得证。

接下来转证引理。我们证明一个加强版本：

引理*：弦图必有单纯点；若是非完全图的弦图，必有两个不相邻的单纯点。

然后我们有一个观察。

观察：弦图 \(G\) 对 \(u,v\) 的极小点割集 \(A\) 是团。

极小就是 \(A\) 的子集都不是点割集。

证明一下。

设 \(V-A\) 的诱导子图里 \(u,v\) 分处两个连通分量 \(V_1,V_2\)。\(\forall x\in A\)，\(N(x)\) 与 \(V_1,V_2\) 都有交。否则 \(A\) 不极小。

然后反证法，假设 \(A\) 中不两两有边。考虑 \(A\) 中不相邻的两点 \(x,y\) 的最短路。记在最短路中，\(x\) 与 \(V_1\) 中 \(x_1\) 相邻，\(y\) 与 \(V_1\) 中 \(y_1\) 相邻；\(V_2\) 中也有 \(x_2,y_2\) 与 \(x,y\) 分别相邻。（这里 \(x_1,y_1\) 是否相同不重要）

因为是最短路，所以 \(x\rightarrow x_1(\rightarrow y_1)\rightarrow y\rightarrow y_2(\rightarrow x_2)\rightarrow x\) 这个环里面肯定没有弦，否则可以更短；然而这就得出一个至少四条边的无弦的环。而 \(G\) 是弦图，矛盾。所以 \(A\) 必两两有边，即 \(A\) 是团。

引理*：弦图必有单纯点；若是非完全图的弦图，必有两个不相邻的单纯点。

然后用这个观察证明加强引理。采用归纳法，显然 \(n=1\) 的加强引理成立。

对于 \(n>1\) 的弦图 \(G\)，若 \(G\) 是完全图，显然；若 \(G\) 不连通，肯定能在至少两个连通块里归纳下去，必有至少两个不相邻的单纯点。

当 \(G\) 连通且非完全图，取点 \(u,v\) 不相邻和 \(A\) 为 \(u,v\) 的一个极小点割集。类似记 \(u,v\) 在 \(V_1,V_2\) 里。因为 \(V_1,V_2\) 不连通，如果我们能各自找出一个单纯点，可以得证；而由对称性，只需证明 \(V_1\) 有单纯点即可。
1. 若 \(V_1\cup A\) 是团。显然 \(V_1\) 中任一点的邻域都是团，都是单纯点。
2. 否则由归纳假设，\(V_1\cup A\) 里有两个不相邻的单纯点。因为 \(A\) 是极小点割集，是一个团，不可能两个单纯点都在 \(A\) 且不相邻；所以 \(V_1\) 中至少有一个单纯点。
证毕。

于是定理完成证明。

【算法】

【求 PEO：LEX-BFS 算法】

字典序-广搜算法。可以在线性时间里求出一个序列 \(P\)。如果 \(G\) 是弦图，求出的是一个 PEO。（我们后面讲到线性判定 PEO 的算法，搭配使用）

定义一个点的 \(pred\) 为所有已访问的邻居的标号构成的集合。算法开始的时候，任取一个点标号 \(n\)，直到标完 \(1\) 算法结束。

一句话：每次从所有未访问的点中取 \(pred\) 最大的，标下一个号。

怎么比较 \(pred\)？先比最大的元素，大的大；相同则比次大，次次大 …… 都相同，则 \(size\) 大的大。

每个点的标号就是在答案序列里的位置。

先说怎么实现。

用一个链表维护。给每个结点除了前驱后继，额外记录一个 \(id\)。\(id\) 相同的是同一个 \(pred\)；然后越往后继方向走，\(pred\) 就越小。

每次取最靠前的点，枚举其邻点。如果这个邻点是这个邻点 \(id\) 中第一个被访问到的，开一个新的 \(id\)，然后让旧 \(id\) 赋值为新 \(id\)，再把它提到旧 \(id\) 那一段最前面；如果这个邻点的 \(id\) 新建过了，让它接到最近结点的后面。

证明这个算法在弦图一定能求出一个 PEO。

反证法。考虑得出的序列 \(p\)。如果不正确，必然存在 \(i<i_1<i_2\)（这里的 \(<\) 是 \(p\) 中靠前），且 \(i_1,i_2\in N(i)\)，\(i_1,i_2\) 无边。

因为 \(i<i_1\)，则 \(i_1\) 更早访问；而 \(i\) 的 \(pred\) 有 \(i_2\)，\(i_1\) 的 \(pred\) 没有，所以 \(i_1\) 一定有 \(i_3>i_2\) 且 \(i,i_3\) 无边，才能比 \(i\) 更早搜到。

如果 \(i_2,i_3\) 有边，\(i,i_1,i_2,i_3\) 构成无弦四元环，非弦图。

否则对比 \(i_1,i_2\)，\(i_2\) 更靠后但是 \(i_1\) 有 \(i_3\)。所以 \(i_2\) 必有 \(i_4\) 且 \(i_1,i_4\) 无边。若 \(i_4\) 与 \(i_3\) 有边，构成无弦五元环了。

循环往复，但是点个数有限，矛盾。

【线性判定 PEO】

朴素算法可以枚举序列每个点，再枚举所有在它后面的邻点判断是否是团。复杂度 \(O(\sum d_i^2)\)。

但是发现对于点 \(x\)，只需要找到在它后面的第一个邻点 \(nei\)，然后判断 \(nei\) 是否与 \(nei\) 之后的 \(x\) 的邻点有边即可；因为 \(nei\) 之后的 \(x\) 的邻点的内部已经在 \(nei\) 的时候判断了是不是团了。复杂度 \(O(\sum d_i)\)。

【应用】

弦图的最大团、最小染色数（给点染色，相邻不同色）、最大独立集、最小团覆盖都能线性求。

注意在一般图里，最大团 \(\le\) 最小染色数，最大独立集 \(\le\) 最小团覆盖。而在弦图里，这两个不等式都取到等号。

标签：,子图,诱导,相邻,单纯,PEO,id
From： https://www.cnblogs.com/FLY-lai/p/18321894

弦图