弦图算法
导出子图
图G=(V,E)的导出子图G′=(V′,E′)，需要满足，V′⊂V，且E′={(u,v)|(u,v)∈E∧u∈V′∧v∈V′}。
团
一个无向图中的一个导出子图如果是完全图，则称改导出子图为团。
最大独立集
最大独立集是指V的一个子集，使得其中元素两两之间没有边存在。
最小团覆盖
最小团覆盖是指将V切分为尽可能少的不相交集合。
弦
环上连接两个环上不相连的顶点的边称为弦。
弦图
一个无向图中任意长度大于3的环都至少有一个弦，这样的无向图称为弦图。
弦图的导出子图一定也是弦图
单纯点
设N(v)表示与点v相邻的点集，一个点称为单纯点当{v}+N(v)的导出子图是一个团。
任何一个弦图都至少有一个单纯点
完美消除序列
对于无向图G=(V,E)，设n=|V|。图的完美消除序列为{v1,v2,…,vn}。满足对于任意i，vi为{vi,vi+1,…,vn}的导出子图的一个单纯点。
一个无向图是弦图当且仅当图存在完美消除序列
最大势算法
最大势算法可以以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
弦图最小团覆盖
设弦图最大独立集为{v1,v2,…,vk}，那么弦图的最小团覆盖为{v1+N(v1),v2+N(v2),…,vk+N(vk)}。