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

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

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

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

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

Предположим, что G и сильно связна что k делит длины всех циклов в G .Рассмотрим результаты выполнения поиска в глубину G v , начиная с любой вершины, и присваивая каждой вершине множеству Vi , _где i — длина (взятая по модулю k ) пути в дереве поиска в глубину из корень до v . Можно показать ( Jarvis & Shier 1996 ), что это разбиение на множества Vi _{обладает} каждое ребро в графе переходит из множества Vi _{тем свойством, что} в другое множество V _{( i + 1) по модулю k} . наоборот существует разбиение с этим свойством , если для сильно связного графа G , k должно делить длины всех циклов в G. И

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

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

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

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

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

Приложения

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

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

Ссылки

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