Havel–Hakimi算法

Havel-Hakimi算法是圖論中解決圖形實現問題的算法。 也就是說，它回答了以下問題：給定一個非負整數的有限列表，是否有一個簡單的圖形，使得它的度序列恰好是這個列表。 這裡，“度序列”是一個數字列表，對於圖的每個頂點，它表示它有多少個鄰居。 對於肯定答案，整數列表稱為圖形。 該算法構造一個特殊的解決方案，如果存在或證明一個人找不到肯定的答案。 這種結構基於遞歸算法。 該算法由Havel（1955）出版，後來由Hakimi（1962）出版。

基本介紹

• 中文名：Havel–Hakimi算法
• 外文名：Havel–Hakimi algorithm

介紹

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，到這一步出現了負數，因此該序列是不可簡單圖化的。

算法

Havel–Hakimi算法基於以下定理。

令 為有限多個非負整數組成的非遞增序列。 可簡單圖化若且唯若有窮序列只含有非負整數且是可簡單圖化的。

如果給定的序列是可簡單圖化的，那么算法最多運行次賦值。注意每次賦值後可能需要重新對序列排序。當全部為零時，算法停止。在每一步中，如果序列可簡單圖化，就從向,各引出一條邊，即{,},{,},{,}，然後令約化為。如果在任何一步中，序列無法約化為非負整數序列，算法就給出最開始的不可簡單圖化的結論。

代碼

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std;  
struct node  
{  
    int num,e;  
}x[15];  
bool map[15][15];  
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(1){  
        sort(x+1,x+n+1,cmp);  
        if(!x[1].num)  
            return 1;//數組全為 0 的情況退出  
        for(i=2;i<=x[1].num+1;i++){  
            if(x[i].num>0){  
                x[i].num--;  
                map[x[1].e][x[i].e]=map[x[i].e][x[1].e]=1;  
            }  
            else  
                return 0;  
        }  
        x[1].num=0;  
    }  
}  
int main()  
{  
    int n,t,i,j;  
    bool flag;  
    scanf("%d",&t);  
    while(t--){   
        scanf("%d",&n);  
        for(i=1;i<=n;i++){  
            scanf("%d",&x[i].num);  
            x[i].e=i;  
        }  
        memset(map,0,sizeof(map));  
        flag=judge(n);  
  
        if(flag){  
            printf("YES/n");  
            for(i=1;i<=n;i++){  
                for(j=1;j<=n;j++)  
                    printf(j==1?"%d":" %d",map[i][j]);  
                printf("/n");  
            }  
        }  
        else  
            printf("NO/n");  
        if(t)  
            printf("/n");  
    }  
    return 0;  
}