哈韋爾-哈基米算法

哈韋爾-哈基米算法是一種圖論算法，由Havel (1955)與Hakimi (1962)先後發表，解決了可簡單圖化問題。這個問題是指給定一串有限多個非負整數組成的序列，是否存在一個簡單圖使得其度數列恰為這個序列。我們稱滿足條件的序列為可簡單圖化的。如果一個序列可簡單圖化，這個算法能夠構造一個特解；否則算法指出序列不可簡單圖化。該算法是一個遞歸算法。

算法

哈韋爾-哈基米算法基於以下定理。

令$S=(d_{1},\dots ,d_{n})$為有限多個非負整數組成的非遞增序列。$S$可簡單圖化當且僅當有窮序列$S'=(d_{2}-1,d_{3}-1,\dots ,d_{d_{1}+1}-1,d_{d_{1}+2},\dots ,d_{n})$只含有非負整數且是可簡單圖化的。

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

參見 

• Erdős–Gallai定理

參考文獻 

• Havel, Václav, A remark on the existence of finite graphs, Časopis pro pěstování matematiky, 1955, 80: 477–480 [2017-11-02], （原始內容存檔於2017-07-29） （捷克語） 
• Hakimi, S. L., On realizability of a set of integers as degrees of the vertices of a linear graph. I, Journal of the Society for Industrial and Applied Mathematics, 1962, 10: 496–506, MR 0148049 .