Havel定理描述
給定一個非負整數序列{d1,d2,...dn},若存在一個無向圖使得圖中各點的度與此序列一一對應,則稱此序列可圖化。進一步,若圖為簡單圖,則稱此序列可簡單圖化。
可圖化的判定比較簡單:d1+d2+...dn=0(mod2)。關于具體圖的構造,我們可以簡單地把奇數度的點配對,剩下的全部搞成自環。
可簡單圖化的判定,有一個Havel定理,是說: 我們把序列排成不增序,即d1>=d2>=...>=dn,則d可簡單圖化當且僅當d'=(d2-1, d3-1, ... d(d1+1)-1, d(d1+2), d(d1+3), ... dn)可簡單圖化。這個定理寫起來麻煩,實際上就是說,我們把d排序以後,找出度最大的點(設度為d1),把它和度次大的d1個點之間連邊,然後這個點就可以不管了,一直繼續這個過程,直到建出完整的圖,或出現負度等明顯不合理的情況。
定理的簡單證明如下:
(<=)若d'可簡單圖化,我們隻需把原圖中的最大度點和d'中度最大的d1個點連邊即可,易得此圖必為簡單圖。
(=>)若d可簡單圖化,設得到的簡單圖為G。分兩種情況考慮:
(a)若G中存在邊(V1,V2), (V1,V3), ...(V1,V(d1+1)),則把這些邊除去得簡單圖G',于是d'可簡單圖化為G'
(b)若存在點Vi,Vj使得i<j, (V1,Vi)不在G中,但(V1,Vj)在G中。這時,因為di>=dj,必存在k使得(Vi, Vk)在G中但(Vj,Vk)不在G中。這時我們可以令GG=G-{(Vi,Vk),(V1,Vj)}+{(Vk,Vj),(V1,Vi)}。GG的度序列仍為d,我們又回到了情況(a)。
(以下示範轉自 “每天進步一點點” 部落格: http://sbp810050504.blog.51cto.com/2799422/883904)
Havel-Hakimi定理很容易了解: 三步走就可以了: 比如序列:4 7 7 3 3 3 2 1
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
值 | 4 | 7 | 7 | 3 | 3 | 3 | 2 | 1 |
第一步:把序列按降序排序。
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
值 | 7 | 7 | 4 | 3 | 3 | 3 | 2 | 1 |
第二步:删除第一個數7。序列變成
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
值 | 7 | 4 | 3 | 3 | 3 | 2 | 1 |
第三步:從頭開始,數7個數,也就是下标:[1,7]把[1,7]區間裡的值都減1 由于第一個數已經删除,那麼序列變成這樣的了:
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
值 | 6 | 3 | 2 | 2 | 2 | 1 |
然後: 重複第一步:排序。 重複第二步:删除第一個數6 重複第三步:從頭開始數6個數:也就是下标【1,6】,把區間【1,6】中的數删除。序列變成:
下标 | 1 | 2 | 3 | 4 | 5 | 6 |
值 | 2 | 1 | 1 | 1 | -1 |
由于已經出現了-1,而一個點的邊數(度)不可能為負數。是以,我們就可以判定序列無法構成一個圖,是以此序列是不可圖的。 下面再舉一個例子: 已經排序:
5 | 4 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1. |
删除第一個數5:
4 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1. |
把前面5個數減1:
3 | 2 | 2 | 1 | 1 | 2 | 1 | 1 | 1. |
排序:
3 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1. |
删除第一個數3:
2 | 2 | 2 | 1 | 1 | 1 | 1 | 1. |
把前面3個數減1:
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1. |
排序:
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1. |
删除第一個數1:
1 | 1 | 1 | 1 | 1 | 1 | 1. |
把前面1個數減1:
1 | 1 | 1 | 1 | 1 | 1. |
排序:
1 | 1 | 1 | 1 | 1 | 1 |
删除第一個數1:
1 | 1 | 1 | 1 | 1 |
把前面1個數減1:
1 | 1 | 1 | 1 |
排序:
1 | 1 | 1 | 1 |
依此類推:到最後隻剩下:
由此判斷該序列是可圖的。
核心代碼:
bool Havel_Hakimi(){
for(int i=0; i<n-1; ++i){
sort(arr+i,arr+n,greater<int>());
if(i+arr[i] >= n) return false;
for(int j=i+1; j<=i+arr[i] ; ++j){
--arr[j];
if(arr[j] < 0) return false;
}
}
if(arr[n-1]!=0) return false;
return true;
}
關于這個定理應用的題目:
1. poj 1659 :
http://poj.org/problem?id=1659
2. UVa 10720 - Graph Construction:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1661