弦图学习笔记

弦图

基本介绍与基本性质

弦，即连接环中不相邻两点的边

弦图，即任意一个长度大于3的环均存在一条弦的无向图

弦图是一种特殊的图，很多在一般图上的 NP-Hard 问题在弦图上都有优秀的线性时间复杂度算法。

区间图，

即在一条数轴上存在若干个区间，存在边 $(u,v)$ 当且仅当区间 $u$ 与区间 $v$ 有交的无向图

区间图是弦图

团数：最大团的点数，记作 $\omega(G)$

色数：最小染色的颜色数，记作 $\chi(G)$

$\text{Lemma}:\space \omega(G)\leq \chi(G)$

考虑对于最大团的导出子图，至少需 $\omega(G)$ 种颜色

最大独立集：最大的点集使得点集的导出子图边集为空的点集大小，记作 $\alpha(G)$

最小团覆盖：以最少的团覆盖整个点集所用团数，记作 $\kappa(G)$

$\text{Lemma}:\space \alpha(G)\leq \kappa(G)$

考虑最小团覆盖中最多每个团选一个进最大独立集

弦图的判定

前置定义

记 $N(x)$ 为点 $x$ 的邻域，若 $\{x\}+N(x)$ 的导出子图为一个团，则称点 $x$ 为单纯点

定义图 $G$ 的完美消除序列 $v_1,v_2\dots,v_n$ 为 $1,2\dots,n$ 的一个排列

满足 $v_i$ 在 $\{v_{i},v_{i+1},\dots,v_n\}$ 的导出子图中为一个单纯点

$\text{Lemma}:$ 一个无向图是弦图当且仅当其有一个完美消除序列

完美消除序列

朴素算法

每次找到图中的一个单纯点，加入到完美消除序列中

正确性显然，复杂度 $O(n^4)$

$\text{MCS}$算法

即最大势算法，可在 $O(n+m)$ 的时间复杂度内找出完美消除序列

算法流程

逆序加入完美消除序列（因为完美消除序列的限制是后缀的形式）

设 $label_x$ 表示点 $x$ 已与多少个以放入完美消除序列的点相邻

每次从全局选择 $label$ 最大的点 $x$ 加入完美消除序列

以链表类似桶维护不同 $label$ 的点

判定完美消除序列

记 $v_i$ 相连的点中在完美消除序列后面离 $i$ 最近的点为 $v_j$

只需判断 $v_j$ 是否与 $N(v_i)\cap\{v_{i+1},v_{i+2}\dots,v_n\}$ 的点都相连，并把问题归到 $v_j$ 身上

复杂度 $O(n+m)$

综上，我们能以 $O(n+m)$ 的复杂度判断一个图是否为弦图，且得到该图的完美消除序列

弦图上的NP-Hard

极大团

弦图的极大团一定是 $\{v_i\}\cup (N(v_i)\cap\{v_{i+1},v_{i+2}\dots,v_n\})$

时间复杂度 $O(n+m)$

团数与色数

构造方法：按完美消除序列从后往前贪心染色复杂度 $O(n+m)$，且 $\chi(G)=\omega(G)$

正确性证明较简单，只需考虑在决定 $v_i$ 的颜色时，影响它颜色的点与它在一个团内即可

最大独立集与最小团覆盖

最大独立集：完美消除序列从前往后，贪心选即可

最小团覆盖即最大独立集中每一个元素在完美消除序列上之后的邻域所组成的团

显然上面所述算法所得两答案均一致，设为 $s$，由定义 $t \le \alpha(G),t\ge \kappa(G)$，又$\alpha(G)\le \kappa(G)$

故 $t=\alpha(G)=\kappa(G)$

参考资料

OI-wiki