is_digraphical

is_digraphical(in_sequence, out_sequence)

如果某个有向图可以实现进出度序列，则返回true。

参数

in_sequence列表或可迭代容器

以度为单位的整数节点序列

out_sequence列表或可迭代容器

整型结点出度序列

返回

valid布尔尔

如果输入序列和输出序列为双音假，则为真，否则为假。

笔记

该算法来自Kleitman和Wang [1]. 最糟糕的情况是运行时 \(O(s \times \log n)\) 哪里 \(s\) 和 \(n\) 分别是序列的总和和长度。

工具书类

1

D.J.Kleitman和D.L.Wang用给定值和因子构造图和有向图的算法，离散数学，6（1），第79-88页（1973）