首页 > 代码库 > 可图性判定--Havel-Hakimi定理

可图性判定--Havel-Hakimi定理

2024-07-12 09:21:30   225人阅读

两个概念

1、度序列

　　若把图G所有顶点的度数排成一个序列S，则称S为图G的度序列。

2、序列是可图的

　　一个非负整数组成的序列如果是某个无向图的度序列，则称该序列是可图的。

 

 

 

Havel-Hakimi定理

 

由非负整数组成的非增序列S：d1, d2 ,..., dn (n≥2,d1≥1)是可图的，当且仅当序列S1：d2-1,d3-1,...,dd1+1-1,dd1+2,...,dn是可图的。其中，序列S1中有n-1个非负整数，S序列中d1后的前d1个度数(即d2~dd1+1)减1后构成S1中的前d1个数。

 

 

 

应用：POJ 1659 Frogs‘ Neighborhood

http://poj.org/problem?id=1659

 

贴上一个博客

http://blog.csdn.net/monkey_little/article/details/6358601

 

对于该题目中的第一个序列，分析如下：

具体操作时候，每次都把排序好的序列第一个元素处理完以后就置为0，加入到队列的最后。若是最后元素全为0，则该序列是可图的。若在中间出现某个元素减一之后变为负的，则说明此序列是不可图的。

我的AC代码如下：

 1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #define MAXN 10 5 typedef struct Company 6 { 7   int data; 8   int no; 9 }Company;10 Company x[MAXN];11 int map[MAXN][MAXN];12 int Compare(const void *elem1, const void *elem2)13 {14   Company *p1 = (Company*)elem1;15   Company *p2 = (Company*)elem2;16 //  if (p1->data =http://www.mamicode.com/= p2->data)>17 //  {18 //    return p1->no - p2->no;19 //  }20   return p2->data - p1->data;21 }22 int main()23 {24   int T, N;25   scanf("%d", &T);26   while(T--)27   {28     scanf("%d", &N);29     memset(map, 0, sizeof(map));30     int flag = 0;31     for (int i = 0; i < N; ++i)32     {33       scanf("%d", &x[i].data);34       x[i].no = i;35     }36     qsort(x, N, sizeof(Company), Compare);37     while(!flag && x[0].data)38     {39       int start = x[0].data;40       for (int i = 1; i < start+1; ++i)41       {42         x[i].data--;43         if (x[i].data < 0)44         {45           flag = 1;46           break;47         }48         map[x[0].no][x[i].no] = 1;49         map[x[i].no][x[0].no] = 1;50       }51       x[0].data = http://www.mamicode.com/0;52       qsort(x, N, sizeof(Company), Compare);53     }54     if (flag)55     {56       printf("NO\n");57     }else58     {59       printf("YES\n");60       for (int i = 0; i < N; ++i)61       {62         for (int j = 0; j < N; ++j)63         {64           printf(j == 0 ? "%d" : " %d", map[i][j]);65         }66         printf("\n");67       }68     }69     if (T)70     {71       printf("\n");72     }73   }74   return 0;75 }

x.no这个属性用来记录每个输入数据的输入时的编号次序，以用来在map[][]数组填充1时用，否则不知道该x[?][?] = 1；

flag是一个标志位，若中间有负数出现，就改变其值

 

思路源自以下代码：

 1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 struct node 6 { 7     int num,e; 8 }x[15]; 9 bool map[15][15];10 int cmp(node a,node b)11 {12     if(a.num==b.num)13         return a.e<b.e;14     return a.num>b.num;15 }16 int judge(int n)17 {18     int i,num,tmp;19     while(1){20         sort(x+1,x+n+1,cmp);21         if(!x[1].num)22             return 1;//数组全为 0 的情况退出23         for(i=2;i<=x[1].num+1;i++){24             if(x[i].num>0){25                 x[i].num--;26                 map[x[1].e][x[i].e]=map[x[i].e][x[1].e]=1;27             }28             else29                 return 0;30         }31         x[1].num=0;32     }33 }34 int main()35 {36     int n,t,i,j;37     bool flag;38     scanf("%d",&t);39     while(t--){ 40         scanf("%d",&n);41         for(i=1;i<=n;i++){42             scanf("%d",&x[i].num);43             x[i].e=i;44         }45         memset(map,0,sizeof(map));46         flag=judge(n);47 48         if(flag){49             printf("YES/n");50             for(i=1;i<=n;i++){51                 for(j=1;j<=n;j++)52                     printf(j==1?"%d":" %d",map[i][j]);53                 printf("/n");54             }55         }56         else57             printf("NO/n");58         if(t)59             printf("/n");60     }61     return 0;62 }
View Code


联系
我们