Havel-Hakimi定理

作用是:判断一个序列是否可图

Havel定理描述**给定一个非负整数序列{d1,d2,...dn},若存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化。进一步,若图为简单图,则称此序列可简单图化。

可图化的判定比较简单:d1+d2+...dn=0(mod2)。关于具体图的构造,我们可以简单地把奇数度的点配对,剩下的全部搞成自环。

可简单图化的判定,有一个Havel定理,是说: 我们把序列排成不增序,即d1>=d2>=...>=dn,则d可简单图化当且仅当d'=(d2-1, d3-1, ... d(d1+1)-1, d(d1+2), d(d1+3), ... dn)可简单图化。这个定理写起来麻烦,实际上就是说,我们把d排序以后,找出度最大的点(设度为d1),把它和度次大的d1个点之间连边,然后这个点就可以不管了,一直继续这个过程,直到建出完整的图,或出现负度等明显不合理的情况。

举例:序列S:7,7,4,3,3,3,2,1 删除序列S的首项 7 ,对其后的7项每项减1,得到:6,3,2,2,2,1,0,继续删除序列的首项6,对其后的6项每项减1,得到:2,1,1,1,0,-1,到这一步出现了负数,因此该序列是不可图的

我解释一下意思:排好序后为d1,d2,d3,d4....dn,设度数最大的为v1,将它与度数次大的前d1个顶点连边,然后这个顶点就可以不管了,及在序列中删除首项d1,并把后面的d1个度数减1,依次下去,知道所有的为0就是可图的,出现负数,就一定不可图..

POJ1659 Frogs' Neighborhood(Havel定理)

首先我们对这个序列进行排序,然后找出最大的度数n,然后在这个排好序的序列中对接下来的n个数进行减一,如果出现两种情况就证明这个序列不可图,否则就就在邻接矩阵中把这两个点连起来

①某次对剩下的序列排序后,最大的度数超过了剩下的顶点数

②对最大的度数后面的n个度数进行减1后,出现了负数

如果出现了这两种情况,那么这个序列不可图

struct node  
{  
    int degree,id;//顶点的度数和标号  
} v[20];  
int map[20][20];  
bool cmp(node a,node b)  
{  
    return a.degree>b.degree;  
}  
int main()  
{  
    int t,n,flag;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d",&n);  
        for(int i=0; i<n; i++)  
        {  
            scanf("%d",&v[i].degree);  
            v[i].id=i;//记录顶点的编号  
        }  
        mem(map,0);  
        flag=1;  
        for(int k=0; k<n; k++)  
        {  
            sort(v+k,v+n,cmp);//从第k位开始,对整个数组排序  
            int i=v[k].id;//当前要连的顶点的编号  
            int d1=v[k].degree;//记录当前这个节点的度数  
            if(d1>n-k-1)//当当前节点的度数比剩余的顶点数要大的时候,则不存在相连的关系  
                flag=0;  
            for(int r=1; r<=d1&&flag; r++)//从当前点开始给后面的度数减一  
            {  
                int j=v[k+r].id;//当前要连的顶点的编号  
                if(v[k+r].degree<=0)//出现负值代表不存在相连的关系  
                    flag=0;  
                v[k+r].degree--;  
                map[i][j]=map[j][i]=1;  
            }  
        }  
        if(flag)  
        {  
            puts("YES");  
            for(int i=0; i<n; i++)  
            {  
                for(int j=0; j<n; j++)  
                {  
                    if(j)printf(" ");  
                    printf("%d",map[i][j]);  
                }  
                puts("");  
            }  
        }  
        else  
            puts("NO");  
        if(t)  
            puts("");  
    }  
    return 0;  
}

results matching ""

    No results matching ""