Rzhepish
@Rzhepish

Алгоритм Боржа для перебора простых путей на графе

В рамках работы над курсачом нужно узнать, что это есть. Поисковики хором предлагают искать «Бержа» вместо «Боржа».
В книге К.Бержа «Теория графов и ее применения» непосредственно этот вопрос не затрагивается. Возможно, следует искать в более поздних публикациях.
Может кто-то подскажет, где можно найти подробное описание алгоритма?
  • Вопрос задан
  • 3841 просмотр
Решения вопроса 1
@atomicus
Не слышал о таком алгоритме. И для описанной задачи он вряд ли существует. Дело в том, что перебор всех простых путей (в которых ни одна вершина не встречается дважды) между любыми двумя вершинами в графе общего вида является NP-полной задачей. Кроме метода грубой силы решения пока не найдено.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Nostr
@Nostr
Можно посмотреть тут, если подойдет www.e-maxx.ru/algo/
Но не факт, что там есть именно тот алгоритм, который вы ищете
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы