Comments 15
Учитывая, что графы зачастую являются полносвязными или около того, то для них есть более простая оценка: 1 + число_рёбер - число_узлов. Логика простая: n-1 рёбер достаточно, чтобы связать все узлы без циклов. Каждое следующее ребро добавляет 1 цикл.
Одно ребро может добавить гораздо больше, чем 1 цикл.
Каким образом?
К сожалению, в комментариях не очень удобно приводить подробные примеры, но обратите внимание на табл.1 -- в ней количества циклов определены прямым подсчетом на вполне реальных графах.
Возьмем первый попавшийся ориентированный граф из картинок в гугле:
Добавим ребро Г->Е. Сколько новых циклов образуется?
Вы видимо намекаете на вырожденные циклы, которые образуются из циклов поменьше. Такие обычно не интересны.
Не припоминаю такого термина "вырожденный цикл". В любом случае в данной статье определение цикла дано. Кроме того. Про циклы поменьше. Давайте представим граф, узлы которого образуют четырехугольник ABCD. Ребра {A->B, A->D, B->C, D->C}. Сколько циклов возникнет при добавлении ребра C->A?
Математик: ваш граф зависимостей образует 11 циклов (AA, BB, CC, DD, ABCA, ABDA, BDCB, CDAC, ABCDA, BCADB, CABDC) и может быть сериализован 24 способами (далее куча формул с факториалами). Каждый узел имеет не менее 4 и не более 4 рёбер (далее огромная таблица смежности со статистикой по каждой строке и столбцу). Граф может быть представлен на плоскости без пересечения рёбер и раскрашен не менее 4 цветами (далее доказательство на 10 страниц). Физическое моделирование методом Монте-Карло показало, что при одинаковой силе всех рёбер, наиболее оптимальное (по Русалочкину) расположение узлов - это замкнутый треугольник, внутри которого располагаются все остальные узлы (далее листинг программы на псевдоскрипте и схематическое изображение всех двух возможных конфигураций).
Инженер: у вас 3 циклические зависимости (ABD, BDC, CDA). Самые слабые зависимости (AB, BC, CD) были автоматически устранены для корректного упорядочивания ваших модулей в бандле.
Для того, чтобы присутствовали петли (простые циклы из одной вершины), необходимо, чтобы присутствовало соответствующее ребро, например, A->A, однако в списке ребер из моего примера таковых нет. Далее, возьмем еще тип некорректного цикла из вашего примера: BDCB. Для того, чтобы он существовал, необходимо ребро B->D, какового в рассматриваемом графе также не наблюдается.
То есть вас интересуют циклы подлиннее? Тогда я продолжу ваш воображаемый диалог:
Инженер: у меня есть небольшой граф из 100 вершин с 500-ми ребрами, мне надо найти самый длинный цикл на нем. Тэкс, мой супер-пупер параллельный алгоритм позволяет находить 1000 000 000 циклов в секунду, а примерное число циклов у нас... таааак... 1 + 500 - 100 ... 401. Через секунду скажу результат!
Математик: сын мой, не спеши, ты получишь свой результат примерно через 3 170 979 198 376 459 000 лет... Я, конечно, могу ошибиться на порядок-другой... Но к обеду точно не управишься!
Комментарии тоже не все одинаково интересны; тем не менее, они существуют.
Для полносвязных графов, т.е. таких, где каждая пара вершин смежна, каждое циклическое размещение вершин образует цикл, и общее количество их определяется суммированием выражения (19) по тексту статьи для K от 2 до N, что существенно больше Вашей оценки. Например, в полносвязном ориентированном графе с 10 вершинами имеется 90 ребер, и общее количество циклов составляет 1112073. Сравните с 1 + 90 - 10 = 81.
Я очень благодарен Вам за комментарий, он весьма наглядно показывает, как крупно можно ошибиться в интуитивных рассуждениях о графах и циклах на них.
Оч. хорошая статья. Эталон для статей по науке/инженерии.
Оценка количества простых циклов на графе