弦图学习笔记
参考: WC2009讲稿
定义及性质：
不存在 (geq 4) 的简单环的图，即对于图中每一个 (geq 4) 的环，都存在至少一条连接环不相邻节点的边。
弦图的每一个导出子图都是弦图，其任意一个导出子图不同构与 (geq 4) 的简单环。
单纯点：
记 (N(v)) 为 (v) 的相邻点集，(v) 为单纯点当且仅当 (v + N(v)) 的导出子图为一个团。
引理 ：任何一个弦图都有至少一个单纯点，不同于完全图的弦图至少有两个相邻的单纯点。
完美消除序列：
对于一个点的排列 (p_i) ，满足 (forall p_i) 在 ({v_i,v_{i+1}..v_n}) 的导出子图中是一个单纯点。
求法： 最大势算法可以在 (mathcal O(n+m)) 的复杂度内求出一个消除序列的反序。一开始设所有点的权值为 (0) ，每次随便取出一个权值最大的点加入序列，并把其相邻的点权值 (+1) 。
判定：对于每一个点 (v) ，设 (N(v)) 在其序列位置之后的点集为 (N'(v)) ，检查 (N'(v)) 中第一个点是否与其它点有连边即可。
弦图的判定定理：
一个无向图是弦图当且仅当它有一个完美消除序列。
充分性： 引理可以得知一个弦图至少有一个单纯点，删去这个单纯点后仍然是一个弦图，可以数学归纳证明。
必要性：若无向图中存在一个 (k geq 4) 的无弦环，若存在完美消除序列，取出这个环在消除序列中最前面的点，此时消除序列说其导出子图是团，与无弦环矛盾。
弦图的判定：
用最大势算法求出一个可能的完美消除序列， (mathcal O(n + m)) 判断这个完美消除序列是否合法即可。
弦图的极大团：
弦图的极大团一定是 (v cup N'(v)) 的形式，设 (next(v)) 为 (N'(v)) 中出现最前的点，若存在一个 (u) ，满足
那么意味着 (vcup N'(v)sub u cup N'(u)) ，此时 (v cup N'(v)) 不是极大团，那么只需要判断是否存在一个这样的 (u) 即可，可以 (mathcal O(n+m)) 计算。
弦图的点染色问题：
最小点染色：每次贪心的在完美消除序列上染色， 给当前点染一个可以染的最小的颜色，即是弦图的最小染色数。假设使用了 (T) 种颜色，(T=) 最大团点数，又因为最大团点数 (leq) 色数，所以这样求出的 (T) 是最小的染色数。
k-染色方案数计数：(=prod_{i=1}^n k-N'(p_i)+1)，因为 (forall vcup N'(v)) 都是其所在完美消除序列后缀的极大团， (v) 颜色不能与 (N'(v)) 中任意一个相同。
弦图的最大点独立集：
在完美消除序列上从前往后选取，能选就选。假设选出了 (x) 个点，那么这 (x) 个点一定是一个最小团覆盖，又因为最小团覆盖 $geq $ 最大独立集，所以求出来的点集是最大点独立集。
区间图：
区间图是弦图，区间图的一个完美消除序列是按照右端点排序，然后就可以用数据结构维护许多东西了，证明先咕咕了。