比较冷门，还是学一下。
1.定义
弦：连接环中不相邻两点的边。
弦图：任意长度大于 $3$ 的环都有一个弦的图称为弦图。
2.弦图的判定
2.1 点割集
对于图 $G$ 上的两点 $u,v$，定义这两点间的 点割集 为满足删除这一集合后，$u,v$ 两点之间不连通。如果关于 $u,v$ 两点间的一个点割集的任意子集都不是点割集，则称这个点割集为 极小点割集。
2.2 单纯点
设 $N(x)$ 表示与点 $x$ 相邻的点集。若点集 ${x}+N(x)$ 的导出子图为一个团，则称点 $x$ 为单纯点。
2.3 完美消除序列
令 $n=|V|$，完美消除序列 $v_1,v_2,\ldots ,v_n$ 为 $1,2,\ldots ,n$ 的一个排列，满足 $v_i$ 在 ${v_i,v_{i+1},\ldots ,v_n}$ 的导出子图中为单纯点。
一个无向图是弦图当且仅当其有一个完全消除序列。
2.4 最大势算法 MCS
我们按照逆序即 $n$ 到 $1$ 的顺序给每个点编号，最终得到的序列就是完美消除序列。设 $label_x$ 为与 $x$ 相邻的已标号的节点。我们每次选择 $label_x$ 最大的节点进行编号。 我们用链表维护 $label_x=i$ 的节点即可。时间复杂度为 $\mathcal O(n+m)$。对于弦图使用该算法即可得到完美消除序列。
2.4.1 证明
Lemma 1: 对于任意弦图，一定不存在一个序列 $v_0,v_1\cdots,v_k (k\le 2)$ 满足：
- $v_0,v_1\cdots,v_k$ 的导出子图是一条链。
- $\alpha(v_0)>\alpha(v_i)(i\in[1,k])$。
- 存在 $i\in[1,k-1]$，满足 $\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)$。
证明:
因为 $\alpha(v_1)<\alpha(v_k)<\alpha(v_0)$，且 $(v_0,v_1)$ 间有边相连，$(v_0,v_k)$ 间不相连,所以必然存在 $x$ 满足 $\alpha(v_k)<\alpha(x)$，$(v_k,x)$ 间相连，$(v_1,x)$ 不相连。
我们设最小的 $j\in(1,k]$ 满足 $(v_j,x)$ 相连。我们可以推出 $(v_0,x)$ 不相连，否则 $(v_0,v_1,\cdots,v_j,x,v_0)$ 构成一个长度大于等于 $4$ 且无弦的环。
若 $\alpha(x)<\alpha(v_0)$，则 $v_0,v_1\cdots,v_j,x$ 也是一个满足性质的序列。若 $\alpha(x)>\alpha(v_0)$，则 $x,v_j\cdots,v_1,v_0$ 也是一个满足性质的序列。这样我们扩大了 $\min(\alpha(x),\alpha(v_0))$，一直推下去，则必然产生矛盾。
设得到的序列中 $x$ 的位置为 $\alpha(x)$。我们要证明对于 $\alpha(u)<\alpha(v)<\alpha(w)$，若存在 $(u,v),(u,w)$ 相连，则必然存在 $(v,w)$ 相连。考虑反证， $(v,w)$ 不相连，那么 $w,u,v$ 就是一个满足 Lemma 1 的中性质的序列，我们证明这样的序列不存在，所以矛盾，$v,w$ 相连。
2.4.2 代码
Code
1 | inline void MCS() |
2.5 判断一个序列是否是完美消除序列
根据完美消除序列的定义，设 $v_i$ 在 $v_i,v_{i+1},\cdots,v_n$ 中与 $v_i$ 相邻的按照原顺序为 $v_{c_1},v_{c_2},\cdots,v_{c_k}$，我们只需要判断 $v_{c_1}$ 与其它点是否有边相连即可。使用哈希表即可做到 $\mathcal O(n+m)$。下面给出一种不使用哈希表的做法。
Code
1 | inline bool check() |