havel_hakimi_graph

havel_hakimi_graph(deg_sequence, create_using=None)

使用 Havel-Hakimi 算法构造一个具有给定度序列的简单图。

参数:

deg_sequence: 整数列表

每个整数对应一个节点的度（无需排序）。

create_usingNetworkX 图构造器，可选 (默认=nx.Graph)

要创建的图类型。如果是图实例，则在填充前会清空。不允许使用有向图。

引发:

NetworkXException

对于非图示度序列（即，不能由某个简单图实现的度序列）。

注释

Havel-Hakimi 算法通过反复连接度最高的节点与其他度最高的节点、按度重新排序剩余节点并重复此过程来构造一个简单图。生成的图具有高度的度关联性。节点编号为 1,.., len(deg_sequence)，对应于它们在 deg_sequence 中的位置。

基本算法来自 Hakimi [1]，并由 Kleitman 和 Wang [2] 进行了推广。

参考文献

[1]

Hakimi S., On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I, Journal of SIAM, 10(3), pp. 496-506 (1962)

[2]

Kleitman D.J. and Wang D.L. Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors Discrete Mathematics, 6(1), pp. 79-88 (1973)