is_aperiodic

is_aperiodic(G)

如果 G 是非周期图，则返回 True。

如果不存在大于 1 的整数 k 能够整除图中每个圈的长度，则有向图是非周期的。

参数:

GNetworkX DiGraph

有向图

返回:

bool

如果图是非周期图则为 True，否则为 False

引发:

NetworkXError

如果 G 不是有向图

注意

此方法使用了[1]中概述的方法，给定图中 \(m\) 条边，运行时间为 \(O(m)\)。请注意，如果图是无环的，则它不是非周期的，因为任何整数都能整除长度为 0 的圈。

参考文献

[1]

Jarvis, J. P.; Shier, D. R. (1996), “Graph-theoretic analysis of finite Markov chains,” in Shier, D. R.; Wallenius, K. T., Applied Mathematical Modeling: A Multidisciplinary Approach, CRC Press.

示例

一个由一个长度为 2 的圈组成的图。因此 k = 2 整除图中每个圈的长度，所以该图不是非周期的

>>> DG = nx.DiGraph([(1, 2), (2, 1)])
>>> nx.is_aperiodic(DG)
False

一个由两个圈组成的图：一个长度为 2，另一个长度为 3。圈长互质，因此不存在大于 1 的单个 k 值能够整除每个圈长，所以该图是非周期的

>>> DG = nx.DiGraph([(1, 2), (2, 3), (3, 1), (1, 4), (4, 1)])
>>> nx.is_aperiodic(DG)
True

一个由两个圈组成的图：一个长度为 2，另一个长度为 4。圈长共享公因数 k = 2，因此该图不是非周期的

>>> DG = nx.DiGraph([(1, 2), (2, 1), (3, 4), (4, 5), (5, 6), (6, 3)])
>>> nx.is_aperiodic(DG)
False

一个无环图，因此该图不是非周期的

>>> DG = nx.DiGraph([(1, 2), (2, 3)])
>>> nx.is_aperiodic(DG)
False