哈韦尔-哈基米算法

哈韦尔-哈基米算法是一种图论算法，由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 .