Комментарии 11
Учитывая, что графы зачастую являются полносвязными или около того, то для них есть более простая оценка: 1 + число_рёбер - число_узлов. Логика простая: n-1 рёбер достаточно, чтобы связать все узлы без циклов. Каждое следующее ребро добавляет 1 цикл.
Одно ребро может добавить гораздо больше, чем 1 цикл.
Каким образом?
К сожалению, в комментариях не очень удобно приводить подробные примеры, но обратите внимание на табл.1 -- в ней количества циклов определены прямым подсчетом на вполне реальных графах.
Возьмем первый попавшийся ориентированный граф из картинок в гугле:
Добавим ребро Г->Е. Сколько новых циклов образуется?
Для полносвязных графов, т.е. таких, где каждая пара вершин смежна, каждое циклическое размещение вершин образует цикл, и общее количество их определяется суммированием выражения (19) по тексту статьи для K от 2 до N, что существенно больше Вашей оценки. Например, в полносвязном ориентированном графе с 10 вершинами имеется 90 ребер, и общее количество циклов составляет 1112073. Сравните с 1 + 90 - 10 = 81.
Я очень благодарен Вам за комментарий, он весьма наглядно показывает, как крупно можно ошибиться в интуитивных рассуждениях о графах и циклах на них.
Оч. хорошая статья. Эталон для статей по науке/инженерии.
Оценка количества простых циклов на графе