Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/2: Рейтинг темы: голосов - 2, средняя оценка - 4.50
Nescafe32
5 / 5 / 2
Регистрация: 07.05.2014
Сообщений: 101
1

Будет ли существовать путь Эйлера в слабо связном ориентированом графе?

03.01.2015, 15:45. Просмотров 461. Ответов 11
Метки нет (Все метки)

Добрый день. Подскажите пожалуйста, в слабо связном ориентированом графе будет ли существовать путь Эйлера? На примере продемонстрируйте, если можно
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.01.2015, 15:45
Ответы с готовыми решениями:

Как найти степень вершины в ориентированом графе?
Как найти степень вершины в ориентированом графе?

Нахождение самого длинного пути в ориентированом графе
Всем доброго времени суток.Необходима помощь с алгоритмом поиска самого длинного из...

Найти такую вершину в графе, что любой путь из a в b будет проходить через неё
Есть задача, бьюсь над ней уже третий день. Мне дают неориентированный граф, не содержащий петель и...

Сколько роботов будет существовать через N дней?
Бригада из 3 роботов собирает за 1 день еще 1 нового робота.Время жизни нового робота-5 дней,после...

Сколько роботов будет существовать через N дней
Бригада из 3 роботов собирает за 1 день еще 1 нового робота.Время жизни нового робота-5 дней,после...

11
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
04.01.2015, 08:58 2
Задача на ориентированный граф. Решение - путь (цикл) Эйлера.
Транспорт на Новый год. Графы
Не знаю, правда, насколько этот граф слабо связный.
1
Nescafe32
5 / 5 / 2
Регистрация: 07.05.2014
Сообщений: 101
06.01.2015, 00:13  [ТС] 3
Благодарю. Однако хочу узнать таки ответ на свой вопрос. Слабо связным будет орграф если будет связен неориентированный граф.. А по примеру слабо связного графа, найденного на просторах Интернета, было видно, что никакого путь Эйлера не существует, так как он закрывался еще на середине графа.. Нужен пример
0
ltkj
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
06.01.2015, 00:23 4
Цитата Сообщение от Nescafe32 Посмотреть сообщение
Благодарю. Однако хочу узнать таки ответ на свой вопрос. Слабо связным будет орграф если будет связен неориентированный граф.. А по примеру слабо связного графа, найденного на просторах Интернета, было видно, что никакого путь Эйлера не существует, так как он закрывался еще на середине графа.. Нужен пример
Подойдёт любой граф, где у одной из вершин кол-во входящих и исходящих рёбер сильно отличается. Например, можно взять вершину, отправить в нее все ребра. Остальные как-то разрисовать, чтоб граф был слабо связан. Тогда как только мы пройдём по одному из ребёр в направлении взятой вершины, путь прекратится(ибо идти дальше некуда), и остальные ребра в эту вершину посещены не будут. Следовательно, пути и нет.
Точный ответ - путь не обязательно будет существовать.
0
06.01.2015, 00:23
Nescafe32
5 / 5 / 2
Регистрация: 07.05.2014
Сообщений: 101
06.01.2015, 00:40  [ТС] 5
Вот такой пример я видел. Однако в задании указано найти путь Эйлера именно для слабо связного графа. Значит из "необязательно" нужно взять именно когда будет. Однако я не могу представить этого, в голову приходит только граф с разницей входных и выходных вершин
0
ltkj
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
06.01.2015, 00:42 6
Цитата Сообщение от Nescafe32 Посмотреть сообщение
Вот такой пример я видел. Однако в задании указано найти путь Эйлера именно для слабо связного графа. Значит из "необязательно" нужно взять именно когда будет. Однако я не могу представить этого, в голову приходит только граф с разницей входных и выходных вершин
Ну тогда 2 вершины, соединенные ребром возьмите. У вас же нет условия, что он не должен быть сильно связным?
1
Nescafe32
5 / 5 / 2
Регистрация: 07.05.2014
Сообщений: 101
06.01.2015, 00:50  [ТС] 7
Только что вычитал, почему-то кажется, что это мне поможет.
"Любой односторонне связный граф является также слабо связным"
Графы обьяснили плохо, в интернете информации куча и некие несостыковочки бывают. Если эта цитата верна - спасибо, тему можно будет даже закрыть
0
ltkj
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
06.01.2015, 01:37 8
А чем вам мой пример так не понравился? Тот факт, что граф слабо связен очевиден и баз этого. Уберите стрелочку от этого ребра, граф же будет связным!
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
07.01.2015, 23:09 9
Эйлеров путь - это путь, проходящий через все рёбра. Он существует, если в графе не более двух вершин имеют нечётную степень. Для ориентированного графа, если все вершины (кроме не более чем двух) имеют одинаковые степени исхода и захода, а среди особых не более чем у одной степень исхода на 1 больше степени захода и не более чем у одной степень захода на 1 больше степени исходи, а других вершин с неравными степенями нет.

И слабосвязность вообще никак не влияет. В задании слабосвязный граф скорее всего даётся с целью использования соответствующего способа хранения графа.
1
Nescafe32
5 / 5 / 2
Регистрация: 07.05.2014
Сообщений: 101
28.01.2015, 19:10  [ТС] 10
Наконец то руки дошли сделать. Реализовал, но есть вопрос: граф еще должен быть взвешенным - как это использовать? При наличии пути Эйлера просто указать сколько весит данный путь? Или если есть степень исхода больше 1 - двигаться всегда по ребру с меньшей стоимостью?
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
28.01.2015, 19:39 11
Цитата Сообщение от Nescafe32 Посмотреть сообщение
граф еще должен быть взвешенным - как это использовать?
Никак.

Цитата Сообщение от Nescafe32 Посмотреть сообщение
При наличии пути Эйлера просто указать сколько весит данный путь?
Сумму весов всех рёбер.

Цитата Сообщение от Nescafe32 Посмотреть сообщение
Или если есть степень исхода больше 1 - двигаться всегда по ребру с меньшей стоимостью?
Бессмысленно.
1
Nescafe32
5 / 5 / 2
Регистрация: 07.05.2014
Сообщений: 101
28.01.2015, 20:02  [ТС] 12
Как все просто.. Спасибо еще раз
0
28.01.2015, 20:02
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.01.2015, 20:02

Технология .NET вытеснит обычное программирование под Windows или будет существовать параллельно?
SUBJ?

Алгоритм Флери для нахождения цикла Эйлера в графе
Может кто-нибудь делал такую работу, я просто не представляю как ее делать. Помогите пожалуйста.

К-ый путь в графе(ДП)
Здраствуйте! Прошу Вас помоч с задачной на ДП, думаю над ней достаточно долго, но ничего в голову...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.