is_aperiodic

is_aperiodic(G)

如果 G 是无周期的，则返回 True。

有向图是无周期的，如果图中不存在一个大于 1 的整数 k，使得 k 能整除图中每个环的长度。

Parameters:

GNetworkX 有向图

一个有向图

Returns:

bool

如果图是无周期的，则返回 True，否则返回 False

Raises:

NetworkXError

如果 G 不是有向图

Notes

这使用了 [1] 中概述的方法，该方法在给定 G 中有 \(m\) 条边的情况下，运行时间为 \(O(m)\)。请注意，如果图是无环的，则它不是无周期的，因为每个整数都能整除长度为 0 的环。

References

[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.

Examples

一个由长度为 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