///已知各点的度，推断是否为一个简单图#include
     
      #include
      
       #include
       
        using namespace std;int a[1010];bool cmp(int x,int y){    return x>y;}int main(){    int t,n,i,j;    scanf("%d",&t);    while(t--)    {        int flag=1;        scanf("%d",&n);        for (i=0; i
        
         =0)        {            int i = 1;            while (a[0]--)            {                --a[i++];            }            ++a[0];            sort(a,a+n,cmp);        }        if(a[n-1]<0)            printf("no\n");        else            printf("yes\n");    }    return 0;}
        
       
      
     

1。Havel-Hakimi定理主要用来判定一个给定的序列是否是可图的。

2。首先介绍一下度序列：若把图 G 全部顶点的度数排成一个序列 S。则称 S 为图 G 的度序列。

3，一个非负整数组成的有限序列假设是某个无向图的序列，则称该序列是可图的。

4，判定过程：（1）对当前数列排序，使其呈递减，（2）从S【2】開始对其后S【1】个数字-1，（3）一直循环直到当前序列出现负数（即不是可图的情况）或者当前序列全为0 （可图）时退出。

5，举例：序列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。在这一点上已经出现了负。因此，序列图不可。

版权声明：本文博客原创文章，博客，未经同意，不得转载。