is_multigraphical

is_multigraphical(sequence)

如果某个多重图可以实现该序列，则返回 True。

Parameters:

sequencelist

一个整数列表

Returns:

validbool

如果 deg_sequence 是一个多重图度序列，则返回 True，否则返回 False。

Notes

最坏情况下的运行时间是 \(O(n)\)，其中 \(n\) 是序列的长度。

References

[1]

19. 12. Hakimi. “关于将一组整数作为线性图顶点的度数实现的问题”, J. SIAM, 10, 第 496-506 页 (1962).

Examples

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

测试一个非多重图序列： >>> sequence_list = [d for _, d in G.degree()] >>> sequence_list[-1] += 1 >>> nx.is_multigraphical(sequence_list) False