基本介紹
- 中文名：Havel定理
- 外文名：Canisters theorem
- 特點：非負整數序列{dn}
- 實質：無向圖使得圖中各點的度
給定一個非負整數序列{dn}，若存在一個無向圖使得圖中各點的度與此序列一一對應，則稱此序列可圖化。進一步，若圖為簡單圖，則稱此序列可簡單圖化
可圖化的判定：d1+d2+……dn=0（mod 2）。關於具體圖的構造，我們可以簡單地把奇數度的點配對，剩下的全部搞成自環。
可簡單圖化的判定（Havel定理）：把序列排成不增序，即d1>=d2>=……>=dn，則d可簡單圖化若且唯若d’={d2-1，d3-1，……d(d1+1)-1， d(d1+2)，d(d1+3)，……dn}可簡單圖化。簡單的說，把d排序後，找出度最大的點（設度為d1），把它與度次大的d1個點之間連邊，然後這個點就可以不管了，一直繼續這個過程，直到建出完整的圖，或出現負度等明顯不合理的情況。
定理的證明：略
