弦图相关

简单记录弦图相关概念和算法。

一些定义

弦：连接环上不相邻两点的边。

弦图：每个简单环都有至少一条弦的无向图。

事实上，可以预见的是，弦图的每个简单环都可以表示为若干三元环的对称差。

团：任意两点都有边的无向图。

单纯点：与其相邻的点集的导出子图是团。

完美消除序列：点集的一个排列 \(\{p\}\) ，满足每个点 \(p_i\) 在 \(p_j (j > i)\) 的导出子图中都是单纯点。

弦图判定

定理：一个无向图是弦图当且仅当它有一个完美消除序列。

对于一个弦图，可以从后往前确定完美消除序列，定义一个点的势为与当前已经确定的点有边的点的数量。每次选择势最大的未加入的点加入完美消除序列即可。

但是如果不是弦图，求出来的序列就不会是完美消除序列，因此弦图判定等价于判定该序列是否为完美消除序列。 从后往前枚举每个点按定义判定即可，需要注意如果当前判定到了点 \(x\) ，说明在其后的点 \(y\) 都是满足完美消除序列的性质的，据此可以在判定的时候优化，复杂度 \(O(n+m)\) 。

最小色数

等于最小团数，等于所有点在加入前的势的最大值加一。

事实上最优方案就是从完美消除序列从后往前染色。

最大独立集

等于最小团覆盖数。

事实上最优方案就是从完美消除序列从前往后加点。