@dalbio

Как найти рекурсивным способом эйлеров путь в графе, из какой вершины начинать?

Мне нужно найти эйлеров путь в ориентированном графе, в интернете я нашёл статью в статье сказано:
После ввода графа нужно запустить euler(0) или от любой другой вершины.
,но это не работает для ориентированного графа, тогда как мне быть?
Заранее спасибо за ответ.
  • Вопрос задан
  • 30 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Эйлеров цикл существует в графе, только если входная степень каждой вершины равна ее выходной степени.

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

Это элементарно доказать - путь в каждую вершину входит сколько-то раз и столько же раз выходит. Исключение - только начальная и конечная вершина, если они не совпадают.

Соответственно, вам надо подсчитать степени всех вершин, проверить что все хорошо (максимум одна с in==out+1 и одна с in==out-1) и запустить или от любой или от той, у которой исходящих ребер больше.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bnovo Санкт-Петербург
от 110 000 до 140 000 ₽
Spice IT Recruitment Москва
от 160 000 до 200 000 ₽
04 мар. 2021, в 13:23
800 руб./в час
04 мар. 2021, в 13:23
750000 руб./за проект
04 мар. 2021, в 13:11
250000 руб./за проект