EG定理 

还有一篇博客讲的havel定理

另有havel定理

havel定理是基于贪心构造的

每次顶点按度大小从大到小排序，去除度最大的点Vi，依次和度较大的那些顶点Vj链接，同时减去Vj的度。连接完之后就不再考虑Vi了，剩下的点再次排序去找度最大的去连接。

如何判断无解呢，若某次选出的Vi的度比剩下的顶点还多，则无解；若某次的度Vj减成了负数，则无解

此定理证明啥的 还是略了 本人太弱，并不懂，时间复杂度是O(n^2 logn),可以通过优先队列或者计数排序优化成O(n^2) 然而还是比EG定理慢

NEU 1429

EG定理代码

O(nlogn)

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N = 1e4 + 10;int deg[N],sumd[N],sum[N];bool cmp(int x,int y){
    return x>y;}bool check(int n){    memset(sumd,0,sizeof(sumd));    memset(sum,0,sizeof(sum));    for(int i = 1; i <= n; i++) sumd[i] = sumd[i-1] + deg[i];    if(sumd[n]&1) return false;    for(int r = 1; r
          
           i*(i-1) + sum[i]) return false;    }    return true;}int main(){    int n;    while(~scanf("%d",&n))    {        for(int i = 1; i<=n; i++) scanf("%d",°[i]);        sort(deg+1,deg+n+1,cmp);        if(check(n)) puts("YES");        else puts("NO");    }    return 0;}
          
         
        
       
      

havel定理代码

#include
      
       #include
       
        using namespace std;const int N = 1e4 + 10;int deg[N];bool cmp(int x,int y){    return x > y;}bool check(int n){    for(int i = 0 ; i < n ; i++)    {        sort(deg+i,deg+n,cmp);        if(i + deg[i]>=n) return false;        for(int j = i + 1; j<=i+deg[i]; j++)        {            if(--deg[j] < 0 ) return false;        }    }    if(deg[n-1]!=0) return false;    return true;}int main(){  int n;  while(~scanf("%d",&n))  {   for(int i = 0;i
       
      

havel定理相对于EG定理 时间复杂度是没有优势的

但是其对于EG定理，具有明显的构造性

给出两道题目

POJ_1659: .

UVa_10720_Graph_construction.