CDQ的论文
以下纯属复制论文，避免以后再看一次
一些概念
子图
点集和边集都是原图的子集的图
诱导子图
是子图，不含其它边
团
子图，并且是完全图
极大团
不是任何一个团的子图
最大团
点数最多的团
最小染色
用最少的颜色染给每个点，使相邻点不同色
最大独立集
不相邻的最大点集
最小团覆盖
最少的团覆盖所有点
显然的结论
团数(le)色数
最大独立集(le)最小团覆盖
弦
连接环内两个不相邻的点的边
弦图
任意大于三的环都至少有一条弦
结论1
弦图的诱导子图是弦图
单纯点
设(N(v))为(v)相邻的点集
(v)为单纯点当且仅当({v}+N(v))的诱导子图为团
结论2
任何一个弦图至少一个单纯点
不是完全图的弦图至少两个
完美消除序列
每个点正好出现一次的序列({v_1, v_2, ..., v_n})
满足(v_i)在({v_i, v_{i+1}, ..., v_n})的诱导子图中为单纯点
结论3
一个无向图为弦图当且仅当它有一个完美消除序列
证明
略看论文
结论5
团数(=)色数
最大独立集(=)最小团覆盖
证明
略看论文
求解
求完美消除序列
不想学什么(Lex BFS)的方法，自己看论文
还是(MCS)最大势算法好：
按(n...1)的顺序给点标号
标号为(i)的点为完美消除序列的第(i)个
设(label[i])表示与多少个已经标号的点相邻
每次找(label)最大的点标号
复杂度(O(n+m))
判断一个序列是否为完美消除序列
设在(v_i,v_{i+1}..v_n)中，与(v_i)相邻的点依次为(v_{j1}...v_{jk})
只需要判断(v_{j1})是否与(v_{j2}..v_{jk})相邻即可
复杂度(O(n+m))
最少的颜色给所有点染色&团数
完美消除序列逆序，贪心
每次给一个点染色可以染的最小的颜色
最大独立集&最小团覆盖
完美消除序列中，贪心，能选就选