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)