Периодические и апериодические ориентированные графы - PullRequest
Новая
       49

Периодические и апериодические ориентированные графы

0 голосов
/ 04 января 2019

Я немного запутался в том, как отличить ориентированный граф от апериодического или периодического.Википедия говорит об апериодических графах:

'В математической области теории графов ориентированный граф называется апериодическим, если нет целого числа k> 1, которое делит длину каждого циклаграфик. '

Например, график ниже апериодический или периодический.Я считаю, что график не является периодическим, но по определению википедии он является периодическим, поскольку целое число k = 2 делит все циклы в графе (AC и ACDB)

enter image description here

Было бы замечательно, если бы кто-то мог предоставить метод, чтобы различать, является ли график апериодическим или периодическим.Возможно, приведу несколько примеров периодических и апериодических графиков, чтобы помочь объяснить.

Спасибо.

1 Ответ

0 голосов
/ 13 января 2019

Вот короткая реализация на Python, основанная на Networkx, для нахождения графика периодического: 

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, это означает, что график является периодическим, в противном случае он является апериодическим по определению.

Вы можете поиграть с различными примерами, чтобы улучшить интуицию, а также визуализировать свой график.добавив: 

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