is_valid_degree_sequence_erdos_gallai

is_valid_degree_sequence_erdos_gallai(deg_sequence)

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

验证使用 Erdős-Gallai 定理完成 [EG1960]。

参数:

deg_sequencelist

一个整数列表

返回:

validbool

如果 deg_sequence 是可绘图的（graphical），则为 True，否则为 False。

说明

此实现使用了 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 中得到证明。

参考文献

[1]

A. Tripathi 和 S. Vijay。“关于 Erdős & Gallai 定理的注记”，Discrete Mathematics, 265, pp. 417-420 (2003)。

[2] (1,2)

I.E. Zverovich 和 V.E. Zverovich。“对图序列理论的贡献”，Discrete Mathematics, 105, pp. 292-303 (1992)。

[EG1960]

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

示例

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