哈韦尔-哈基米算法

(重定向自Havel–Hakimi算法

哈韦尔-哈基米算法是一种图论算法,由Havel (1955)Hakimi (1962)先后发表,解决了可简单图化问题英语graph realization problem。这个问题是指给定一串有限多个非负整数组成的序列,是否存在一个简单图使得其度数列英语degree (graph theory)恰为这个序列。我们称满足条件的序列为可简单图化的。如果一个序列可简单图化,这个算法能够构造一个特解;否则算法指出序列不可简单图化。该算法是一个递归算法

算法

编辑

哈韦尔-哈基米算法基于以下定理。

 为有限多个非负整数组成的非递增序列 可简单图化当且仅当有穷序列 只含有非负整数且是可简单图化的。

如果给定的序列   是可简单图化的,那么算法最多运行 次赋值 。注意每次赋值后可能需要重新对序列排序。当 全部为零时,算法停止。在每一步中,如果序列可简单图化,就从  各引出一条边,即 ,然后令 约化为 。如果在任何一步中,序列 无法约化为非负整数序列 ,算法就给出最开始的 不可简单图化的结论。

参见 

编辑

参考文献 

编辑