CDQ God's Speech: Chord Diagram and Interval Diagram-Chen Danqi

chart

Fig. G(V,E)

Basic concepts

Subgraph

G'(V'E') is a subgraph of graph G(V,E) if and only if V'< V,E'< E

Induced subgraph

G'(V'E') is a subgraph of graph G(V,E) if and only if V'< V,E'={U < V', V < V'(u,v)< E'}

group

G'(V'E') is a subgraph of graph G(V,E), and G'(V'E') is a complete graph about V'.

G'(V'E') is a group and not a subset of other groups.

G'(V'E') is a large group with the largest number of points. In particular, note that the vertex set size of the largest cluster of graph G is_(G)

Minimum staining

Use the smallest number of colors to dye the dots and the adjacent dots have different colors. The smallest number of colours (colour) is lambda (G).

Maximum Independent Set

Graph G'is a subset of G and is somewhat non-adjacent in G'. Graph G' with the largest vertex set size is the largest independent set of graph G. Note as alpha (G)

Minimum Cluster Coverage

Cover the vertices of all graphs G with a minimum number of cliques. Note x (G)

Two conclusions

1.w(G)≤λ(G)
Because the colours in the largest group must be different from each other.
2.α(G)≤χ(G)
Take at most one point in each regiment.

Chordal graph

concept

string

The edges of two points that are not adjacent to each other in the connecting ring.

Chordal graph

An undirected graph is called a chord graph when a ring of any length greater than 3 in the graph has at least one chord.

Two conclusions

1. Each induced subgraph of a chord graph must be a chord graph.
2. Any induced subgraph of a chord graph is different from Cn(n>3).

Decision of Chord Graph

bzoj1242:Fishing net
Give an undirected graph to determine whether it is a chord graph or not.

Simple point

Let N (v) denote the set of points adjacent to point v. A point is called a simple point when the induced subgraph of v+N(v) is a clique.

Perfect elimination sequence

A sequence of points (each point appears exactly once) v1,v2,... vn satisfies VI in vi,vi+1,... The induced subgraph of vn is a simple point.

algorithm

1. Naive algorithm
The simplest algorithm:
Each time a simple point v is found and added to the perfect elimination sequence.
Delete v and related edges from the graph.
Repeat the above process until all points are deleted (the graph is a chord graph, resulting in a perfect sequence) or there is no simple point v (the graph is not a chord graph).
Time complexity: O(n4)

2.
Lexicographic BFS
The order from n to 1 is punctuated.
Each point maintains a list record of the labeled points adjacent to it, and the labels in the list are sorted from large to small.
Select the unlabeled punctuation with the largest list dictionary order each time.
Time complexity O(n+m).

3,
Maximum Cardinality Search
The order from n to 1 is marked with dots (the dots labeled i appear at the first in the perfect elimination sequence).
Let label[i] denote that the first point is adjacent to several labeled points, and each time the label[i] largest unlabeled point is selected for labeling.

Determine whether an extracted sequence is a perfect elimination sequence? (If the original graph is a chord graph, it must be, but here is the decision.)

A simple algorithm
Judging vi+1,... Whether all points adjacent to vi in vn form a group or not.
Time complexity: O (deg(v)2)

Optimized algorithm
Set vi+1,... In vn, all points adjacent to VI are vj1,... vjk.
Just judge whether vj1 and vj2,... The vjk is adjacent to each other.
Time complexity: O(m+n)

Code for bzoj1242:

#include<bits/stdc++.h>
using namespace std;
struct IO
{
    streambuf *ib,*ob;
    int buf[50];
    inline void init()
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);cout.tie(NULL);
        ib=cin.rdbuf();ob=cout.rdbuf();
    }
    inline int read()
    {
        char ch=ib->sbumpc();int i=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=ib->sbumpc();}
        while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=ib->sbumpc();}
        return i*f;
    }
    inline void W(int x)
    {
        if(!x){ob->sputc('0');return;}
        if(x<0){ob->sputc('-');x=-x;}
        while(x)buf[++buf[0]]=x%10,x/=10;
        while(buf[0])ob->sputc(buf[buf[0]--]+'0');
    }
    inline void W(string x)
    {
        int len=x.length();
        for(int i=0;i<len;i++)ob->sputc(x[i]);
    }
}io;
const int Maxn=1e3+50;
int n,m,que[Maxn],vis[Maxn],cnt[Maxn],pos[Maxn];
vector<int>edge[Maxn];
bool IsConnected[Maxn][Maxn];
struct LIST
{
    int id;
    LIST *pre,*suf;
    LIST():pre(NULL),suf(NULL),id(0){}
    inline void Push(LIST *now)
    {
        now->pre=this;
        now->suf=this->suf;
        if(this->suf)this->suf->pre=now;
        this->suf=now;
    }
    inline void del()
    {
        this->pre->suf=this->suf;
        if(this->suf)this->suf->pre=this->pre;
    }
}List[Maxn],Pool[Maxn];
inline void msc()
{
    for(int i=1;i<=n;i++)List[0].Push(&Pool[i]),Pool[i].id=i,IsConnected[i][i]=true;
    int maxc=0;
    for(int i=1;i<=n;i++)
    {
        while(List[maxc+1].suf)maxc++;
        while(!List[maxc].suf)maxc--;
        int now=List[maxc].suf->id;
        List[maxc].suf->del();
        que[n-i+1]=now;vis[now]=1;pos[now]=n-i+1;
        for(int e=edge[now].size()-1;e>=0;e--)
        {
            int v=edge[now][e];
            if(vis[v])continue;
            Pool[v].del();
            List[++cnt[v]].Push(&Pool[v]);
        }
    }
}
inline bool check()
{
    memset(vis,0,sizeof(vis));
    static int to[Maxn],cnt,mn;
    for(int i=n;i>=1;i--)
    {
        int now=que[i];cnt=0;mn=n;vis[now]=1;
        for(int e=edge[now].size()-1;e>=0;e--)
        {
            int v=edge[now][e];
            if(vis[v])mn=min(mn,pos[v]),to[++cnt]=v;
        }
        if(mn==n)continue;
        for(int i=1;i<=cnt;i++)if(!IsConnected[que[mn]][to[i]])return false;
    }
    return true;
}
int main()
{
    io.init();n=io.read();m=io.read();
    for(int i=1;i<=m;i++)
    {
        int x=io.read(),y=io.read();
        IsConnected[x][y]=IsConnected[y][x]=true;
        edge[x].push_back(y);edge[y].push_back(x);
    }
    msc();
    if(check())io.W("Perfect");
    else io.W("Imperfect");
}