Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Количество путей без циклов в графе
СообщениеДобавлено: 12 ноя 2013, 21:30 
Не в сети
Начинающий
Зарегистрирован:
12 ноя 2013, 21:05
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Доброго времени суток, уважаемые математики.
Прошу Вас дать мне совет в решении следующей проблемы:

Есть орграф с циклами. В нем заданы две произвольные вершины A и B.
Нужно найти количество всевозможных путей не содержащих циклов из вершины A в вершину B.
Как это сделать за полиномиальное время, т.е. не прибегая к полному перебору. Либо если это NP-полная задача - то почему.

У меня есть следующие идеи:
1) Подсчитать количество путей вообще - можно возведением матрицы смежности в степень.
2) Подсчитать количество циклов в графе - штука пока что для меня непонятная. По идее это как-то делается на основе фундаментальной системы циклов (типа суммы величин всевозможных сочетаний элементов из этой системы).

Но как тогда подсчитать количество путей с циклами в графе (причём считая, что цикл обходится лишь один раз, т.е. не учитывая пути с кратными
циклами)?

P.S. Возможно это дурацкий вопрос, который решили уже 100500 лет назад. Прошу не судить строго.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ 1 сообщение ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Определить количество путей

в форуме Дискретная математика, Теория множеств и Логика

lolliker228

3

139

13 дек 2020, 23:57

Посчитать максимальное количество рёбер в графе

в форуме Начала анализа и Другие разделы школьной математики

IG2

0

180

02 июл 2022, 20:14

Дерево - связный граф без циклов, а не что-то другое

в форуме Начала анализа и Другие разделы школьной математики

Fyodor272000

3

268

16 окт 2022, 16:24

Имеется ли алгоритм поиска всех элементарных циклов графа?

в форуме Информатика и Компьютерные науки

inek82

0

233

03 июл 2021, 21:53

Поиск путей

в форуме Аналитическая геометрия и Векторная алгебра

samorez

8

659

26 апр 2015, 17:33

Поиск путей

в форуме Дискретная математика, Теория множеств и Логика

Ivan Kalita

1

140

07 фев 2024, 00:43

Число путей в сети

в форуме Исследование операций и Задачи оптимизации

AGN

6

414

14 ноя 2018, 18:58

Число путей ладьи из угла в угол на шахматной доске

в форуме Дискретная математика, Теория множеств и Логика

K1b0rg

14

1480

29 апр 2018, 21:50

Поиск всех путей от одного узла графа к другому

в форуме Дискретная математика, Теория множеств и Логика

user723

3

302

02 авг 2017, 20:28

Поток на графе

в форуме Дискретная математика, Теория множеств и Логика

AlexMiel

0

216

16 окт 2017, 15:46


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 20


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved