@dalbio

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

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

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

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

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

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

Войти через центр авторизации
Похожие вопросы