То есть вас интересуют циклы подлиннее? Тогда я продолжу ваш воображаемый диалог:
Инженер: у меня есть небольшой граф из 100 вершин с 500-ми ребрами, мне надо найти самый длинный цикл на нем. Тэкс, мой супер-пупер параллельный алгоритм позволяет находить 1000 000 000 циклов в секунду, а примерное число циклов у нас... таааак... 1 + 500 - 100 ... 401. Через секунду скажу результат!
Математик: сын мой, не спеши, ты получишь свой результат примерно через 3 170 979 198 376 459 000 лет... Я, конечно, могу ошибиться на порядок-другой... Но к обеду точно не управишься!
К сожалению, в комментариях не очень удобно приводить подробные примеры, но обратите внимание на табл.1 -- в ней количества циклов определены прямым подсчетом на вполне реальных графах.
Для полносвязных графов, т.е. таких, где каждая пара вершин смежна, каждое циклическое размещение вершин образует цикл, и общее количество их определяется суммированием выражения (19) по тексту статьи для K от 2 до N, что существенно больше Вашей оценки. Например, в полносвязном ориентированном графе с 10 вершинами имеется 90 ребер, и общее количество циклов составляет 1112073. Сравните с 1 + 90 - 10 = 81. Я очень благодарен Вам за комментарий, он весьма наглядно показывает, как крупно можно ошибиться в интуитивных рассуждениях о графах и циклах на них.
То есть вас интересуют циклы подлиннее? Тогда я продолжу ваш воображаемый диалог:
Инженер: у меня есть небольшой граф из 100 вершин с 500-ми ребрами, мне надо найти самый длинный цикл на нем. Тэкс, мой супер-пупер параллельный алгоритм позволяет находить 1000 000 000 циклов в секунду, а примерное число циклов у нас... таааак... 1 + 500 - 100 ... 401. Через секунду скажу результат!
Математик: сын мой, не спеши, ты получишь свой результат примерно через 3 170 979 198 376 459 000 лет... Я, конечно, могу ошибиться на порядок-другой... Но к обеду точно не управишься!
Интереснейшая тема, и замечательно раскрыта в статье. Спасибо!
Комментарии тоже не все одинаково интересны; тем не менее, они существуют.
Весьма признателен за столь лестный отзыв. Спасибо!
К сожалению, в комментариях не очень удобно приводить подробные примеры, но обратите внимание на табл.1 -- в ней количества циклов определены прямым подсчетом на вполне реальных графах.
Для полносвязных графов, т.е. таких, где каждая пара вершин смежна, каждое циклическое размещение вершин образует цикл, и общее количество их определяется суммированием выражения (19) по тексту статьи для K от 2 до N, что существенно больше Вашей оценки. Например, в полносвязном ориентированном графе с 10 вершинами имеется 90 ребер, и общее количество циклов составляет 1112073. Сравните с 1 + 90 - 10 = 81.
Я очень благодарен Вам за комментарий, он весьма наглядно показывает, как крупно можно ошибиться в интуитивных рассуждениях о графах и циклах на них.
std::function<int(int)> l = [](int){ return 0; };
https://github.com/trustwallet/wallet-core только что собрал )) без малейшего бубна