Введение
В ряде практических приложений возникает необходимость поиска простых циклов на графах, в связи с чем встаёт вопрос об оценке количества вычислительных операций, необходимых для этого, т.е. вычислительной сложности задачи.
Сама по себе задача перебора циклов на конкретном графе не является особенно сложной и легко реализуется средствами практически любого языка программирования, поддерживающего рекурсивные вычисления. Однако поиск методов априорной оценки вычислительных затрат переборного алгоритма, к моему удивлению, не дал вменяемых результатов. Тем не менее, достаточно простые рассуждения позволяют получить требуемую оценку, неплохо согласующуюся с тестовыми данными и позволяющую, помимо прочего, получить некоторую дополнительную информацию о структуре результатов перебора.
Формализация задачи
Итак, для определенности будем рассматривать граф G – ориентированный, без петель.
![](https://habrastorage.org/getpro/habr/upload_files/66f/e60/3a9/66fe603a9f2c632932760d746a764af5.png)
При этом порядок графа равен, очевидно, N, а количество рёбер – M.
![](https://habrastorage.org/getpro/habr/upload_files/685/ad5/fc3/685ad5fc30dcacb02f9d2fb56ce21a80.png)
Графу можно взаимно однозначно сопоставить матрицу смежности A.
![](https://habrastorage.org/getpro/habr/upload_files/c0d/88d/54f/c0d88d54f42ce25e570f3ff904c1066c.png)
Вследствие ориентированности графа G соответствующая матрица смежности в общем случае асимметрична:
![](https://habrastorage.org/getpro/habr/upload_files/253/069/f90/253069f9071cf847282ffe2f479c2c58.png)
Условие (4) отсутствия петель в графе приводит к тому, что на главной диагонали матрицы смежности допустимы только нулевые элементы
![](https://habrastorage.org/getpro/habr/upload_files/3b3/a5f/2a4/3b3a5f2a40e9e33b5ae29a526a0cc16e.png)
и матрица, таким образом, имеет вид
![](https://habrastorage.org/getpro/habr/upload_files/568/3f1/006/5683f100631c0f407ac9fc52349b1ea8.png)
Под простым циклом L длины K на графе G будем понимать такую последовательность K неповторяющихся вершин графа, что каждые две последовательные вершины в последовательности, а также последняя и первая вершины в ней, смежны. Далее речь будет идти только о простых циклах; будем, для краткости, называть их просто циклами.
![](https://habrastorage.org/getpro/habr/upload_files/d8b/900/4eb/d8b9004ebaa8c5cf41bb729af0ec93f3.png)
Будем далее обозначать
![](https://habrastorage.org/getpro/habr/upload_files/a49/ec0/67f/a49ec067f837d4fdefefad2e7f1f9272.png)
Оценка количества циклов
Для построения оценочной формулы примем следующее допущение: для графа G нам известны только порядок графа и количество рёбер в нём; точный вид матрицы смежности, какие-либо закономерности её формирования и т.п. нам неизвестны. Другими словами, мы будем считать, что наш конкретный граф был сконструирован в результате стохастического процесса такого рода:
Были зафиксированы N вершин графа, т.е. множество V.
Матрица смежности размером N x N была заполнена нулевыми значениями.
В матрице смежности совершенно случайным образом были выбраны ровно M элементов, не лежащих на главной диагонали, и им были присвоены единичные значения.
На указанных вершинах в соответствии с матрицей смежности были построены ребра графа E.
С учётом изложенного и (11), вероятность того, что произвольный элемент матрицы смежности вне главной диагонали равен единице, очевидно, равна
![](https://habrastorage.org/getpro/habr/upload_files/59d/231/d22/59d231d2263342b0cc0c71506a47d838.png)
Легко увидеть, что выражения (12), (13) определяют циклическое размещение без повторений длины K из генеральной совокупности V размером в N элементов; из комбинаторики известно, что количество различных размещений при этом составляет
![](https://habrastorage.org/getpro/habr/upload_files/6bc/0fd/c60/6bc0fdc60ceb290d0b87e5701e10db63.png)
Для того, чтобы циклическое размещение из (12), (13) соответствовало циклу на графе G, необходимо, чтобы выполнялись условия (14), (15), т.е. чтобы существовали соответствующие рёбра, или, другими словами, K соответствующих элементов матрицы смежности были равны единице. С учётом (18), вероятность этого составляет
![](https://habrastorage.org/getpro/habr/upload_files/aeb/b3f/df4/aebb3fdf4436bf61d8e215dc43c5f8fb.png)
Таким образом, исходя из выбранной модели формирования графа G, произвольное циклическое размещение без повторений, состоящее из K вершин графа, формирует цикл на этом графе с вероятностью (21).
Заметим, что теперь количество циклов длины K на графе можно рассматривать как случайную величину, математическое ожидание которой из (19) и (21) составляет
![](https://habrastorage.org/getpro/habr/upload_files/329/326/7a0/3293267a014079cf64b6c24a0e5ff05e.png)
И, наконец, математическое ожидание количества циклов на графе G с учётом (17) равно
![](https://habrastorage.org/getpro/habr/upload_files/e70/4eb/68f/e704eb68f20218a45eef0aac421a1686.png)
Это и есть искомая оценка.
Замечания и обсуждение
Прежде всего, заметим, что указанная оценка довольно неплохо согласуется с экспериментальными данными. В таблице 1 приведены данные о количестве циклов в графах, полученные переборным методом. Эксперимент охватывал 4 группы графов, в каждой группе содержалось по 10 графов с 50-ю вершинами каждый и количеством рёбер 90, 100, 110 и 120 для каждой из групп соответственно. Несмотря на то, что для каждого конкретного графа количество циклов может заметно отличаться от оценочного, среднее по группе значение достаточно близко к нему.
![](https://habrastorage.org/getpro/habr/upload_files/acb/891/413/acb8914131a4c9b927b773a8973deee2.png)
Далее, стоит отметить, что даже для сравнительно небольших графов оценка (23) предсказывает наличие весьма значительного количества циклов на них; ряд оценочных значений приведен в таблице 2. Это стоит учитывать при планировании вычислений, связанных с перебором циклов на графе: они могут занять несколько больше времени и ресурсов, чем кажется!
Ещё одним интересным моментом является то, что формула (23) позволяет легко построить функцию, которую можно интерпретировать как оценку плотности распределения циклов по длинам:
![](https://habrastorage.org/getpro/habr/upload_files/fb0/75a/e39/fb075ae397aacbfb459c4802b66a41d1.png)
На рис. 1 изображены графики оценочной и экспериментальной плотности распределения циклов по длинам на графе с 60 вершинами и 140 рёбрами. Как видно, они довольно неплохо согласуются между собой. При этом под экспериментальной плотностью понимается
![](https://habrastorage.org/getpro/habr/upload_files/410/866/12b/41086612bf5e7fdd3885b6c27dee1658.png)
где количества циклов в отношении получены прямым подсчётом.
Таким образом, оценка (24) позволяет сделать вполне обоснованное предсказание о характерных длинах циклов на графе.
Остаётся заметить, что хотя рассуждения в статье относятся к случаю простых циклов на ориентированных графах без петель, подобные результаты могут быть получены для прочих типов графов и циклов путём аналогичных рассуждений.
![](https://habrastorage.org/getpro/habr/upload_files/1bf/fa1/ecd/1bffa1ecda35e416d7b7d35844308f63.png)
Заключение
Я надеюсь, что полученные результаты заинтересуют читателя, будут кому-то полезны в его практической деятельности и, быть может, послужат толчком к дальнейшим исследованиям в этой области.
nin-jin
Учитывая, что графы зачастую являются полносвязными или около того, то для них есть более простая оценка: 1 + число_рёбер - число_узлов. Логика простая: n-1 рёбер достаточно, чтобы связать все узлы без циклов. Каждое следующее ребро добавляет 1 цикл.
rafuck
Одно ребро может добавить гораздо больше, чем 1 цикл.
nin-jin
Каким образом?
CheshireBat Автор
К сожалению, в комментариях не очень удобно приводить подробные примеры, но обратите внимание на табл.1 -- в ней количества циклов определены прямым подсчетом на вполне реальных графах.
rafuck
Возьмем первый попавшийся ориентированный граф из картинок в гугле:
https://static.wixstatic.com/media/d028ad_fc16cd9d11ef4e38a6213876166ba781.png/v1/fill/w_433,h_221,al_c,q_85,usm_0.66_1.00_0.01,enc_auto/d028ad_fc16cd9d11ef4e38a6213876166ba781.png
Добавим ребро Г->Е. Сколько новых циклов образуется?
nin-jin
Вы видимо намекаете на вырожденные циклы, которые образуются из циклов поменьше. Такие обычно не интересны.
rafuck
Не припоминаю такого термина "вырожденный цикл". В любом случае в данной статье определение цикла дано. Кроме того. Про циклы поменьше. Давайте представим граф, узлы которого образуют четырехугольник ABCD. Ребра {A->B, A->D, B->C, D->C}. Сколько циклов возникнет при добавлении ребра C->A?
nin-jin
Математик: ваш граф зависимостей образует 11 циклов (AA, BB, CC, DD, ABCA, ABDA, BDCB, CDAC, ABCDA, BCADB, CABDC) и может быть сериализован 24 способами (далее куча формул с факториалами). Каждый узел имеет не менее 4 и не более 4 рёбер (далее огромная таблица смежности со статистикой по каждой строке и столбцу). Граф может быть представлен на плоскости без пересечения рёбер и раскрашен не менее 4 цветами (далее доказательство на 10 страниц). Физическое моделирование методом Монте-Карло показало, что при одинаковой силе всех рёбер, наиболее оптимальное (по Русалочкину) расположение узлов - это замкнутый треугольник, внутри которого располагаются все остальные узлы (далее листинг программы на псевдоскрипте и схематическое изображение всех двух возможных конфигураций).
Инженер: у вас 3 циклические зависимости (ABD, BDC, CDA). Самые слабые зависимости (AB, BC, CD) были автоматически устранены для корректного упорядочивания ваших модулей в бандле.
rafuck
Для того, чтобы присутствовали петли (простые циклы из одной вершины), необходимо, чтобы присутствовало соответствующее ребро, например, A->A, однако в списке ребер из моего примера таковых нет. Далее, возьмем еще тип некорректного цикла из вашего примера: BDCB. Для того, чтобы он существовал, необходимо ребро B->D, какового в рассматриваемом графе также не наблюдается.
CheshireBat Автор
То есть вас интересуют циклы подлиннее? Тогда я продолжу ваш воображаемый диалог:
Инженер: у меня есть небольшой граф из 100 вершин с 500-ми ребрами, мне надо найти самый длинный цикл на нем. Тэкс, мой супер-пупер параллельный алгоритм позволяет находить 1000 000 000 циклов в секунду, а примерное число циклов у нас... таааак... 1 + 500 - 100 ... 401. Через секунду скажу результат!
Математик: сын мой, не спеши, ты получишь свой результат примерно через 3 170 979 198 376 459 000 лет... Я, конечно, могу ошибиться на порядок-другой... Но к обеду точно не управишься!
CheshireBat Автор
Комментарии тоже не все одинаково интересны; тем не менее, они существуют.
CheshireBat Автор
Для полносвязных графов, т.е. таких, где каждая пара вершин смежна, каждое циклическое размещение вершин образует цикл, и общее количество их определяется суммированием выражения (19) по тексту статьи для K от 2 до N, что существенно больше Вашей оценки. Например, в полносвязном ориентированном графе с 10 вершинами имеется 90 ребер, и общее количество циклов составляет 1112073. Сравните с 1 + 90 - 10 = 81.
Я очень благодарен Вам за комментарий, он весьма наглядно показывает, как крупно можно ошибиться в интуитивных рассуждениях о графах и циклах на них.
nin-jin
*просто связный.