弦图学习笔记

· · 个人记录

基础定义

定义 1（弦图） 设 G=(V,E) 是简单无向图。设 v_1,v_2,...,v_n\in V 是图中的互异节点，称 (v_1,v_2,...,v_n) 构成一个环（cycle） 当且仅当 \forall 1\leq i < n，v_i 和 v_{i+1} 均有边相连且 v_n 和 v_1 有边相连，此时记这个环的长度为 n。G 是弦图（chordal graph），当且仅当对于 G 中的任意长度大于等于 4 的环，总存在一条连接环上不相邻两点的无向边，这样的边称为该环的一条弦（chord）。

定义 2（生成子图） 设 G=(V,E) 是无向图，V'\subset V 是原图顶点的一个子集。定义 G 关于 V' 的生成子图 G(V') 是以 V' 为顶点集的图，其边集是 G 中两端都在 V' 里的所有的边。我们也可以用生成子图的理论改写弦图的叙述：简单无向图 G=(V,E) 是弦图，当且仅当不存在长度 n\geq 4 的顶点序列 v_1,...,v_n，使得 G(\{v_1,...,v_n\}) 中包含且只包含 (v_1,v_2),...,(v_{n-1},v_n),(v_n,v_1) 这些边。

完美消除序列

本节的主要研究对象如下：

定义 3（完美消除序列） 设 G=(V,E) 是有 n 个节点的简单无向图。设 (p_1,...,p_n) 是 V 中节点的一个排列，称其为 G 的完美消除序列，当且仅当：

上面的条件也可以改写为：

本节的核心是证明下面的定理：

定理 4 简单无向图有完美消除序列当且仅当它是弦图。

同时，本节还会给出判定无向图是否是弦图的算法，以及求出弦图的完美消除序列的方法。

我们首先证明一个相对简单的部分：

定理 4 的第一部分 有完美消除序列的简单无向图一定是弦图。

证明 设 G 不是弦图，那么 G 必然有 k\geq 4 个节点组成的无弦环 (v_1,...,v_k)。方便起见下面记 v_{k+1}=v_1,v_0=v_k。设 v_1,...,v_k 中最先出现的点是 v_i，那么 v_i,v_{i-1},v_{i+1} 就违反了完美消除序列的性质，矛盾！故 G 一定是弦图。

接下来我们给出一个求解弦图完美消除序列的算法，并借助这个算法证明：弦图一定有完美消除序列。这个算法是著名的最大势算法：

算法 5（最大势算法） 设输入 G=(V,E) 是有 n 个节点的简单无向图。对于每个节点 i，赋予一个标记 \mathrm{label}_i，初始时均为 0。设 p 是答案序列，接下来重复执行下面的操作 n 次：

定理 4 的第二部分 接下来我们将要证明：若 G 是弦图，那么算法 5 给出的序列 p 便是 G 的完美消除序列。不失一般性，设算法 5 给出的序列为 1,2,...,n。我们想证明：不存在 i < j < k 使得 (i,j),(i,k) 间有边而 (j,k) 间无边。为此，我们证明一个更强的命题：

引理 6 在上述条件下，设 k\geq 2，那么不存在 k+1 个互异节点 v_0,v_1,...,v_k，使得：

证明 假设存在一个这样的序列。我们的思路是：利用算法的过程和这个序列，找出一个新的符合条件的序列，进而可以得到无穷多个符合条件的序列，这样就和有穷性推出矛盾了。

由于 v_0 > v_k > v_1 且边 (v_0,v_1) 存在而 (v_0,v_k) 不存在，说明 v_0 给 \mathrm{label}_{v_1} 贡献了 1 而没有给 \mathrm{label}_{v_k} 贡献。但 v_k 还是比 v_1 先加入了答案序列，这说明存在一个节点 x > v_k 使得 x 给 \mathrm{label}_{v_k} 贡献了而没有给 \mathrm{label}_{v_1} 贡献，即存在边 (v_k,x) 而没有边 (v_1,x)。

设 j 是最小的在 [2,k] 之间的使得 (v_j,x) 存在的 j（由于 (v_k,x) 存在，这样的 j 必定存在）。那么，(v_0,x) 必然不存在（否则就形成了无弦环 (v_0,...,v_j,x)）。可以看出，序列 (v_0,...,v_j,x) 是一个满足条件 A 的序列。为了进一步满足条件 B，我们讨论 v_0 和 x 的大小关系：

综上，我们找到了一个新的符合题设的序列。再观察一下可以发现：新序列的尾项严格大于原来的尾项 v_k，这说明：我们按这个策略生成的序列一定不会重！那么，从这个方法我们就可以生成无限组满足条件的序列。可另一方面，这样的序列最多只有有限组，矛盾！故引理 6 得证。

引理 6 得证后，证明定理 4 的余下部分变得非常简单。如果存在 i < j < k 且 (i,j),(i,k) 存在而 (j,k) 不存在，那么 (k,i,j) 便是符合引理 6 中条件的序列，矛盾！故定理 4 证毕。

团树和子树图

弦图理论的应用