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;  
}