Поиск всех циклов в неориентированных графах
Мне нужен рабочий алгоритм для поиска всех простых циклов в неориентированном графе. Я знаю, что стоимость может быть экспоненциальной, а проблема является NP-полной, но я собираюсь использовать ее в небольшом графе (до 20-30 вершин), а количество циклов невелико.
После долгих исследований (в основном здесь) у меня все еще нет рабочего подхода. Вот краткое изложение моего поиска:
Поиск всех циклов в ориентированном графе -> находит циклы только в ориентированном графики
Единственный ответ, который я нашел, который подходит к моей проблеме, таков:
Кажется, что найти базовый набор циклов и выполнить их с помощью XOR можно. Найти базовый набор циклов легко, но я не понимаю, как их объединить, чтобы получить все циклы на графике .
Ответы (11)
Для неориентированного графа стандартный подход состоит в том, чтобы искать так называемую базу цикла: набор простых циклов, из которых можно генерировать посредством комбинаций все остальные циклы. Это не обязательно все простые циклы на графике. Рассмотрим, например, следующий график:
Здесь есть 3 простых цикла: A-B-C-A, B-C-D-B и A-B-D-C-A. Однако вы можете взять каждые 2 из них за основу и получить 3-й как комбинацию из 2-х. Это существенное отличие от ориентированных графов, где нельзя комбинировать так свободно циклы из-за необходимости соблюдать направление ребер.
Стандартный базовый алгоритм для поиска базы цикла для неориентированного графа таков: построить остовное дерево, а затем для каждого ребра, которое не является частью дерева, построить цикл из этого ребра и некоторых ребер на дереве. Такой цикл должен существовать, потому что в противном случае ребро было бы частью дерева.
Например, одно из возможных покрывающих деревьев для приведенного выше примера графа следующее:
Два ребра не в дереве — это B-C и C-D. И соответствующие простые циклы — это A-B-C-A и A-B-D-C-A.
Вы также можете построить следующее связующее дерево:
И для этого остовного дерева простыми циклами будут A-B-C-A и B-C-D-B.
Базовый алгоритм можно доработать по-разному. Насколько мне известно, лучшее уточнение принадлежит Патону (К. Патон, Алгоритм поиска фундаментального набора циклов для неориентированного линейного графа, Comm. ACM 12 (1969), стр. 514-518). Реализация с открытым исходным кодом на Java доступна здесь: http://code.google.com/p/niographs/.
Я должен был упомянуть, как вы комбинируете простые циклы из базы цикла, чтобы сформировать новые простые циклы. Вы начинаете с перечисления в любом (но фиксированном в дальнейшем) порядке всех ребер графа. Затем вы представляете циклы последовательностями нулей и единиц, помещая единицы в положения ребер, которые принадлежат циклу, и нули в положениях ребер, которые не являются частью цикла. Затем вы выполняете побитовое исключающее ИЛИ (XOR) последовательностей. Причина, по которой вы выполняете XOR, заключается в том, что вы хотите исключить ребра, принадлежащие обоим циклам, и, таким образом, сделать комбинированный цикл непростым. Вам также необходимо проверить, что 2 цикла имеют НЕКОТОРЫЕ общие ребра, проверив, что побитовое И последовательностей не все нули. В противном случае результатом XOR будет 2 непересекающихся цикла, а не новый простой цикл.
Вот пример приведенного выше примера графика:
Начнем с перечисления ребер: ((AB), (AC), (BC), (BD), (CD)). Тогда простые циклы A-B-C-A, B-D-C-B и A-B-D-C-A представлены как (1, 1, 1, 0, 0), (0, 0, 1, 1, 1) и (1, 1, 0, 1, 1). Теперь мы можем, например, выполнить XOR A-B-C-A с B-D-C-B, и результат будет (1, 1, 0, 1, 1), что в точности совпадает с A-B-D-C-A. Или мы можем выполнить XOR A-B-C-A и A-B-D-C-A с результатом (0, 0, 1, 1, 1). Что в точности B-D-C-B.
Учитывая базовый цикл, вы можете обнаружить все простые циклы, исследуя все возможные комбинации двух или более различных базовых циклов. Более подробно процедура описана здесь: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf на странице 14.
Для полноты картины я бы заметил, что использование алгоритмов для поиска всех простых циклов ориентированного графа кажется возможным (и неэффективным). Каждое ребро неориентированного графа можно заменить двумя направленными ребрами, идущими в противоположных направлениях. Тогда должны работать алгоритмы для ориентированных графов. Для каждого ребра неориентированного графа будет 1 «ложный» 2-узловой цикл, который нужно будет игнорировать, и будет версия по часовой стрелке и против часовой стрелки для каждого простого цикла неориентированного графа. Реализацию с открытым исходным кодом на Java алгоритмов для поиска всех циклов в ориентированном графе можно найти по уже цитированной ссылке.
Оценка количества простых циклов на графе
В ряде практических приложений возникает необходимость поиска простых циклов на графах, в связи с чем встаёт вопрос об оценке количества вычислительных операций, необходимых для этого, т.е. вычислительной сложности задачи.
Сама по себе задача перебора циклов на конкретном графе не является особенно сложной и легко реализуется средствами практически любого языка программирования, поддерживающего рекурсивные вычисления. Однако поиск методов априорной оценки вычислительных затрат переборного алгоритма, к моему удивлению, не дал вменяемых результатов. Тем не менее, достаточно простые рассуждения позволяют получить требуемую оценку, неплохо согласующуюся с тестовыми данными и позволяющую, помимо прочего, получить некоторую дополнительную информацию о структуре результатов перебора.
Формализация задачи
Итак, для определенности будем рассматривать граф 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) позволяет сделать вполне обоснованное предсказание о характерных длинах циклов на графе.
Остаётся заметить, что хотя рассуждения в статье относятся к случаю простых циклов на ориентированных графах без петель, подобные результаты могут быть получены для прочих типов графов и циклов путём аналогичных рассуждений.
Заключение
Я надеюсь, что полученные результаты заинтересуют читателя, будут кому-то полезны в его практической деятельности и, быть может, послужат толчком к дальнейшим исследованиям в этой области.
Как посчитать циклы в графе
Задача — найти в произвольном неориентированном графе количество циклов, не связанных с другими частями графа.
Искомый цикл состоит минимум из двух вершин и не имеет «лишних» рёбер, то есть, представляет собой кольцо вида 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 узлов
К счастью, задавать произвольный граф полной связности в программе не нужно, так как, похоже, можно посчитать по аналитической формуле:
Нахождение цикла
Напомним, что циклом в графе $G$ называется ненулевой путь, ведущий из вершины $v$ в саму себя. Граф называют ацикличным, если в нем нет циклов.
Для нахождения цикла, рассмотрим такой альтернативные способ делать обход в глубину:
Здесь мы вместо массива used передаем в рекурсию параметр $p$, равный номеру вершины, откуда мы пришли, или $-1$, если мы начали обход в этой вершине.
Этот способ корректен только для деревьев — проверка u != p гарантирует, что мы не пойдем обратно по ребру, однако если в графе есть цикл, то мы в какой то момент вызовем dfs второй раз с одними и теми же параметрами и попадем в бесконечный цикл.
Если мы можем определять, попали ли мы в бесконечный цикл, то это ровно то, что нам нужно. Модифицируем dfs так, чтобы мы могли определять момент, когда мы входим в цикл. Для этого просто вернем массив used обратно, но будем использовать его для проверки, были ли мы когда-то в вершине, которую мы собираемся посетить — это будет означать, что цикл существует.
Если нужно восстанавливать сам цикл, то можно вместо завершения программы возвращаться из рекурсии несколько раз и выписывать вершины, пока не дойдем до той, в которой нашелся цикл.
Как и со всеми обходами, если в графе больше одной компоненты связности, или если граф ориентированный, то dfs нужно запускать несколько раз от вершин разных компонент.
Помогите с информатикой и количеством циклов в графе
Помогите. Как здесь найти количество циклов? 
Задание 1.
Пусть у вершин этого квадрата будут названия A, B, C, D. В его центре вершины нету ��
1-й цикл: фигура ABCD — собственно, сам квадрат;
ещё циклы: это треугольники ABC, ABD, BCD, CDA;
ещё — в виде песочных часов: ABDC, ADBC;
Итого: 7 циклов
Во втором задании — те же циклы. В нём отличие только в том, что боковые грани квадрата разделили ещё одной вершиной. Ответ: 7 циклов.
Задание 3
Большой квадрат; маленький квадрат; 4 четырёхугольника между ними; 4 фигуры, образованные из предыдущих четырёхугольников, если у рядом расположенных убрать общую грань; ещё 4 фигуры, образованные из предыдущих, если у них убрать 2 грани, общих с внутренним квадратом. Дальше — сложнее. Пусть вершины большого квадрата будут носить названия A, B, C, D, маленького A1, B1, C1, D1. Тогда вот циклы: 4 фигуры, которые можно получить, если поочерёдно «вырезать» 4-хугольники, расположенные между внешним и внутренним квадратом, например ADCBB1A1; 4 фигуры, которые можно получить, если «вырезать» в 4-х предыдущих ещё и маленький квадрат, например: ADCBB1C1D1A1
Итог: 22
Устал �� 4-е задание не буду делать)))
Дмитрий Мыслитель (6233) Я нашёл вот эти циклы 
Помогите с информатикой и количеством циклов в графе
Помогите. Как здесь найти количество циклов?
Задание 1.
Пусть у вершин этого квадрата будут названия A, B, C, D. В его центре вершины нету 🙂
1-й цикл: фигура ABCD — собственно, сам квадрат;
ещё циклы: это треугольники ABC, ABD, BCD, CDA;
ещё — в виде песочных часов: ABDC, ADBC;
Итого: 7 циклов
Во втором задании — те же циклы. В нём отличие только в том, что боковые грани квадрата разделили ещё одной вершиной. Ответ: 7 циклов.
Задание 3
Большой квадрат; маленький квадрат; 4 четырёхугольника между ними; 4 фигуры, образованные из предыдущих четырёхугольников, если у рядом расположенных убрать общую грань; ещё 4 фигуры, образованные из предыдущих, если у них убрать 2 грани, общих с внутренним квадратом. Дальше — сложнее. Пусть вершины большого квадрата будут носить названия A, B, C, D, маленького A1, B1, C1, D1. Тогда вот циклы: 4 фигуры, которые можно получить, если поочерёдно «вырезать» 4-хугольники, расположенные между внешним и внутренним квадратом, например ADCBB1A1; 4 фигуры, которые можно получить, если «вырезать» в 4-х предыдущих ещё и маленький квадрат, например: ADCBB1C1D1A1
Итог: 22
Устал 🙂 4-е задание не буду делать)))
Дмитрий Филюшкин Мудрец (11559) Я нашёл вот эти циклы