Апериодичный граф

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

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

Сильно связанный орграф с периодом три.

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

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

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

Предположим, что граф G сильно связан и что k делит длины всех циклов в графе G.

Рассмотрим результаты поиска в глубину на графе G, начиная с любой вершины, и назначим каждой вершине v набор V_i, где i равно длине (по модулю k) пути в дереве поиска в глубину от корня v. Можно показать, что это разбиение вершин V_i имеет свойство, что каждое ребро в графе исходит из множества V_i и кончается в другом множестве V_{(i + 1) mod k}. Обратно, если разбиение с таким свойством существует для сильно связанного графа G, k должно делить длины всех циклов графа G.

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

• Осуществляем поиск в глубину по графу G
• Для каждой дуги e графа G, соединяющей вершину на уровне i дерева поиска в глубину с вершиной на уровне j, положим k_e=j — i — 1.
• Вычислим наибольший общий делитель набора чисел k_e.

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

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

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

Приложения

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

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

Литература

• Jarvis J. P., Shier D. R. Graph-theoretic analysis of finite Markov chains // Applied Mathematical Modeling: A Multidisciplinary Approach / Shier D. R., Wallenius K. T.. — CRC Press, 1996.
• Avraham N. Trahtman. The road coloring problem // Israel Journal of Mathematics. — 2009. — Т. 172, вып. 1. — С. 51–60. — doi:10.1007/s11856-009-0062-5. — arXiv:0709.0099.