弦图-学习笔记

· · 个人记录

被板板安利了一发就来学弦图啦！orz zsy

一些定义：

弦：连接换上两个不相邻节点的边称为弦。

弦图：若一张无向图中任意一个大小超过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个队列，类似莫队求区间众数一样搞。

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大的点是否有边即可。

    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)}为最小团覆盖