哈韦尔-哈基米算法

哈韦尔-哈基米算法是一种图论算法，由Template:Harvtxt与Template:Harvtxt先后发表，解决了Template:Tsl。这个问题是指给定一串有限多个非负整数组成的序列，是否存在一个简单图使得其Template:Tsl恰为这个序列。我们称满足条件的序列为可简单图化的。如果一个序列可简单图化，这个算法能够构造一个特解；否则算法指出序列不可简单图化。该算法是一个递归算法。

算法

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

令$S=(d_1,\dots ,d_n)$为有限多个非负整数组成的非递增序列。$S$可简单图化当且仅当有穷序列$S^{\prime }=(d_2-1,d_3-1,\dots ,d_{d_1+1}-1,d_{d_1+2},\dots ,d_n)$只含有非负整数且是可简单图化的。

如果给定的序列 $S$ 是可简单图化的，那么算法最多运行$n-1$次赋值$S:=S^{\prime }$。注意每次赋值后可能需要重新对序列排序。当$S^{\prime }$全部为零时，算法停止。在每一步中，如果序列可简单图化，就从$v_1$向$v_2,\cdots ,v_n$各引出一条边，即$\{v_1,v_2\},\{v_1,v_3\},\cdots ,\{v_1,v_{d_1+1}\}$，然后令$S$约化为$S^{\prime }$。如果在任何一步中，序列$S$无法约化为非负整数序列$S^{\prime }$，算法就给出最开始的$S$不可简单图化的结论。

参见 

• Template:Tsl

参考文献 

• Template:Citation
• Template:Citation.