弦图算法
导出子图
图$G=(V,E)$的导出子图$G'=(V',E')$，需要满足，$V'\subset V$，且$E'=\left\{(u,v)|(u,v)\in E \land u\in V'\land v\in V'\right\}$。
团
一个无向图中的一个导出子图如果是完全图，则称改导出子图为团。
最大独立集
最大独立集是指V的一个子集，使得其中元素两两之间没有边存在。
最小团覆盖
最小团覆盖是指将V切分为尽可能少的不相交集合。
弦
环上连接两个环上不相连的顶点的边称为弦。
弦图
一个无向图中任意长度大于3的环都至少有一个弦，这样的无向图称为弦图。
弦图的导出子图一定也是弦图
单纯点
设$N(v)$表示与点$v$相邻的点集，一个点称为单纯点当$\left\{v\right\}+N(v)$的导出子图是一个团。
任何一个弦图都至少有一个单纯点
完美消除序列
对于无向图$G=(V,E)$，设$n=|V|$。图的完美消除序列为$\left\{v_1,v_2,\ldots ,v_n\right\}$。满足对于任意$i$，$v_i$为$\left\{v_i,v_{i+1},\ldots ,v_n\right\}$的导出子图的一个单纯点。
一个无向图是弦图当且仅当图存在完美消除序列
最大势算法
最大势算法可以以$O(|V|+|E|)$的时间复杂度判断一个图是否是弦图，如果是还能同时找到图的完美消除序列。
算法原理不清楚，这里直接将一下算法怎么实现。
n = |V|;
m = |E|;
A = empty-set
B = V
for(i = n - 1; i >= 0; i--){
在B中找到x，满足与x相邻的元素组成的集合N(x)与V的交集大小最大
将x标记为i
将x从B移到A
}
for(i = 0; i < n; i++){
记x为被标记为i的结点
设C为与x相邻且编号大于i的所有顶点组成的集合
设y为集合C中编号最小的顶点
如果C中存在某个顶点z，z不是y，且z与y没有边，那么这个图就不是弦图，退出
}
这个图是弦图，并找到了完美消除序列
弦图点染色问题
要计算弦图的染色数，只需要逆序遍历完美消除序列，为每个顶点染色尽可能小的颜色即可。
弦图最大独立集
弦图中的最大独立集可以通过按序遍历完美消除序列，并以贪心的方式选取尽可能多的元素。
set = 空集
for(i = 0; i < n; i++){
记x表示被标记为i的顶点;
如果x某个邻接的顶点属于set，则跳过，否则将x加入到set中
}
return set
弦图最小团覆盖
设弦图最大独立集为$\left\{v_1, v_2, \ldots, v_k\right\}$，那么弦图的最小团覆盖为$\left\{v_1+N(v_1), v_2+N(v_2), \ldots, v_k + N(v_k)\right\}$。