Назад
Задача

В связном графе степени всех вершин чётны. Докажите, что на рёбрах этого графа можно расставить стрелки так, чтобы выполнялись следующие условия:

  а) двигаясь по стрелкам, можно добраться от каждой вершины до любой другой;

  б) для каждой вершины числа входящих и выходящих рёбер равны.

Решение

Рассмотрим эйлеров цикл, проходящий по всем рёбрам графа, (см. задачу 130806) и ориентируем все рёбра в соответствии с порядком прохождения цикла.

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет