is_valid_degree_sequence_erdos_gallai

is_valid_degree_sequence_erdos_gallai(deg_sequence)

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

验证使用的是 Erdős-Gallai 定理 [EG1960]。

Parameters:

deg_sequence列表

一个整数列表

Returns:

valid布尔值

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

Notes

此实现使用了 Erdős-Gallai 准则的等价形式。 最坏情况下的运行时间是 \(O(n)\)，其中 \(n\) 是序列的长度。

具体来说，序列 d 是图形的当且仅当序列的和是偶数，并且对于序列中的所有强索引 k，

\[\sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{j=k+1}^{n} \min(d_i,k) = k(n-1) - ( k \sum_{j=0}^{k-1} n_j - \sum_{j=0}^{k-1} j n_j )\]

强索引 k 是任何满足 d_k >= k 的索引，值 n_j 是 j 在 d 中的出现次数。最大强索引称为 Durfee 索引。

这种特定的重排来自 [2] 中定理 3 的证明。

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

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

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

References

[1]

A. Tripathi 和 S. Vijay. “A note on a theorem of Erdős & Gallai”, Discrete Mathematics, 265, pp. 417-420 (2003).

[2] (1,2)

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

[EG1960]

Erdős 和 Gallai, Mat. Lapok 11 264, 1960.

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

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