弦(chord)：连接环中不相邻的两个点的边。

弦图(chordalgraph)：一个无向图称为弦图当且仅当图中任意长度大于3的环都至少有一个弦。

单纯点(simplicialvertex)：设N(v)表示与点v相邻的点集。一个点称为单纯点当{v} + N(v)的诱导子图为一个团。

完美消除序列(perfect elimination ordering)：这是一个序列{v[i]}，它满足v[i]在{v[i..n]}的诱导子图中为单纯点。

弦图的判定：存在完美消除序列的图为弦图。可以用MCS最大势算法求出完美消除序列。

 

最大势算法 Maximum Cardinality Search

从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。

设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。

用n个vector来保存label为i的是哪些点，可以使复杂度达到O(n+m)。

 

弦图上的问题：

用最少的颜色给每个点染色使得相邻的点染的颜色不同：完美消除序列从后往前依次给每个点染上可以染的最小的颜色。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define MAX(a,b) a>b?a:b 6 #define MIN(a,b) a
          

vec[N];15 void add(int u,int v)16 {17 e[++ee]=v;nex[ee]=head[u];head[u]=ee;18 }19 int main()20 {21 scanf("%d%d",&n,&m);22 rep(i,m)23 {24 scanf("%d%d",&u,&v);25 add(u,v);26 add(v,u);27 }28 best=0;29 for (i=1;i<=n;i++)30 vec[0].push_back(i);31 for (i=n;i>=1;i--)32 {33 while (1)34 {35 u=vec[best].back();36 if (vis[u])37 vec[best].pop_back();38 else39 break;40 while (vec[best].size()==0)41 best--;42 }43 a[i]=u;44 vis[u]=1;45 for (j=head[u];j>0;j=nex[j])46 {47 lab[e[j]]++;48 best=MAX(lab[e[j]],best);49 vec[lab[e[j]]].push_back(e[j]);50 }51 }52 //for (i=1;i<=n;i++)printf("lbz %d\n",a[i]);53 54 for (i=n;i>=1;i--)55 {56 for (j=head[a[i]];j>0;j=nex[j])57 {58 b[c[e[j]]]=i;59 } 60 rep(j,n)61 if (b[j]!=i)62 {63 c[a[i]]=j;64 ans=MAX(ans,c[a[i]]);65 break;66 }67 }68 printf("%d\n",ans);69 return 0;70 71 }