Про простые циклы в орграфе , алгоритм, структуры данных, сложность

[FasterHarder]

Всем хай! Сходу к делу!
А дело касается простых циклов в орграфе.

Вот есть такое определение орцикла ( поскольку граф ор, то и все циклы в нем тоже ор автоматом вроде ) по Вики:
Ориентированный цикл в орграфе — это последовательность вершин, начинающаяся и завершающаяся в той же самой вершине, и в этой последовательности для любых двух последовательных вершин существует дуга из более ранней в более позднюю.
* но это вроде определение не про простой цикл на 100%, а просто про цикл

А простой цикл по Вики:
Другой тип циклов, иногда называемых простыми циклами, — это замкнутые обходы без повторного прохода по ребру или посещения вершины дважды, за исключением начальной и конечной вершин.
* и дается пометка, что для орграфа такое определение простого цикла вполне справедливо

============================================================

У меня была задача найти ВСЕ простые циклы в заданном орграфе. Потратив колоссальное количество времени на исследование, закодировал программу, которая находит все простые циклы ( причем в лексикографическом порядке по меткам вершин ), вот пример результата:

Прикреплённая картинка

Кстати, как я понял, циклы a-b-c-a, b-c-a-c и т.п. ТОЖДЕСТВЕННЫ, т е дубликатные и следует оставить ЛЮБОЙ из них, т к остальные можно получить "сдвигом", так сказать. Или нет? И это считаются разные циклы??

Например, вот такой орграф ( специально на дугах, чтобы подчеркнуть, что это орграф ):

Прикреплённая картинка

Сколько здесь простых циклов, состоящие из 3 вершин?
1. a - b - c - a
2. b - c - a - b
3. c - a - b - c
4. a - c - b - a
5. c - b - a - c
6. b - a - c - b

по факту ОНИ ведь все дубликаты и следует оставить ЛЮБОЙ из них?

=================================================================

Но на одном англосайте нашел одну занимательную картинку, которая заставила меня задуматься ( внезапно!)) ), а правильно ли я вообще все понял и сделал. ВОт эта картинка с пояснением:

Прикреплённая картинка

Как я понял, там поясняется, почему цикл 1 - 2 - 3 - 4 - 1 не является ПРОСТЫМ, т к он "распадется" на другие, более "простые" циклы. Но, разве цикл 1 - 2 - 3 - 4 - 1 противоречит определению простого цикла?? Все ребра различные, все вершины различные кроме первой и последней.
У меня была такая мысль, что при построении простого цикла на каждой итерации любая вершина стремится замкнуть цикл и на этом как бы цикл построен, но это не соот-ет определению как бы вроде.

Проясните плз ситуацию по этим простым циклам...

[Akina]

Цитата FasterHarder @ 23.12.23, 04:06

по факту ОНИ ведь все дубликаты и следует оставить ЛЮБОЙ из них?

Обычно "основным" считают тот цикл, который начинается (и заканчивается соответственно) на вершине этого цикла с минимальным из всех номеров вершин номером.

Цитата FasterHarder @ 23.12.23, 04:06

ВОт эта картинка с пояснением

Это неориентированный граф. Введи ориентацию - и выяснится, что нужны два разнонаправленных ребра между 1 и 3 вершинами. А это уже будет немножко не "распадаются".

Цитата FasterHarder @ 23.12.23, 04:06

Проясните плз ситуацию по этим простым циклам...

Простым обычно называется несамопересекающийся цикл. Иногда считают, что в графе есть только один простой цикл - и тогда из всех имеющихся им объявляют либо самый короткий, либо первый лексикографически - кто во что горазд.

---

Представь себе неориентированный граф. Вершины: 1 (0,0), 2 (0,2), 3 (1,1), 4 (2, 0), 5 (2,2), рёбра 1-2, 1-3, 2-3, 3-4, 3-5, 4-5.

Имеем 4 цикла:

1-2-3-1
3-4-5-3
1-2-3-4-5-3-1
1-2-3-5-4-3-1

Первые два цикла - простые.
Вторые два цикла - не простые, ибо кроме начальной вершины 1 дважды посещается вершина 3.

И да, моя трактовка не совпадает с трактовкой на "одном англосайте".

[FasterHarder]

Цитата Akina @ 23.12.23, 11:24

Обычно "основным" считают тот цикл, который начинается (и заканчивается соответственно) на вершине этого цикла с минимальным из всех номеров вершин номером.

Хорошо, тут все понятно. У меня в прожке именно так и реализовано, т е из всех дубликатов выбирается самый лексикографический.

Цитата Akina @ 23.12.23, 11:24

Это неориентированный граф. Введи ориентацию - и выяснится, что нужны два разнонаправленных ребра между 1 и 3 вершинами. А это уже будет немножко не "распадаются".

ну, ребро по своей сути, ведь равносильна двум дугам.
смотрю на этот неорграф, как на орграф и вроде все то же самое)

Цитата Akina @ 23.12.23, 11:24

Вторые два цикла - не простые, ибо кроме начальной вершины 1 дважды посещается вершина 3.

это я вроде понимаю. Называется замкнутым обходом.

Цитата Akina @ 23.12.23, 11:24

И да, моя трактовка не совпадает с трактовкой на "одном англосайте".

+1

Добавлено 23.12.23, 14:03
В своей программке, чтобы находить циклы-дубликаты, смотрю ТОЛЬКО на состав вершин и мне все равно, в каком порядке они линкуются.

А какова верхняя оценка простых циклов в орграфе?

Например, N = 5
циклов длиной 5 вершин: 1 * 5! циклов, причем только 1 реальный, а остальные дубликаты
циклов длиной 4 вершины: 5 * 4! циклов, причем только 5 реальных, а остальные дубликаты
циклов длиной 3 вершины: 10 * 3! циклов, причем только 10 реальных, а остальные дубликаты
циклов длиной 2 вершины: 10 * 2! циклов, причем только 10 реальных, а остальные дубликат

Итого, в орграфе, состоящем из 5 вершин МАКСИМАЛЬНО может быть простых циклов ( без дубликатов ): 1 + 5 + 10 + 10 = 26 шт.
А общее кол-во циклов: 120 + 120 + 60 + 20 = 320 шт.
Т е львиную долю занимать могут циклы-дубликаты, поэтому нужен эффективный алгоритм фильтрации дубликатов...

Сообщение отредактировано: FasterHarder - 23.12.23, 14:03

[Akina]

Цитата FasterHarder @ 23.12.23, 13:09

нужен эффективный алгоритм фильтрации дубликатов...

Нормализация. Любой цикл можно вращать - вот и вращаем до минимальной вершины. Программно - ну, например, удвоение, поиск минимального элемента, взятие подстроки.

[FasterHarder]

Цитата Akina @ 23.12.23, 17:40

Нормализация. Любой цикл можно вращать - вот и вращаем до минимальной вершины. Программно - ну, например, удвоение, поиск минимального элемента, взятие подстроки.

т е ты намекаешь на то, что, например, есть циклы:
1. 0 - 1 - 3 - 4
2. 3 - 4 - 0 - 1

то 2ой цикл достаточно "прокрутить" влево на 2 вершины и тогда они совпадут?
но сдается мне, что может быть такой вариант:
1. 0 - 1 - 3 - 4
2. 3 - 0 - 4 - 1

т е состав вершин ОДИНАКОВЫЙ, а линки разные и тогда при вращении не совпадут...

возможно, ты совсем другое имел в виду.
=========================================

у меня сейчас реализована фильтрация дубликатов через хеш-функцию на целых числах. Подсчет суммы вершин - номер слота в хеш-таблице. Каждой вершине соот-ет число из последовательности 2^i. Их сумма - ключ хеш-функции. Это сумма будет одинаковой ТОЛЬКО для одного и того же набора вершин. Минусы в том, что приходится находить 2 суммы ( хотя там циклы быстрые)) ) + хеш-таблица сильно разряженная, т к 2^i растет оч. быстро...

[Akina]

Цитата FasterHarder @ 23.12.23, 18:05

состав вершин ОДИНАКОВЫЙ, а линки разные и тогда при вращении не совпадут...

В случае неориентированного графа минимальным считается цикл от минимального в цикле числа в направлении минимального из его соседей. То есть из всех "дублей" выбирается лексикографически минимальный. Соответственно после нахождения минимального в текущем направлении обхода цикл проверяется и при необходимости реверсируется.

Сообщение отредактировано: Akina - 24.12.23, 09:14