定期和非定期有向图

Question

我有点困惑如何区分一个有向图是非周期性的还是周期性的。维基百科对于非周期性图的定义如下：

“在图论这个数学领域中，如果不存在大于1的整数k能够被图中每个环的长度整除，则称有向图为非周期性的。”

例如下面的图是非周期性的还是周期性的？我认为这个图不是周期性的，但根据维基百科的定义，它是周期性的，因为整数k=2可以整除图中的所有环（AC和ACDB）。

如果有人能提供一种区分图形是否为非周期性或周期性的方法，那将是很好的。也许可以提供一些周期性和非周期性图形的例子来帮助解释。

谢谢。

- Jaman

Answer 1

这是一个基于Networkx的Python短实现，用于查找图形是否是周期性的：

import networkx as nx
from math import gcd
from functools import reduce

G = nx.DiGraph()
G.add_edges_from([('A', 'C'), ('C', 'D'), ('D', 'B'), ('B', 'A'), ('C', 'A')])
cycles = list(nx.algorithms.cycles.simple_cycles(G))
cycles_sizes = [len(c) for c in cycles]
cycles_gcd = reduce(gcd, cycles_sizes)
is_periodic = cycles_gcd > 1
print("is_periodic: {}".format(is_periodic))

代码的功能如下：

• 通过指定边来构建图形（使用您的示例）。
• 列出所有循环（AC和ACDB）。
• 列出所有循环大小[2,4]。
• 找到最大公约数（GCD）。
• 如果GCD为1，则意味着该图是非周期性的，否则根据定义它是周期性的。

您提供的上述图不是非周期性的，因为它具有2的周期。 （即每个节点可以在2步的倍数中返回自己）

您可以尝试不同的示例以获得更好的直觉，并通过添加以下内容来可视化您的图形：

import matplotlib.pyplot as plt
nx.draw_networkx(G, with_labels=True)
plt.show()

- zohar.kom