Как посчитать циклы в графе
БлогNot. Ищем количество циклов в неориентированном графе
Ищем количество циклов в неориентированном графе
Задача — найти в произвольном неориентированном графе количество циклов, не связанных с другими частями графа.
Искомый цикл состоит минимум из двух вершин и не имеет «лишних» рёбер, то есть, представляет собой кольцо вида 1-2-1 или 1-2-3-1, и т.п.
Граф был взят из этой заметки, только к нему приписан не связанный с остальными вершинами цикл 8-9-10-8.
Само представление графа — максимально простое, с помощью векторов, расчёт проверен в консоли Visual Studio 2013, больше тут ничего нет под рукой 🙂
Во второй задаче для двух положительных натуральных значений n и k задан неориентированный полный связный граф из n узлов, то есть, каждый узел связан с каждым.
Проблема состоит в том, чтобы вычислить количество способов, с помощью которых можно начинать с любого узла и возвращаться к нему, посетив всего k узлов.
Например, для кольца из 3 вершин и длины пути 3 таких способов 2 (1-2-3-1 и 1-3-2-1), если вершин становится 4, то есть 3 способа сделать путь для значения k=2 (1-2-1, 1-3-1, 1-4-1) — см. рисунок.
полные связные графы размерности 3 и 4
При увеличении размерности всё становится интереснее, например, для n=5 и k=3 возможные пути нарисованы на втором рисунке шестью цветами радуги, и каждый путь можно пройти в двух направлениях, то есть, всего возможных путей 12.
полный связный граф размерности 5 и пути с посещением 3 узлов
К счастью, задавать произвольный граф полной связности в программе не нужно, так как, похоже, можно посчитать по аналитической формуле:
Как посчитать циклы в графе
полные связные графы размерности 3 и 4
полный связный граф размерности 5 и пути с посещением 3 узлов
Помогите. Как здесь найти количество циклов?
Дмитрий Мыслитель (6233) Я нашёл вот эти циклы 
Оценка количества простых циклов на графе
В ряде практических приложений возникает необходимость поиска простых циклов на графах, в связи с чем встаёт вопрос об оценке количества вычислительных операций, необходимых для этого, т.е. вычислительной сложности задачи.
Сама по себе задача перебора циклов на конкретном графе не является особенно сложной и легко реализуется средствами практически любого языка программирования, поддерживающего рекурсивные вычисления. Однако поиск методов априорной оценки вычислительных затрат переборного алгоритма, к моему удивлению, не дал вменяемых результатов. Тем не менее, достаточно простые рассуждения позволяют получить требуемую оценку, неплохо согласующуюся с тестовыми данными и позволяющую, помимо прочего, получить некоторую дополнительную информацию о структуре результатов перебора.
Формализация задачи
Итак, для определенности будем рассматривать граф 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) позволяет сделать вполне обоснованное предсказание о характерных длинах циклов на графе.
Остаётся заметить, что хотя рассуждения в статье относятся к случаю простых циклов на ориентированных графах без петель, подобные результаты могут быть получены для прочих типов графов и циклов путём аналогичных рассуждений.
Заключение
Я надеюсь, что полученные результаты заинтересуют читателя, будут кому-то полезны в его практической деятельности и, быть может, послужат толчком к дальнейшим исследованиям в этой области.
Нахождение всех циклов в графе
Есть граф, представленный списком в файле, где n — количество вершин. Необходимо найти все циклы в графе. С кода у меня пока что есть только чтение графа, чтобы было понятнее что к чему.
Совет: уточните формулировку
К сожалению, без точной формулировки задачи ответить на ваш вопрос очень сложно. Для начала, что вы ищете? Простые циклы? Элементы циклического пространства? Обычные циклы? Понимаете ли вы, что для полного графа с n вершинами размер ответа в любой из вышеперечисленных задач не меньше n! ? Такой огромный размер ответа (а, значит, и время работы) говорит о том, что с практической точки зрения задача мало полезна (для полного графа с 14 вершинами это порядка 100 миллиардов циклов). Поэтому я крайне рекомендую уточнить постановку/необходимость задачи.
Если всё же нужно решить именно эту задачу
Например, с помощью алгоритмов поиска MST можно найти все фундаментальные циклы графа. Каждый цикл в графе является линейной комбинацией (коэффициенты берутся 0 или 1, сложение — исключающее или циклов) фундаментальных циклов, поэтому, перебрав эти комбинации, и взяв только нужные вам (только связные, или только простые), вы найдёте ответ. Это далеко не самый оптимальный алгоритм ( O(2^m) , где m — число рёбер), и я не сомневаюсь, что его можно немного улучшить, если уточнить постановку задачи.