Формулы для вычисления количества простых циклов в графе

[inek82]

Подскажите, известны ли формулы для быстрого и точного вычисления количества простых циклов длины "Х" в произвольном плоском графе или алгоритмы для их вычисления?
Знаю, что есть исследования и результаты (по упоминаниям из публикаций), но преимущественно они связаны с приближёнными или вероятностными вычислениями. Помогите найти ссылки на источники по теме или напишите сами формулы.
Спасибо за помощь.

[mihaild]

Возьмите $X$ равным числу вершин и погуглите задачу коммивояжера для планарных (плоский - это же планарный?) графов.

[Geen]

inek82 в сообщении #1587058 писал(а):

количества простых циклов длины "Х"

А почему Вы думаете, что ответ "однозначен"?

[inek82]

Geen в сообщении #1587102 писал(а):

inek82 в сообщении #1587058 писал(а):

количества простых циклов длины "Х"

А почему Вы думаете, что ответ "однозначен"?

Может нужно сформулировать точнее: явная (аналитическая или в другой форме) формула (или метод) для вычисления количества циклов в плоском графе. Циклы считаются без учёта циклической перестановки самой замкнутой цепи (т.е. 12345 и 34512 - это один и тот же цикл).
Находил информацию о формулах выведенных для длин 3, 4, 5 (отсылка была к некой публикации Харари, которую в инете найти не смог, если есть у кого буду благодарен за ссылку), есть ещё приближённые методы и основанные на теории вероятностей.

Проблема в том, что материалов по теме мало, не знаю насколько она разработана...

-- 03.04.2023, 20:37 --

mihaild в сообщении #1587068 писал(а):

Возьмите $X$ равным числу вершин и погуглите задачу коммивояжера для планарных (плоский - это же планарный?) графов.

не очень понимаю, какая связь? задача коммивояжёра разве не про поиск оптимальных маршрутов?

[mihaild]

Да, погорячился, у вас же невзвешенный граф. Ну всё равно - существование гамильтонова пути в планарном графе тоже NP-трудно.

[sqribner48]

inek82
Мне кажется, что эти формулы известны. Эти формулы можно найти в статье А.Н.Воропаев. "Вывод явных формул для подсчёта циклов фиксированной длины в неориентированных графах" Информационные процессы, Том 11, № 1, 2011, стр. 90–113. (вот и ссылка http://www.jip.ru/2011/90-113-2011.pdf)
Есть и еще полезные источники:
1. В. Л. Арлазаров, А. В. У сков, И. А. Фараджев. Алгоритм нахождения всех простых циклов в ориентированном графе.— В кн.: Исследования по дискретной математике. М., «Наука», 1973, с. 178—183.
2. А. Кофман. Введение в прикладную комбинаторику. М. Наука, 1975.
Посмотрите там параграф 44 "Перечисление элементарных контуров " в главе IV "Перечисление"

[maxal]

inek82 в сообщении #1587058 писал(а):

Подскажите, известны ли формулы для быстрого и точного вычисления количества простых циклов длины "Х" в произвольном плоском графе или алгоритмы для их вычисления?
Знаю, что есть исследования и результаты (по упоминаниям из публикаций), но преимущественно они связаны с приближёнными или вероятностными вычислениями. Помогите найти ссылки на источники по теме или напишите сами формулы.
Спасибо за помощь.

В моей статье (раздел 4) есть кое-что на эту тему: https://arxiv.org/abs/1602.01396