is_pseudographical

is_pseudographical(sequence)

如果某个伪图能够实现该序列，则返回 True。

每个总和为偶数的非负整数序列都是伪图可实现的（参见 [1]）。

参数:

sequence列表或可迭代容器

整数节点度的序列

返回:

valid布尔值

如果序列是伪图度序列则返回 True，否则返回 False。

注意

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

参考

[1]

F. Boesch and F. Harary. “Line removal algorithms for graphs and their degree lists”, IEEE Trans. Circuits and Systems, CAS-23(12), pp. 778-782 (1976).

示例

>>> 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_pseudographical(sequence)
True

测试一个非伪图可实现的序列： >>> sequence_list = [d for _, d in G.degree()] >>> sequence_list[-1] += 1 >>> nx.is_pseudographical(sequence_list) False