Havel–Hakimi算法

Havel–Hakimi算法是一种图论算法，由Havel (1955)与Hakimi (1962)先后发表，解决了可简单图化问题。这个问题是指给定一串有限多个非负整数组成的序列，是否存在一个简单图使得其度数列恰为这个序列。我们称满足条件的序列为可简单图化的。如果一个序列可简单图化，这个算法能够构造一个特解；否则算法指出序列不可简单图化。该算法是一个递归算法。

算法

Havel–Hakimi算法基于以下定理。
令为有限多个非负整数组成的非递增序列。可简单图化当且仅当有穷序列只含有非负整数且是可简单图化的。
如果给定的序列 是可简单图化的，那么算法最多运行次赋值。注意每次赋值后可能需要重新对序列排序。当全部为零时，算法停止。在每一步中，如果序列可简单图化，就从向各引出一条边，即，然后令约化为。如果在任何一步中，序列无法约化为非负整数序列，算法就给出最开始的不可简单图化的结论。