弦图-学习笔记

被板板安利了一发就来学弦图啦！[orz zsy](https://www.cnblogs.com/zhoushuyu/p/8716935.html) 一些定义： 弦：连接换上两个不相邻节点的边称为弦。 弦图：若一张无向图中任意一个大小超过3的环都存在至少一条弦，那么这样的图称为弦图。**就是说所有的环都被“三角剖分”了** 单纯点：与其相邻的点集的诱导子图（把所有的边都连上后生成的图）是一个团（任两个点之间都有边）。 完美消除序列： 一个点的排列$v_1,v_2...v_n$满足$v_i$在$v_i,v_{i+1}...v_n$的诱导子图中为一个单纯点。 ## 弦图的判定 ### 一个无向图是弦图当且仅当它有一个完美消除序列 用最大势算法(Maximum Cardinality Search)可以在$O(n+m)$的时间内求出一个消除序列的反序。 简单的说，先初始化每个点的lab为0. 第i次取出lab最大的点作为序列中倒数第i个点。同时把与i相邻的点的lab+1。 具体实现可以开n个队列，类似莫队求区间众数一样搞。 ```cpp void mcs() { int mx=0; for(ri i=1; i<=n; ++i) q[0].push(i); for(ri i=n; i>=1; --i) { while(!q[mx].empty()&&rk[q[mx].front()]) q[mx].pop(); if(q[mx].empty()) {++i,--mx; continue;} rk[sa[i]=q[mx].front()]=i,q[mx].pop(); for(solid v:E[sa[i]]) if(!rk[v]) { ++lab[v],q[lab[v]].push(v); ckmax(mx,lab[v]); } } } ``` ### 验证“完美消除序列” 我们只需要找出与x相邻的排名比x大的**排名最小的点**，看看它和其他与x相邻的比x大的点是否有边即可。 ```cpp for(ri i=n; i>=1; --i) { static int st[N]; int tp=0,mn=n; for(ri j=head[sa[i]]; j; j=nx[j]) if(rk[v[j]]>i) st[++tp]=v[j],ckmin(mn,rk[v[j]]); mn=sa[mn]; for(ri i=1; i<=tp; ++i) if(st[i]!=mn&&!g[mn][st[i]]) { puts("Imperfect"); return 0; } } puts("Perfect"); ``` ------------ 插入一些性质： 团数=最大团大小，色数=最小颜色数使得相邻点的颜色不同。 **团数 ≤ 色数**（其实**团数=色数**） **最大独立集数 ≤ 最小团覆盖数** ------- ## 极大团 设$N(v)$表示与v相邻且排名大于v的点集。则弦图的极大团一定是$v+N(v)$的形式。 定义$nxt(v)$为$N(v)$中排名最小的点。 如果$v+N(v)$是极大团，那么对于所有$nxt[w]=v$的w，$|N(v)|+1>N(w)$ ## 弦图的点染色问题 HNOI2008 神奇的国度。 完美消除序列从后往前给每个点染色， 给每个点染上可以染的最小颜色。 等于最小团数，也就是$\max_{i=1}^{n}label[i]+1$  ## 最大独立集 消除序列从后往前贪心。 ## 最小团覆盖 设最大独立集为{p1 , p2 , …, pt}，则{p1∪N(p1), …, pt∪N(pt)}为最小团覆盖