is_valid_degree_sequence_havel_hakimi

is_valid_degree_sequence_havel_hakimi(deg_sequence)

如果deg_序列可以通过简单的图实现，则返回true。

验证使用Havel-Hakimi定理 [havel1955], [hakimi1962], [CL1996]. 最坏情况下的运行时间是 \(O(s)\) 哪里 \(s\) 是该序列的和。

参数

deg_sequence列表

整数列表，其中每个元素指定图中节点的度。

返回

valid布尔尔

如果deg_equence是图形化的，则为True，否则为False。

笔记

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

\[|d| >=\frac（\max（d）+\min（d）+1）^2 4*\min（d）\]

那么d就是图形。这一点如年的定理6所示。 [1].

工具书类

1

即Zverovich和V.E.Zverovich。”对图形序列理论的贡献”，离散数学，105，292-303页（1992）。

havel1955

Havel，V.《关于有限图的存在性的注记》，Casopis Pest。垫子。80,477-480,1955年。

hakimi1962

Hakimi、S.“关于整数集作为图的顶点的度的可实现性。”暹罗J.Appl.数学课。10496-506,1962年。

CL1996

G.Chartrand和L.Lesniak，《图形和有向图》，Chapman and Hall/CRC，1996。