Как посчитать циклы в графе
Блог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 узлов
К счастью, задавать произвольный граф полной связности в программе не нужно, так как, похоже, можно посчитать по аналитической формуле:
Нахождение цикла
Напомним, что циклом в графе $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) Я нашёл вот эти циклы 