弦:连接环中不相邻的两个点的边。
弦图:一个无向图称为弦图当图中任意长度大于 3 的环都至少有一个弦。
团:满足 G 为关于 V 的完全图的图。
单纯点:设 N(v) 表示与点 v 相邻的点集。一个点称为单纯点当{v} + N(v) 的诱导子图为一个团。
完美消除序列:一个点的序列 (每个点出现且恰好出现一次) v1, v2, …, vn 满足 vi
在{vi, vi+1,…,vn}的诱导子图中为一个单纯点。
弦图充要条件:一个无向图是弦图当且仅当它有一个完美消除序列。
MCS 算法:从 n 到 1 依次给点标号,设 label[i] 表示第 i 个点与多少个已标号的点相邻,每次选择 label[i] 最大的未标号的点进行标号。
判断序列是否为完美消除序列:设{v[i+1],……,v[n]}中所有与 v[i] 相邻的点依次为
{v[j1],v[j2],……,v[jk]},只需要判断 v[j1] 是否与{v[j2],……,v[jk]}相邻即可。
时间复杂度:O(n+m)