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

两个概念

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代码如下：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #define MAXN 10

 typedef struct Company

 {

   int data;

   int no;

 }Company;

 Company x[MAXN];

 int map[MAXN][MAXN];

 int Compare(const void *elem1, const void *elem2)

 {

   Company *p1 = (Company*)elem1;

   Company *p2 = (Company*)elem2;

 //  if (p1->data == p2->data)

 //  {

 //    return p1->no - p2->no;

 //  }

   return p2->data - p1->data;

 }

 int main()

 {

   int T, N;

   scanf("%d", &T);

   while(T--)

   {

     scanf("%d", &N);

     memset(map, , sizeof(map));

     int flag = ;

     for (int i = ; i < N; ++i)

     {

       scanf("%d", &x[i].data);

       x[i].no = i;

     }

     qsort(x, N, sizeof(Company), Compare);

     while(!flag && x[].data)

     {

       int start = x[].data;

       for (int i = ; i < start+; ++i)

       {

         x[i].data--;

         if (x[i].data < )

         {

           flag = ;

           break;

         }

         map[x[].no][x[i].no] = ;

         map[x[i].no][x[].no] = ;

       }

       x[].data = ;

       qsort(x, N, sizeof(Company), Compare);

     }

     if (flag)

     {

       printf("NO\n");

     }else

     {

       printf("YES\n");

       for (int i = ; i < N; ++i)

       {

         for (int j = ; j < N; ++j)

         {

           printf(j ==  ? "%d" : " %d", map[i][j]);

         }

         printf("\n");

       }

     }

     if (T)

     {

       printf("\n");

     }

   }

   return ;

 }

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

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

思路源自以下代码：

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 struct node

 {

     int num,e;

 }x[];

 bool map[][];

 int cmp(node a,node b)

 {

     if(a.num==b.num)

         return a.e<b.e;

     return a.num>b.num;

 }

 int judge(int n)

 {

     int i,num,tmp;

     while(){

         sort(x+,x+n+,cmp);

         if(!x[].num)

             return ;//数组全为 0 的情况退出

         for(i=;i<=x[].num+;i++){

             if(x[i].num>){

                 x[i].num--;

                 map[x[].e][x[i].e]=map[x[i].e][x[].e]=;

             }

             else

                 return ;

         }

         x[].num=;

     }

 }

 int main()

 {

     int n,t,i,j;

     bool flag;

     scanf("%d",&t);

     while(t--){

         scanf("%d",&n);

         for(i=;i<=n;i++){

             scanf("%d",&x[i].num);

             x[i].e=i;

         }

         memset(map,,sizeof(map));

         flag=judge(n);

         if(flag){

             printf("YES/n");

             for(i=;i<=n;i++){

                 for(j=;j<=n;j++)

                     printf(j==?"%d":" %d",map[i][j]);

                 printf("/n");

             }

         }

         else

             printf("NO/n");

         if(t)

             printf("/n");

     }

     return ;

 }

巴特西

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

最新文章

热门文章