Оценка количества простых циклов на графе
Введение
В ряде практических приложений возникает необходимость поиска простых циклов на графах, в связи с чем встаёт вопрос об оценке количества вычислительных операций, необходимых для этого, т.е. вычислительной сложности задачи.
Сама по себе задача перебора циклов на конкретном графе не является особенно сложной и легко реализуется средствами практически любого языка программирования, поддерживающего рекурсивные вычисления. Однако поиск методов априорной оценки вычислительных затрат переборного алгоритма, к моему удивлению, не дал вменяемых результатов. Тем не менее, достаточно простые рассуждения позволяют получить требуемую оценку, неплохо согласующуюся с тестовыми данными и позволяющую, помимо прочего, получить некоторую дополнительную информацию о структуре результатов перебора.
Формализация задачи
Итак, для определенности будем рассматривать граф G — ориентированный, без петель.
При этом порядок графа равен, очевидно, N, а количество рёбер — M.
Графу можно взаимно однозначно сопоставить матрицу смежности A.
Вследствие ориентированности графа G соответствующая матрица смежности в общем случае асимметрична:
Условие (4) отсутствия петель в графе приводит к тому, что на главной диагонали матрицы смежности допустимы только нулевые элементы
и матрица, таким образом, имеет вид
Под простым циклом L длины K на графе G будем понимать такую последовательность K неповторяющихся вершин графа, что каждые две последовательные вершины в последовательности, а также последняя и первая вершины в ней, смежны. Далее речь будет идти только о простых циклах; будем, для краткости, называть их просто циклами.
Будем далее обозначать
Оценка количества циклов
Для построения оценочной формулы примем следующее допущение: для графа G нам известны только порядок графа и количество рёбер в нём; точный вид матрицы смежности, какие-либо закономерности её формирования и т.п. нам неизвестны. Другими словами, мы будем считать, что наш конкретный граф был сконструирован в результате стохастического процесса такого рода:
Были зафиксированы N вершин графа, т.е. множество V.
Матрица смежности размером N x N была заполнена нулевыми значениями.
В матрице смежности совершенно случайным образом были выбраны ровно M элементов, не лежащих на главной диагонали, и им были присвоены единичные значения.
На указанных вершинах в соответствии с матрицей смежности были построены ребра графа E.
С учётом изложенного и (11), вероятность того, что произвольный элемент матрицы смежности вне главной диагонали равен единице, очевидно, равна
Легко увидеть, что выражения (12), (13) определяют циклическое размещение без повторений длины K из генеральной совокупности V размером в N элементов; из комбинаторики известно, что количество различных размещений при этом составляет
Для того, чтобы циклическое размещение из (12), (13) соответствовало циклу на графе G, необходимо, чтобы выполнялись условия (14), (15), т.е. чтобы существовали соответствующие рёбра, или, другими словами, K соответствующих элементов матрицы смежности были равны единице. С учётом (18), вероятность этого составляет
Таким образом, исходя из выбранной модели формирования графа G, произвольное циклическое размещение без повторений, состоящее из K вершин графа, формирует цикл на этом графе с вероятностью (21).
Заметим, что теперь количество циклов длины K на графе можно рассматривать как случайную величину, математическое ожидание которой из (19) и (21) составляет
И, наконец, математическое ожидание количества циклов на графе G с учётом (17) равно
Это и есть искомая оценка.
Замечания и обсуждение
Прежде всего, заметим, что указанная оценка довольно неплохо согласуется с экспериментальными данными. В таблице 1 приведены данные о количестве циклов в графах, полученные переборным методом. Эксперимент охватывал 4 группы графов, в каждой группе содержалось по 10 графов с 50-ю вершинами каждый и количеством рёбер 90, 100, 110 и 120 для каждой из групп соответственно. Несмотря на то, что для каждого конкретного графа количество циклов может заметно отличаться от оценочного, среднее по группе значение достаточно близко к нему.
Далее, стоит отметить, что даже для сравнительно небольших графов оценка (23) предсказывает наличие весьма значительного количества циклов на них; ряд оценочных значений приведен в таблице 2. Это стоит учитывать при планировании вычислений, связанных с перебором циклов на графе: они могут занять несколько больше времени и ресурсов, чем кажется!
Ещё одним интересным моментом является то, что формула (23) позволяет легко построить функцию, которую можно интерпретировать как оценку плотности распределения циклов по длинам:
На рис. 1 изображены графики оценочной и экспериментальной плотности распределения циклов по длинам на графе с 60 вершинами и 140 рёбрами. Как видно, они довольно неплохо согласуются между собой. При этом под экспериментальной плотностью понимается
где количества циклов в отношении получены прямым подсчётом.
Таким образом, оценка (24) позволяет сделать вполне обоснованное предсказание о характерных длинах циклов на графе.
Остаётся заметить, что хотя рассуждения в статье относятся к случаю простых циклов на ориентированных графах без петель, подобные результаты могут быть получены для прочих типов графов и циклов путём аналогичных рассуждений.
Заключение
Я надеюсь, что полученные результаты заинтересуют читателя, будут кому-то полезны в его практической деятельности и, быть может, послужат толчком к дальнейшим исследованиям в этой области.
