Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
havel_hakimi_graph¶
- havel_hakimi_graph(deg_sequence, create_using=None)[source]¶
Return a simple graph with given degree sequence constructed using the Havel-Hakimi algorithm.
Parameters : deg_sequence: list of integers
Each integer corresponds to the degree of a node (need not be sorted).
create_using : graph, optional (default Graph)
Return graph of this type. The instance will be cleared. Directed graphs are not allowed.
Raises : NetworkXException
For a non-graphical degree sequence (i.e. one not realizable by some simple graph).
Notes
The Havel-Hakimi algorithm constructs a simple graph by successively connecting the node of highest degree to other nodes of highest degree, resorting remaining nodes by degree, and repeating the process. The resulting graph has a high degree-associativity. Nodes are labeled 1,.., len(deg_sequence), corresponding to their position in deg_sequence.
The basic algorithm is from Hakimi [R282] and was generalized by Kleitman and Wang [R283].
References
[R282] (1, 2) 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) [R283] (1, 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)