is_valid_degree_sequence_havel_hakimi#

is_valid_degree_sequence_havel_hakimi(deg_sequence)[源代码]#

如果 deg_sequence 可以由一个简单图实现，则返回 True。

验证过程使用 Havel-Hakimi 定理 [havel1955], [hakimi1962], [CL1996]。最坏情况运行时间为 $O(s)$，其中 $s$ 是序列的总和。

参数:

deg_sequence列表

一个整数列表，其中每个元素指定图中一个节点的度。

返回:

valid布尔值

如果 deg_sequence 是可图的则为 True，否则为 False。

注意

ZZ 条件表明，对于序列 d，如果

$$|d|>=\frac{(max(d)+min(d)+1{)}^2}{4\ast min(d)}$$

则 d 是可图的。这在 [1] 中的定理 6 中得到了证明。

参考文献

[1]

I.E. Zverovich and V.E. Zverovich. “Contributions to the theory of graphic sequences”, Discrete Mathematics, 105, pp. 292-303 (1992).

[havel1955]

Havel, V. “A Remark on the Existence of Finite Graphs” Casopis Pest. Mat. 80, 477-480, 1955.

[hakimi1962]

Hakimi, S. “On the Realizability of a Set of Integers as Degrees of the Vertices of a Graph.” SIAM J. Appl. Math. 10, 496-506, 1962.

[CL1996]

G. Chartrand and L. Lesniak, “Graphs and Digraphs”, Chapman and Hall/CRC, 1996.

示例

>>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
>>> sequence = (d for _, d in G.degree())
>>> nx.is_valid_degree_sequence_havel_hakimi(sequence)
True

测试一个无效序列： >>> sequence_list = [d for _, d in G.degree()] >>> sequence_list[-1] += 1 >>> nx.is_valid_degree_sequence_havel_hakimi(sequence_list) False