is_valid_degree_sequence_havel_hakimi#

is_valid_degree_sequence_havel_hakimi(deg_sequence)[source]#

如果度序列可以通过简单图实现，则返回 True。

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

Parameters:
deg_sequencelist

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

Returns:
validbool

如果 deg_sequence 是图形的，则返回 True，否则返回 False。

Notes

ZZ 条件指出，对于序列 d，如果

\[|d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}\]

则 d 是图形的。这在 [1] 中的定理 6 中被证明。

References

[1]

I.E. Zverovich 和 V.E. Zverovich。”对图形序列理论的贡献”，离散数学，105，第 292-303 页（1992）。

[havel1955]

Havel, V. “关于有限图存在性的一个注记”，Casopis Pest. Mat. 80，第 477-480 页，1955。

[hakimi1962]

Hakimi, S. “关于将一组整数实现为图的顶点度数的可行性”，SIAM J. Appl. Math. 10，第 496-506 页，1962。

[CL1996]

  1. Chartrand 和 L. Lesniak，”图和有向图”，Chapman and Hall/CRC，1996。

Examples

>>> 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

On this page