is_valid_degree_sequence_erdos_gallai#
- is_valid_degree_sequence_erdos_gallai(deg_sequence)[源代码]#
如果deg_序列可以通过简单的图实现，则返回true。
验证是使用erdős-Gallai定理完成的。 [EG1960].
- 参数
- deg_sequence列表
整数列表
- 返回
- valid布尔尔
如果deg_equence是图形化的，则为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是指d_k>=k的任何索引，n_j是j在d中出现的次数。最大的强索引称为Durfee索引。
这种特殊的重排来自于中的定理3的证明 [2].
ZZ条件表示，对于序列d，如果
\[|d| >=\frac（\max（d）+\min（d）+1）^2 4*\min（d）\]那么d就是图形。这一点如年的定理6所示。 [2].
工具书类