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

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

В любом ориентированном двудольном графе все циклы имеют длину, которая делится на два. По этой причине никакой двудольный граф не может быть апериодичным. В любом направленном ациклическом графе является истинным, но совершенно бессодержательным, утверждение, что любое число 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 // / 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 : . — arXiv : .