Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ 1 сообщение ] |
|
Автор | Сообщение | |
---|---|---|
konan-san |
|
|
Прошу Вас дать мне совет в решении следующей проблемы: Есть орграф с циклами. В нем заданы две произвольные вершины A и B. Нужно найти количество всевозможных путей не содержащих циклов из вершины A в вершину B. Как это сделать за полиномиальное время, т.е. не прибегая к полному перебору. Либо если это NP-полная задача - то почему. У меня есть следующие идеи: 1) Подсчитать количество путей вообще - можно возведением матрицы смежности в степень. 2) Подсчитать количество циклов в графе - штука пока что для меня непонятная. По идее это как-то делается на основе фундаментальной системы циклов (типа суммы величин всевозможных сочетаний элементов из этой системы). Но как тогда подсчитать количество путей с циклами в графе (причём считая, что цикл обходится лишь один раз, т.е. не учитывая пути с кратными циклами)? P.S. Возможно это дурацкий вопрос, который решили уже 100500 лет назад. Прошу не судить строго. |
||
Вернуться к началу | ||
[ 1 сообщение ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Определить количество путей | 3 |
139 |
13 дек 2020, 23:57 |
|
Посчитать максимальное количество рёбер в графе
в форуме Начала анализа и Другие разделы школьной математики |
0 |
180 |
02 июл 2022, 20:14 |
|
Дерево - связный граф без циклов, а не что-то другое
в форуме Начала анализа и Другие разделы школьной математики |
3 |
268 |
16 окт 2022, 16:24 |
|
Имеется ли алгоритм поиска всех элементарных циклов графа?
в форуме Информатика и Компьютерные науки |
0 |
233 |
03 июл 2021, 21:53 |
|
Поиск путей | 8 |
659 |
26 апр 2015, 17:33 |
|
Поиск путей | 1 |
140 |
07 фев 2024, 00:43 |
|
Число путей в сети | 6 |
414 |
14 ноя 2018, 18:58 |
|
Число путей ладьи из угла в угол на шахматной доске | 14 |
1480 |
29 апр 2018, 21:50 |
|
Поиск всех путей от одного узла графа к другому | 3 |
302 |
02 авг 2017, 20:28 |
|
Поток на графе | 0 |
216 |
16 окт 2017, 15:46 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 20 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |