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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Поиск всех путей от одного узла графа к другому
СообщениеДобавлено: 02 авг 2017, 20:28 
Не в сети
Начинающий
Зарегистрирован:
02 авг 2017, 19:44
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Имеется вот такой граф:
Изображение

Нужно удалить лишние ребра.
Лишние - те что идут от одного узла к другому напрямую (выделены красным цветом), в то время как есть более длинный путь (который надо оставить).
Это только пример для понимания, масштабы реального графа будут намного больше.

Проблема в том, что если граф большой, будет неэффективно искать каждый раз все возможные пути от каждого узла к каждому, делая проход по одному и тому же пути несколько раз.
Подскажите, как это сделать эффективнее?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск всех путей от одного узла графа к другому
СообщениеДобавлено: 02 авг 2017, 20:46 
Не в сети
Последняя инстанция
Зарегистрирован:
08 апр 2015, 12:21
Сообщений: 7567
Cпасибо сказано: 229
Спасибо получено:
2751 раз в 2539 сообщениях
Очков репутации: 473

Добавить очки репутацииУменьшить очки репутации
Вам надо избавиться от циклов (с помощью удаления соответствующих ребер) и привести исходный граф к связному графу-дереву. Есть два известных алгоритма построения таких остовных графов: Алгоритм Прима и алгоритм Краскала (последний считается более быстрый). Смотрите в Интернете - полно ссылок по соответствующему запросу в любом поисковике.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск всех путей от одного узла графа к другому
СообщениеДобавлено: 03 авг 2017, 02:32 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
Мне кажется, ТС нужно транзитивное сокращение исходного графа. Оно может содержать циклы (после забывания ориентации ребер), как показано в примере по ссылке. На самом деле, в транзитивном сокращении могут быть и ориентированные циклы (контуры): например, если исходный граф есть такой цикл. Альтернативно речь может идти о минимальном эквивалентном графе (minimum equivalent graph; см. соответствующую статью на английском). В отличие от транзитивного сокращения он по определению является подграфом исходного графа. Впрочем, эти два понятия совпадают для ориентированных ациклических графов (DAG). Алгоритмы по нахождению транзитивного сокращения и минимального эквивалентного графа см. по ссылкам в статье. В некоторых математических программах эти алгоритмы реализованы, например, в SageMath.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск всех путей от одного узла графа к другому
СообщениеДобавлено: 03 авг 2017, 02:37 
Не в сети
Мастер
Аватара пользователя
Зарегистрирован:
31 мар 2017, 00:16
Сообщений: 206
Cпасибо сказано: 11
Спасибо получено:
76 раз в 70 сообщениях
Очков репутации: 17

Добавить очки репутацииУменьшить очки репутации
Вопрос в том, что нужно - именно алгоритм для графа или просто почистить граф

Про алгоритмы отвечено выше.

А если нужно почистить граф для graphviz, то у graphviz в комплекте есть программка tred (transitive reduction) - она как раз убирает такие избыточные пути. Скармливаешь ей текст-описание графа, она возвращает обработанное описание, которое обычно направляют в другой файл. Ну или на ходу берут, через pipe.

При особом желании можно скачать исходники и посмотреть, как что. Или прицепить тот код к своему, как библиотеку.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Xmas "Спасибо" сказали:
3D Homer
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 4 ]

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

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

Ivan Kalita

1

140

07 фев 2024, 00:43

Поиск путей

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

samorez

8

659

26 апр 2015, 17:33

Матрицы. Переход от одного базиса к другому

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

Deores

0

199

22 дек 2019, 15:24

Как изменится матрица перехода от одного базиса к другому, е

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

smv64

1

409

03 мар 2021, 17:20

Поиск наименьшего доминирующего множества вершин графа

в форуме Mathematica

Seliy

0

215

05 июл 2022, 18:41

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

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

inek82

0

233

03 июл 2021, 21:53

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

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

AGN

6

414

14 ноя 2018, 18:58

Определить количество путей

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

lolliker228

3

139

13 дек 2020, 23:57

Как по другому пишится 1e-7 Н ?

в форуме Размышления по поводу и без

dryjban

1

242

16 мар 2017, 18:26

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

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

K1b0rg

14

1480

29 апр 2018, 21:50


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



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

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


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

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

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

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