查看“︁哈韦尔-哈基米算法”︁的源代码

'''哈韦尔-哈基米算法'''是一种图论算法，由{{harvtxt|Havel|1955}}与{{harvtxt|Hakimi|1962}}先后发表，解决了{{tsl|en|graph realization problem|可简单图化问题|可简单图化问题}}。这个问题是指给定一串有限多个非负[[整数]]组成的[[列举法 (集合论)|序列]]，是否存在一个[[图 (数学)|简单图]]使得其{{tsl|en|degree (graph theory)|度数列|度数列}}恰为这个序列。我们称满足条件的序列为可简单图化的。如果一个序列可简单图化，这个算法能够构造一个特解；否则算法指出序列不可简单图化。该算法是一个[[递归 (计算机科学)|递归算法]]。

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

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

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

== 参见 ==
*{{tsl|en|Erdős–Gallai theorem|Erdős–Gallai定理|Erdős–Gallai定理}}

== 参考文献 ==
*{{citation
| last = Havel
| first = Václav
| authorlink = V. J. Havel
| year = 1955
| title = A remark on the existence of finite graphs
| language = cs
| journal = Časopis pro pěstování matematiky
| volume = 80
| pages = 477–480
| url = http://eudml.org/doc/19050
| accessdate = 2017-11-02
| archive-date = 2017-07-29
| archive-url = https://web.archive.org/web/20170729174826/https://eudml.org/doc/19050
| dead-url = no
}}
*{{citation
 | last = Hakimi | first = S. L. | authorlink = S. L. Hakimi
 | journal = Journal of the {{tsl|en|Society for Industrial and Applied Mathematics||}}
 | mr = 0148049
 | pages = 496–506
 | title = On realizability of a set of integers as degrees of the vertices of a linear graph. I
 | volume = 10
 | year = 1962}}.
{{reflist}}

[[Category:图算法]]