Апериодический график - Aperiodic graph

Апериодический граф. Циклы в этом графе имеют длину 5 и 6; следовательно, нет k > 1, что делит длину всех циклов.
А сильно связный граф с периодом три.

в математический зона теория графов, а ориентированный граф как говорят апериодический если нет целого числа k > 1, что делит длину каждого цикл графа. Эквивалентно график является апериодическим, если наибольший общий делитель длины его циклов - одна; этот наибольший общий делитель графа грамм называется период из грамм.

Графики, которые не могут быть апериодическими

В любом направленном двудольный граф, все циклы имеют длину, кратную двум. Следовательно, никакой ориентированный двудольный граф не может быть апериодическим. В любом ориентированный ациклический граф, это пустая правда что каждый k делит все циклы (поскольку нет направленных циклов, которые нужно разделить), поэтому ни один ориентированный ациклический граф не может быть апериодическим. И в любом направленном график цикла, существует только один цикл, поэтому длина каждого цикла делится на п, длина этого цикла.

Проверка на апериодичность

Предположим, что грамм сильно связан и что k делит длины всех циклов в грамм.Рассмотрим результаты выполнения поиск в глубину из грамм, начиная с любой вершины и назначая каждой вершине v к набору Vя куда я это длина (взято по модулю k) пути в дереве поиска в глубину от корня до v. Это может быть показано (Джарвис и Шайер 1996 ), что это разбиение на множества Vя обладает тем свойством, что каждое ребро в графе выходит из множества Vя в другой набор V(я + 1) мод k. И наоборот, если разбиение с этим свойством существует для сильно связного графа грамм, k должен делить длину всех циклов на грамм.

Таким образом, мы можем найти период сильно связного графа грамм по следующим шагам:

  • Выполните поиск в глубину грамм
  • Для каждого е в грамм который соединяет вершину на уровне я дерева поиска в глубину до вершины на уровне j, позволять kе = j - я - 1.
  • Вычислить наибольший общий делитель набора чисел kе.

График является апериодическим тогда и только тогда, когда период, вычисленный таким образом, равен 1.

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

Джарвис и Шиер описывают очень похожий алгоритм, используя поиск в ширину вместо поиска в глубину; Преимущество поиска в глубину состоит в том, что в один и тот же поиск можно включить строгий анализ связности.

Приложения

В сильно связный граф, если определить Цепь Маркова на вершинах, в которых вероятность перехода из v к ш отличен от нуля тогда и только тогда, когда есть ребро из v к ш, то эта цепочка апериодична тогда и только тогда, когда граф апериодичен. Цепь Маркова, в которой все состояния рекуррентны, имеет сильно связный граф переходов между состояниями, а цепь Маркова является апериодической тогда и только тогда, когда этот граф является апериодическим. Таким образом, апериодичность графов - полезное понятие при анализе апериодичности цепей Маркова.

Апериодичность также является важным необходимым условием решения проблема окраски дороги. По решению этой проблемы (Trahtman 2009 ), сильно связный ориентированный граф, в котором все вершины имеют одинаковые превосходить имеет синхронизируемую раскраску ребер тогда и только тогда, когда она апериодическая.

Рекомендации

  • Jarvis, J. P .; Shier, D. R. (1996), "Теоретико-графический анализ конечных цепей Маркова", в Shier, D. R .; Валлениус, К. Т. (ред.), Прикладное математическое моделирование: мультидисциплинарный подход (PDF), CRC Press.
  • Трахтман, Авраам Н. (2009), «Проблема раскраски дороги», Израильский математический журнал, 172 (1): 51–60, arXiv:0709.0099, Дои:10.1007 / s11856-009-0062-5.