Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 4 ] |
|
Автор | Сообщение | |
---|---|---|
user723 |
|
|
Нужно удалить лишние ребра. Лишние - те что идут от одного узла к другому напрямую (выделены красным цветом), в то время как есть более длинный путь (который надо оставить). Это только пример для понимания, масштабы реального графа будут намного больше. Проблема в том, что если граф большой, будет неэффективно искать каждый раз все возможные пути от каждого узла к каждому, делая проход по одному и тому же пути несколько раз. Подскажите, как это сделать эффективнее? |
||
Вернуться к началу | ||
michel |
|
|
Вам надо избавиться от циклов (с помощью удаления соответствующих ребер) и привести исходный граф к связному графу-дереву. Есть два известных алгоритма построения таких остовных графов: Алгоритм Прима и алгоритм Краскала (последний считается более быстрый). Смотрите в Интернете - полно ссылок по соответствующему запросу в любом поисковике.
|
||
Вернуться к началу | ||
3D Homer |
|
|
Мне кажется, ТС нужно транзитивное сокращение исходного графа. Оно может содержать циклы (после забывания ориентации ребер), как показано в примере по ссылке. На самом деле, в транзитивном сокращении могут быть и ориентированные циклы (контуры): например, если исходный граф есть такой цикл. Альтернативно речь может идти о минимальном эквивалентном графе (minimum equivalent graph; см. соответствующую статью на английском). В отличие от транзитивного сокращения он по определению является подграфом исходного графа. Впрочем, эти два понятия совпадают для ориентированных ациклических графов (DAG). Алгоритмы по нахождению транзитивного сокращения и минимального эквивалентного графа см. по ссылкам в статье. В некоторых математических программах эти алгоритмы реализованы, например, в SageMath.
|
||
Вернуться к началу | ||
Xmas |
|
|
Вопрос в том, что нужно - именно алгоритм для графа или просто почистить граф
Про алгоритмы отвечено выше. А если нужно почистить граф для graphviz, то у graphviz в комплекте есть программка tred (transitive reduction) - она как раз убирает такие избыточные пути. Скармливаешь ей текст-описание графа, она возвращает обработанное описание, которое обычно направляют в другой файл. Ну или на ходу берут, через pipe. При особом желании можно скачать исходники и посмотреть, как что. Или прицепить тот код к своему, как библиотеку. |
||
Вернуться к началу | ||
За это сообщение пользователю Xmas "Спасибо" сказали: 3D Homer |
||
[ Сообщений: 4 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Поиск путей | 1 |
140 |
07 фев 2024, 00:43 |
|
Поиск путей | 8 |
659 |
26 апр 2015, 17:33 |
|
Матрицы. Переход от одного базиса к другому
в форуме Линейная и Абстрактная алгебра |
0 |
199 |
22 дек 2019, 15:24 |
|
Как изменится матрица перехода от одного базиса к другому, е
в форуме Линейная и Абстрактная алгебра |
1 |
409 |
03 мар 2021, 17:20 |
|
Поиск наименьшего доминирующего множества вершин графа
в форуме Mathematica |
0 |
215 |
05 июл 2022, 18:41 |
|
Имеется ли алгоритм поиска всех элементарных циклов графа?
в форуме Информатика и Компьютерные науки |
0 |
233 |
03 июл 2021, 21:53 |
|
Число путей в сети | 6 |
414 |
14 ноя 2018, 18:58 |
|
Определить количество путей | 3 |
139 |
13 дек 2020, 23:57 |
|
Как по другому пишится 1e-7 Н ?
в форуме Размышления по поводу и без |
1 |
242 |
16 мар 2017, 18:26 |
|
Число путей ладьи из угла в угол на шахматной доске | 14 |
1480 |
29 апр 2018, 21:50 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 26 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |