# 弦图

# 概念

# 弦(chord)

连接环中不相邻的两个点的边

# 弦图(chordal graph)

一个无向图称为弦图，当且仅当图中任意长度大于 3 的环都至少有一个弦.

# 单纯点(simplicial vertex)

设 $N(v)$ 表示与点 $v$ 相邻的点集. 一个点称为单纯点当且仅当 $\{v\} + N(v)$ 的诱导子图为一个团.

# 几个性质

• 弦图的每一个诱导子图一定是弦图
• 弦图的任一个诱导子图不同构与 $C_n(n > 3)$ (TODO: $C_n$ 是什么..感觉是含 $n$ 个结点的完全图)

# 一个引理

任何一个弦图都至少有一个单纯点， 不是完全图的弦图至少有两个不相邻的单纯点.

# 完美消除序列(perfect elimination ordering)

# 定义

一个点的序列（每个点恰好出现一次）$v_1, v_2, \dots, v_n$ 满足 $v_i$ 在 $\{v_i, v_{i+1}, \dots, v_n\}$ 的诱导子图中为一个单纯点.

# 定理

一个无向图是弦图当且仅当它有一个完美消除序列.

# 求完美消除序列

# 朴素算法

1. 每次找一个单纯点 $v$，加入到完美消除序列中.
2. 将 $v$ 及其相关的边从图中删掉.
3. 重复以上过程直到所有点被删除（图是弦图，得到了完美消除序列）或不存在单纯点（图不是弦图）.

# 字典序广度优先搜索

# 最大势算法

• 从 $n$ 到 $1$ 的顺序依次给点标号（标号为 $i$ 的点出现在完美消除序列的第 $i$ 个）
• 设势 $p_i$ 表示第 $i$ 个点与多少个已标号的点相邻，每次选择 $p_i$ 最大的未标号的点进行标号

为在 $\mathcal{O}(n+m)$ 的时间内实现，又由于 $p_i$ 最大为 $n$，用 $n$ 个链表维护每个势的结点，即链表 $L_x$ 维护那些 $p_i = x$ 的结点 $i$. 再记录一下当前最大的势 $S$，每次从 $L_S$ 中取出一个结点进行编号，并更新其相邻结点的势加入对应的链表中，同时更新最大势.

# 判断一个序列是否为完美消除序列

• 设 $\{v_{i+1}, \dots, v_n\}$ 中与 $v_i$ 相邻的点依次为 $v_{j_1}, v_{j_2}, \dots, v_{j_k}$
• 只需判断 $v_{j_1}$ 是否与 $v_{j_2}, \dots, v_{j_k}$ 相邻即可
• 时间复杂度 $\mathcal{O}(n+m)$