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

@Nescafe32 · Регистрация: 07.05.2014

Студворк — интернет-сервис помощи студентам

Добрый день. Подскажите пожалуйста, в слабо связном ориентированом графе будет ли существовать путь Эйлера? На примере продемонстрируйте, если можно

@Dennis Ritchie · 04.01.2015, 08:58

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

@Nescafe32 · 06.01.2015, 00:13 **[ТС]**

Благодарю. Однако хочу узнать таки ответ на свой вопрос. Слабо связным будет орграф если будет связен неориентированный граф.. А по примеру слабо связного графа, найденного на просторах Интернета, было видно, что никакого путь Эйлера не существует, так как он закрывался еще на середине графа.. Нужен пример

@ltkj · 06.01.2015, 00:23

Сообщение от Nescafe32

Благодарю. Однако хочу узнать таки ответ на свой вопрос. Слабо связным будет орграф если будет связен неориентированный граф.. А по примеру слабо связного графа, найденного на просторах Интернета, было видно, что никакого путь Эйлера не существует, так как он закрывался еще на середине графа.. Нужен пример

Подойдёт любой граф, где у одной из вершин кол-во входящих и исходящих рёбер сильно отличается. Например, можно взять вершину, отправить в нее все ребра. Остальные как-то разрисовать, чтоб граф был слабо связан. Тогда как только мы пройдём по одному из ребёр в направлении взятой вершины, путь прекратится(ибо идти дальше некуда), и остальные ребра в эту вершину посещены не будут. Следовательно, пути и нет.
Точный ответ - путь не обязательно будет существовать.

@Nescafe32 · 06.01.2015, 00:40 **[ТС]**

Вот такой пример я видел. Однако в задании указано найти путь Эйлера именно для слабо связного графа. Значит из "необязательно" нужно взять именно когда будет. Однако я не могу представить этого, в голову приходит только граф с разницей входных и выходных вершин

@ltkj · 06.01.2015, 00:42

Сообщение от Nescafe32

Вот такой пример я видел. Однако в задании указано найти путь Эйлера именно для слабо связного графа. Значит из "необязательно" нужно взять именно когда будет. Однако я не могу представить этого, в голову приходит только граф с разницей входных и выходных вершин

Ну тогда 2 вершины, соединенные ребром возьмите. У вас же нет условия, что он не должен быть сильно связным?

@Nescafe32 · 06.01.2015, 00:50 **[ТС]**

Только что вычитал, почему-то кажется, что это мне поможет.
"Любой односторонне связный граф является также слабо связным"
Графы обьяснили плохо, в интернете информации куча и некие несостыковочки бывают. Если эта цитата верна - спасибо, тему можно будет даже закрыть

@ltkj · 06.01.2015, 01:37

А чем вам мой пример так не понравился? Тот факт, что граф слабо связен очевиден и баз этого. Уберите стрелочку от этого ребра, граф же будет связным!

@Qwertiy · 07.01.2015, 23:09

Эйлеров путь - это путь, проходящий через все рёбра. Он существует, если в графе не более двух вершин имеют нечётную степень. Для ориентированного графа, если все вершины (кроме не более чем двух) имеют одинаковые степени исхода и захода, а среди особых не более чем у одной степень исхода на 1 больше степени захода и не более чем у одной степень захода на 1 больше степени исходи, а других вершин с неравными степенями нет.

И слабосвязность вообще никак не влияет. В задании слабосвязный граф скорее всего даётся с целью использования соответствующего способа хранения графа.

@Nescafe32 · 28.01.2015, 19:10 **[ТС]**

Наконец то руки дошли сделать. Реализовал, но есть вопрос: граф еще должен быть взвешенным - как это использовать? При наличии пути Эйлера просто указать сколько весит данный путь? Или если есть степень исхода больше 1 - двигаться всегда по ребру с меньшей стоимостью?

@Qwertiy · 28.01.2015, 19:39

Сообщение от Nescafe32

граф еще должен быть взвешенным - как это использовать?

Никак.

Сообщение от Nescafe32

При наличии пути Эйлера просто указать сколько весит данный путь?

Сумму весов всех рёбер.

Сообщение от Nescafe32

Или если есть степень исхода больше 1 - двигаться всегда по ребру с меньшей стоимостью?

Бессмысленно.

@Nescafe32 · 28.01.2015, 20:02 **[ТС]**

Как все просто.. Спасибо еще раз

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод Сайт называется reddit: The Thinkpad X220 Tablet is the best budget school laptop period. Это. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@Nescafe32 5 / 5 / 2 Регистрация: 07.05.2014 Сообщений: 101

	Будет ли существовать путь Эйлера в слабо связном ориентированом графе? 03.01.2015, 15:45. Показов 1107. Ответов 11 Метки нет (Все метки) Добрый день. Подскажите пожалуйста, в слабо связном ориентированом графе будет ли существовать путь Эйлера? На примере продемонстрируйте, если можно 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	04.01.2015, 08:58
	Задача на ориентированный граф. Решение - путь (цикл) Эйлера. Транспорт на Новый год. Графы Не знаю, правда, насколько этот граф слабо связный. 1

@Nescafe32 5 / 5 / 2 Регистрация: 07.05.2014 Сообщений: 101
	06.01.2015, 00:13 [ТС]
	Благодарю. Однако хочу узнать таки ответ на свой вопрос. Слабо связным будет орграф если будет связен неориентированный граф.. А по примеру слабо связного графа, найденного на просторах Интернета, было видно, что никакого путь Эйлера не существует, так как он закрывался еще на середине графа.. Нужен пример 0

@Nescafe32 5 / 5 / 2 Регистрация: 07.05.2014 Сообщений: 101
	06.01.2015, 00:40 [ТС]
	Вот такой пример я видел. Однако в задании указано найти путь Эйлера именно для слабо связного графа. Значит из "необязательно" нужно взять именно когда будет. Однако я не могу представить этого, в голову приходит только граф с разницей входных и выходных вершин 0

@Nescafe32 5 / 5 / 2 Регистрация: 07.05.2014 Сообщений: 101
	06.01.2015, 00:50 [ТС]
	Только что вычитал, почему-то кажется, что это мне поможет. "Любой односторонне связный граф является также слабо связным" Графы обьяснили плохо, в интернете информации куча и некие несостыковочки бывают. Если эта цитата верна - спасибо, тему можно будет даже закрыть 0

@ltkj 122 / 24 / 6 Регистрация: 31.12.2014 Сообщений: 164
	06.01.2015, 01:37
	А чем вам мой пример так не понравился? Тот факт, что граф слабо связен очевиден и баз этого. Уберите стрелочку от этого ребра, граф же будет связным! 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	07.01.2015, 23:09
	Эйлеров путь - это путь, проходящий через все рёбра. Он существует, если в графе не более двух вершин имеют нечётную степень. Для ориентированного графа, если все вершины (кроме не более чем двух) имеют одинаковые степени исхода и захода, а среди особых не более чем у одной степень исхода на 1 больше степени захода и не более чем у одной степень захода на 1 больше степени исходи, а других вершин с неравными степенями нет. И слабосвязность вообще никак не влияет. В задании слабосвязный граф скорее всего даётся с целью использования соответствующего способа хранения графа. 1

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

@Nescafe32 5 / 5 / 2 Регистрация: 07.05.2014 Сообщений: 101
	28.01.2015, 20:02 [ТС]
	Как все просто.. Спасибо еще раз 0