Нахождение цикла
Напомним, что циклом в графе $G$ называется ненулевой путь, ведущий из вершины $v$ в саму себя. Граф называют ацикличным, если в нем нет циклов.
Для нахождения цикла, рассмотрим такой альтернативные способ делать обход в глубину:
Здесь мы вместо массива used передаем в рекурсию параметр $p$, равный номеру вершины, откуда мы пришли, или $-1$, если мы начали обход в этой вершине.
Этот способ корректен только для деревьев — проверка u != p гарантирует, что мы не пойдем обратно по ребру, однако если в графе есть цикл, то мы в какой то момент вызовем dfs второй раз с одними и теми же параметрами и попадем в бесконечный цикл.
Если мы можем определять, попали ли мы в бесконечный цикл, то это ровно то, что нам нужно. Модифицируем dfs так, чтобы мы могли определять момент, когда мы входим в цикл. Для этого просто вернем массив used обратно, но будем использовать его для проверки, были ли мы когда-то в вершине, которую мы собираемся посетить — это будет означать, что цикл существует.
Если нужно восстанавливать сам цикл, то можно вместо завершения программы возвращаться из рекурсии несколько раз и выписывать вершины, пока не дойдем до той, в которой нашелся цикл.
Как и со всеми обходами, если в графе больше одной компоненты связности, или если граф ориентированный, то dfs нужно запускать несколько раз от вершин разных компонент.
Гамильтонов цикл — Теория графов
В этом уроке нам предстоит познакомиться с гамильтоновым циклом. В этом случае мы будем посещать не ребро графа, а каждую вершину и только один раз. При этом будем возвращаться в начальную точку.
Что такое гамильтонов цикл
Гамильтонов цикл в графе — это подграф и цикл, который включает в себя все вершины графа. Граф, в котором есть гамильтонов цикл, называется гамильтоновым. Гамильтонов путь — это подграф-путь, который все вершины графа:
При гамильтоновых циклах нам нужно посетить каждую вершину ровно один раз и вернуться туда, откуда начали. Некоторые ребра могут не использоваться. Нельзя сказать точно, содержит ли граф гамильтонов цикл. Даже если мы знаем, что у графа есть гамильтонов цикл, его все равно сложно найти.
Для гамильтоновых циклов есть несколько простых необходимых условий и несколько относительно простых достаточных условий, но у нас нет ничего простого и полезного, что работало бы в обоих направлениях. Найти простую и быструю проверку, которая работала бы для всех графов, практически невозможно.
Как понять, что у графа нет цикла
Если граф содержит срезанную вершину или срезанное ребро, то у него нет гамильтонова цикла. Когда срезанные вершины или ребра пересекаются, пропадает возможность вернуться, чтобы завершить цикл. Например:
На графике видно, что нет способа вернуться на другую сторону графа, когда мы пересекаем вершину
Рассмотрим следующую теорему:
Если существует некоторое подмножество
больше компонент, чем у
нет гамильтонова цикла
Например, мы можем попытаться удалить одну вершину, которая разбивает граф на два или более компонентов. Это будет вершина разреза. Или мы можем попытаться удалить две вершины, чтобы разбить граф на три или более компонентов. И так дальше по возрастанию.
Нахождение всех циклов в графе
Есть граф, представленный списком в файле, где n — количество вершин. Необходимо найти все циклы в графе. С кода у меня пока что есть только чтение графа, чтобы было понятнее что к чему.
#include #include #include using namespace std; #define FOR(i,a,b) for (int i(a), __N(b); i < __N; ++i) typedef vectorVI; typedef vector VVI; set res; void R()<> int main(int argc, char *args)< // переопределение потоков freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); // чтение графа int n, a, b; scanf("%d", &n); VVI G(n); res = set(); while (scanf("%d %d", &a, &b) != -1) < G[a].push_back(b); G[b].push_back(a); >// обработка графа > Отслеживать
51.4k 87 87 золотых знаков 267 267 серебряных знаков 508 508 бронзовых знаков
задан 18 мар 2011 в 11:17
336 3 3 серебряных знака 11 11 бронзовых знаков
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Совет: уточните формулировку
К сожалению, без точной формулировки задачи ответить на ваш вопрос очень сложно. Для начала, что вы ищете? Простые циклы? Элементы циклического пространства? Обычные циклы? Понимаете ли вы, что для полного графа с n вершинами размер ответа в любой из вышеперечисленных задач не меньше n! ? Такой огромный размер ответа (а, значит, и время работы) говорит о том, что с практической точки зрения задача мало полезна (для полного графа с 14 вершинами это порядка 100 миллиардов циклов). Поэтому я крайне рекомендую уточнить постановку/необходимость задачи.
Если всё же нужно решить именно эту задачу
Например, с помощью алгоритмов поиска MST можно найти все фундаментальные циклы графа. Каждый цикл в графе является линейной комбинацией (коэффициенты берутся 0 или 1, сложение — исключающее или циклов) фундаментальных циклов, поэтому, перебрав эти комбинации, и взяв только нужные вам (только связные, или только простые), вы найдёте ответ. Это далеко не самый оптимальный алгоритм ( O(2^m) , где m — число рёбер), и я не сомневаюсь, что его можно немного улучшить, если уточнить постановку задачи.
Как посчитать циклы в графе
rui_er → Codeforces Round 942 (Div. 1, Div. 2)
MateoCV → Codeforces Round 856 (Div. 2) Editorial
awoo → Educational Codeforces Round 165 [рейтинговый для Div. 2]
Tourist_but_newbie → IZhO 2023 help
Termodinamico → We say thank you to MikeMirzayanov
Black_Panda → ATCODER account issue
maomao90 → Simple and flexible base change algorithm for communication problems
MikeMirzayanov → Часто задаваемые вопросы
violentdoc → Who is rainboy?
akzytr → Pleasant pairs -> O(n log n)
sberens → Daily Codeforces Problem Email
EnDeRBeaT → [Tool] Graph Debugger
sdyakonov → Make proofs
atcoder_official → AtCoder Beginner Contest 351 Announcement
vovuh → Разбор Codeforces Round #640 (Div. 4)
ooaa → Codeforces Round #922 (Div. 2) Разбор
ICPCNews → The 2023 ICPC World Finals Luxor
jdurie → Codeforces Round #941 (Div. 1, Div. 2) Editorial
D0OMoP → Hidden Edge cases
BluoCaroot → problem with testlib.h readDouble
Kolyanchick → До скорых встреч
FedeNQ → Teams going to ICPC WF 2022 (Egypt 2023) — WIP List
FedeNQ → Teams going to ICPC WF 2023 (Egypt 2023, 2nd final) — WIP List
h ehezhou → 2024-The 6th Turing Cup Tournament
PolymathFaisal → How to use Codeforces as a new Bie?
Блог пользователя gofkane
Как найти циклы в графе
Автор gofkane, 11 лет назад ,
Задан неориентированный граф. Найти количество путей проходящие через k вершин, начинающиеся и заканчивающиеся в одной и той же вершине, но не проходящие два раза через любую другую вершину.
Я пробовал написать поиск в глубину, но у меня находилось больше путей, т.к. у меня получилось что 1-2-3-4-1 и 1-4-3-2-1 — разные пути.
Комментарии (20)
Показать архивные | Написать комментарий?
11 лет назад , # |
← Rev. 2 → 
0 
Вероятно, каждый путь получился посчитан одинаковое количество раз (например, два раза или 2k раз). В этом случае можно просто поделить ответ на это число.
11 лет назад , # ^ |
Да, спасибо. Вот здесь задача и моё решение (писалось на PascalABC): http://pastebin.com/9XCpcqW9 1) Если запустить dfs не циклом из всех а один раз из первой то res = 6 (Ответ res/2) 2) Где в условие сказано что нужно искать пути из первой точки? 3) Верное ли решение? Есть ли более оптимальное?
11 лет назад , # ^ |
← Rev. 3 → 0
Честно говоря, я не верю в это решение, мне кажется, поиск в глубину не найдет все циклы. Хотя могу и ошибаться. Есть 100% решение за O(n(n-1)(n-2)(n-3). (n-k+1)*k)=O(k*n^k): перебрать все возможные множества из k вершин и проверить, являются ли они циклами. Тогда ответ надо будет поделить на 2*k, ибо каждый цикл будет посчитан именно столько раз. Но при n=300 и k=4 это будет очень много итераций, так что, думаю, есть и более простое решение :\
11 лет назад , # ^ |
Логика решения такова — идём из вершины(или из всех вершин,что я и делал) по соседям(записав вершину,с которой начали), изменяя длину пути и записывая каждую вершину в сет, чтобы проверить не были ли мы на данной вершине. Как только длина достигает нужного значения — проверяем куда мы пришли. Этот алгоритм переберёт (должен перебрать, т.к. я впервые написал алгоритм на графах) все пути, начинающиеся в вершине,из которой он был запущен. p.s. Задача с муниципального этапа РОИ. Поэтому вопрос номер 2 (выше) всё же актуален.
11 лет назад , # ^ |
Можно по идее сделать так: перебираем все пары вершин. Пересекаем их списки смежности. Считаем количество вершин в пересечении. К ответу прибавляем x * (x — 1) / 2. Итого: алгоритм за N^3. Будет быстрее если списки смежности хранить как битовую маску, тогда пересечение можно сделать за N / 32, а подсчет битов в числе за 2 операции. В конце ответ надо будет поделить на что-то еще, так как все циклы учтутся одинаковое количество раз.
11 лет назад , # ^ |
А разве, если k = n, это не задача о гамильтоновом цикле? 🙂 Не совсем в явном виде, конечно. Но, если мы решим данную, мы узнаем, существует ли в графе гамильтонов цикл.
11 лет назад , # ^ |
Burunduk1: Как следует действовать если k<>n ?
11 лет назад , # ^ |
← Rev. 3 → 0
Я так и не понял, что у Вас не получается. DFS — правильная идея. Gassa уже сказал, что, чтобы пути не учитывались несколько раз, нужно поделить на 2k. Запускать DFS нужно, конечно, от всех вершин по очереди. DFS должен перед выходом из рекурсии снимать пометку с вершины. P.S. Задача коротко формулируется так: кол-во простых циклов длины k в неориентированном графе. UPD1: О! В ссылке оказывается другое условие задачи 🙂 Да, для 4-х все несколько проще. FOR FOR FOR FOR ? 🙂 UPD2: Видимо, хорошим тоном было бы с самого начала дать ссылку на условие задача. Например, оказывается, N < 300.
11 лет назад , # ^ |
O(n^4), при n=300 кол-во операций более 8,1*10^9 — такое решение должно пройти? Ссылки на задачу у меня самого не было. Условие изменил — хотел узнать решение для более общего случая. Но у меня видимо проблема ещё и с пониманием задачи. У нас же есть пути (тест из условия): 1-2-3-4-1 1-4-3-2-1 1-4-2-3-1 3-2-1-4-3 и т.д. А правильный ответ — 3. Что я неправильно понимаю?
11 лет назад , # ^ |
1) Если аккуратно писать, там не N 4 , а N 4 / 4 . Так что может зайти 🙂 2) ValenKof уже сказал, как сделать O(N 3 ) . Попробую объяснить подробнее. Цикл = A-B-C-D-A. Зафиксируем A и C. Пока N 2 . Теперь B и D — любые две вершины, которые соединены и с A, и с C. Нужно найти кол-во таких вершин. Если у нас есть матрица смежности, нас интересует кол-во таких i: g[A,i] and g[C,i]. Теперь ок?
11 лет назад , # ^ |
Выше был код тс с вбитым условием задачи. В условии K = 4. Я и рассказал решение для K = 4.
11 лет назад , # ^ |
Извиняюсь, я как-то не догадался, что автор под ссылкой указал другое условие.
10 лет назад , # ^ |
← Rev. 2 → 0
Wackloner, можешь подробнее объяснить, как для данных 4-ёх вершин за O(k) определить, что они образуют цикл?
11 лет назад , # |
← Rev. 2 → 0
Я могу ошибаться, но разве нельзя взять алгоритм отсюда и посчитать количество путей длиной k от i-той вершины до нее самой?
11 лет назад , # ^ |
но не проходящие два раза через любую другую вершину
Т.е. нужно кол-во простых циклов (путей). По ссылке кол-во непростых циклов (путей).
11 лет назад , # ^ |
Вроде как непростой цикл длины 4 через вершину v — это содержащий петли(которые можно нафиг выкинуть вначале) или состоящий из двух циклов длины 2, а это что-то около deg(v)^2
11 лет назад , # ^ |
и посчитать количество путей длиной k
Насколько я понял, BekzhanKassenov имел в виду случай произвольного k.
11 лет назад , # ^ |
Ну да. Только теперь прочитал что k == 4. Но ведь n^4 не проходит?
11 лет назад , # ^ |
Думаю, можно по аналогии выкидывать повторения для всех разложений k=mp. Но это уже не полином, кажется.
11 лет назад , # |
какой-то хаотичный пост. каждый что-то отвечает но все подразумевают разные задачи, где-то похоже присутсвовал код с условием и ссылкой, но я не обнаружил его.
полагаю речь идет об этой задаче ссылку на которую я скопировал из сообщения выше от Burunduk1. Я думаю можно найти количество циклов(не обязательно простых) длины 4 каким-нибудь тупым способом, например умножением матрицы смежности нужное число раз. затем порисовать всевозможные непростые циклы, какие они вообще бывают. найти для каждой вершины какие и в каком количестве присутствуют. это можно сделать за O(n^3) т.к. в непростых циклах число различных вершин не более 3-х, а количество типов константное (вроде 2, но лень думать). Теперь вычитаем одно из другого, и получаем количество простых циклов.