哈韋爾-哈基米算法

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

算法

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

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

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

參見 

• Erdős–Gallai定理（英語：Erdős–Gallai theorem）

參考文獻 

• 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（英語：Society for Industrial and Applied Mathematics）, 1962, 10: 496–506, MR 0148049.