参考资料
定义们
记 $N(u)$ 为 $u$ 的所有的邻居构成的集合。对于一个点集 $S$，定义 $N(S)$ 为 $\{ x\mid \forall v\in S, x\in N(v)\}$。
弦图 (chordal graph)：满足任意一个长度大于 3 的环都有弦的图。
单纯点 (simplicial vertex)：如果 $N(u)$ 的导出子图为团，就称 $u$ 为单纯点。
完美消除序列 (perfect elimination ordering)：称 $G$ 的结点的一个排列 $\{v_1,v_2,\cdots v_n\}$ 为 $G$ 的完美消除序列，当且仅当对于每一个 $i$ ，$v_i$ 在 $v_i,v_{i+1},\cdots v_n$ 的导出子图中是单纯点。
下文中，称完美消除序列的逆序为单纯消除序列 (simplicial elimination ordering)（这个中文名称是我编的，因为没有在网上找到相应的中文资料），也就是满足 $v_i$ 在 $v_1,v_2,\cdots v_i$ 的导出子图中为单纯点的排列。
一个定理
引理 1：弦图的任意导出子图也是弦图。
引理 2：任何弦图都至少有一个单纯点；不是完全图的弦图至少有两个不相邻的单纯点。
定理：$G$ 是弦图当且仅当 $G$ 存在完美消除序列。
完美消除序列判定
判断一个序列是否为完美消除序列。
设 $v_i$ 在 $v_{i+1},v_{i+2}\cdots v_n$ 中相邻的点按照它们在序列中出现的顺序依次为 $v_{c_1},v_{c_2},\cdots v_{c_k}$，只需要判断 $v_{c_1}$ 与其它点是否相邻即可。
正确性证明：假设已知 $v_{i+1},v_{i+2},\cdots v_n$ 是合法的完美消除序列的后缀，那么由于 $v_{c_1}$ 在 $\{v_{c_1},v_{c_1+1},\cdots v_n\}$ 的导出子图中为单纯点，如果 $v_{c_1}$ 与 $v_{c_2},v_{c_3},\cdots v_{c_k}$ 都相邻，那么 $v_{c_2},v_{c_3},\cdots v_{c_k}$ 一定形成团。
最大势算法
又称为maximum cardinality search algorithm、MCS algorithm。是用来求完美消除序列的一种算法。
算法流程
设图 $G$ 的点集为 $V$；用 $weight(u)$ 表示点 $u$ 的权重。
- 初始化 $W$ 为 $V$，并将 $V$ 中所有点的权重置为 $0$
- 对 $i=1,2,\cdots n$ ，执行以下过程
- 令 $u$ 为此时 $W$ 中权重最大的点
- 令 $v_i = u$
- 将 $u$ 的所有邻居的权重增加 $1$
- 将 $u$ 从 $W$ 中删除
- 返回 $\{v_1,v_2,\cdots v_n\}$
用链表实现可以做到 $O(n+m)$ 的复杂度。
可以证明，当 $G$ 为弦图时，MCS 算法返回的序列是 $G$ 的单纯消除序列。
正确性证明
令 $V_i = \{v_,v_2,\cdots v_i\}$ ；令 $W_i$ 为第 2 步进行了 $i$ 次之后的 $W$ ；令 $weight_i(v)$ 表示第 2 步进行了 $i$ 次之后 $v$ 点的权重；令 $a \prec b$ 表示在返回的序列中 $a$ 在 $b$ 的前面。
我们通过证明以下循环不变式来证明命题：
- $v_i$ 在 $V_i$ 的导出子图中为单纯点
- 令 $S$ 为 $V$ 的一个子集，其中的每个点 $v_x$ 都满足 $v_x$ 在 $V_x$ 的导出子图中为单纯点；对于两个点 $a,v_i \in N(S) - S$ ，如果 $a\prec v_i$ 且 $N(S)-S$ 中存在一条从 $a$ 到 $v_i$ 的路径，那么 $N(S)-S$ 中存在一条从从 $a$ 到 $v_i$ 且经过的所有点都满足 $\prec v_i$ 的路径
证明 1.
考虑反证：假设 $v_i$ 在 $V_i$ 的导出子图中不是单纯点，那么必定存在 $v_j,v_k\in N(v_i)\cap V_{i-1}$ 满足 $j< k < i, v_k\notin N(v_j)$。
case 1: 对于所有的 $v_j,v_k\in N(v_i)\cap V_{i-1}, v_k \notin N(v_j)$，都有 $V_{i-1}\cap N(v_i)\cap N(v_j) \cap N(v_k) = \varnothing$
对于连通图 $G$ ，我们可以归纳地证明 $V_i$ 都是连通的。而 $N(v_i)$ 中的点显然在 $G$ 的同一个连通块中，所以 $N(v_i)\cap V_{i-1}$ 中的点在 $V_{i-1}$ 的导出子图中是连通的。
找出一对 $V_{i-1}$ 中的 $v_j,v_k$ 使其满足 $v_k \notin N(v_j)$ 且它们在 $V_{i-1}$ 的导出子图中的最短路最短。由于 $v_k \notin N(v_j)$ ，所以最短路的点数大于 2（含 $v_j,v_k$）。
那么最短路上的每个点一定都和 $v_i$ 直接有边相连（如果没有加额外的边则不符合弦图的定义；如果是加的其它的边则不符合最短路的定义）：
- 如果最短路的长度大于 3，那么从这条最短路上随便选取连续的三个点，把第一个点和第三个点作为 $v_j,v_k$，就能得到更短的最短路
- 如果最短路的长度等于 3，那么最短路上的第二个点属于集合 $V_{i-1}\cap N(v_i) \cap N(v_j) \cap N(v_k)$，与 $V_{i-1}\cap N(v_i)\cap N(v_j) \cap N(v_k) = \varnothing$ 矛盾。
case 2: 存在 $v_j,v_k\in V_{i-1} \cap N(v_i), v_k \notin N(v_j)$ 满足 $V_{i-1} \cap N(v_j)\cap N(v_k) \cap N(v_i) \neq \varnothing$
令 $S$ 为满足 $v_i,v_j,v_k\in N(S)-S$ 的仅由 $V_{i-1}$ 中的点构成的集合（显然不为空集的 $S$ 一定存在，并且由归纳假设我们知道 $S$ 中的每个点 $v_x$ 都满足 $v_x$ 在 $V_x$ 的导出子图中为单纯点）。那么 $v_j \to v_i \to v_k$ 是 $N(S)-S$ 中的一条路径，所以一定存在一条 $N(S)-S$ 中的路径 $P=\{v_j = x_0 \to x_1 \to x_2 \cdots x_{m-1} \to x_m = v_k\}$，路径上的每个点都满足 $\prec v_i$（应用不变式2.，注意这里与不变式中的形式不完全一样）。在所有可能的四元组 $(v_j,v_k,S,P)$ 中，我们选择一个 $|S|$ 最大的；如果有两个 $|S|$ 相同的，我们选择 $P$ 的长度更短的。如此，$v_i,v_j=x_0,x_1,\cdots x_m=v_k,v_i$ 将会是一个长度大于 3 的环。根据弦图的定义这个环上一定有弦：
- 如果弦为 $(x_a,x_b)$，其中 $a+1<b$，那么 $P$ 可以更短
- 如果弦为 $(x_a,v_i)$，其中 $0<a<m-1$，那么令 $v_j=x_a,P=\{v_j=x_a\to x_{a+1}\cdots x_{m-1}\to x_m=v_k\}$ 将会使 $P$ 更短；弦为 $(x_a,v_i), 1 < a < m$ 同理
- 否则，$m=2$ 且弦为 $(x_1,v_i)$ ，但是显然此时 $S\cup \{x_1\}$ 是一个更大的满足 $v_i,v_j,v_k \in N(S)-S$ 且每个点都属于 $V_{i-1}$ 的点集。
证明 2.
如果 $a\in N(v_i)$ ，证毕。接下来考虑 $a\notin N(v_i)$ 的情况。
如果存在一个 $b\in (V_{i-1}-S) \cap N(v_i)$，那么对于每个 $s\in S$：
- 若 $s\prec v_i$，则因为 $b,s\in N(v_i)$，在 $V_i$ 的导出子图中我们可以推出 $b,s$ 相邻，所以 $G$ 中 $b,s$ 相邻；
- 若 $a\prec v_i\prec s$，由于 $a,v_i\in N(s)$，在 $V_s$ 的导出子图中可以推出 $a\in N(v_i)$，矛盾
所以一定有 $b\in N(S)-S$，由归纳假设知 $N(S)-S$ 中存在一条从 $a$ 到 $b$ 的只经过 $\prec \max\{a,b\}$ 的点的路径，在这条路径后面加上点 $v_i$ 即得证。
否则 $N(v_i) \cap (V_{i-1}-S)=\varnothing$，所以 $weight_{i-1}(v_i) = \left|S\cap V_{i-1} \right|$。由于 $N(S)-S$ 中存在一条从 $a$ 到 $v_i$ 的路径，这段路径上一定存在两个相邻的点 $c,d$，满足 $c\prec v_i\prec d$（因为从 $v_i$ 出发的第一个点一定 $\succ v_i$，而 $a\prec v_i$），于是推出 $weight_{i-1}(d) \ge |S\cap V_{i-1}|+1$（+1是因为 $c\in N(d),c\prec v_i$），这和 $weight_{i-1}(v_i)$ 为 $weight_{i-1}$ 的最大值矛盾。