Для решения задачи нам нужно воспользоваться свойствами графов и некоторыми теоремами из теории направленных графов.

Пусть у нас есть неориентированный граф ( G = (V, E) ), где ( V ) — это множество городов, а ( E ) — множество дорог. Мы знаем, что:

Граф связный, т.е. из любого города можно добраться до любого другого.Общее количество дорог (то есть количество рёбер в графе) чётно.

Мы хотим ориентировать рёбра графа таким образом, чтобы из каждого города выходило чётное число дорог. В терминах теории графов это означает, что степень выхода (out-degree) для каждой вершины (города) должна быть чётной.

Для решения этой задачи мы можем воспользоваться следующими шагами:

Чётные степени: В неориентированном графе прямое следствие из того, что сумма всех степеней вершин равна удвоенному количеству рёбер (т.е. ( \sum{v \in V} \deg(v) = 2|E| )). Поскольку ( |E| ) чётно, то ( \sum{v \in V} \deg(v) ) также четно.

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

Распределение рёбер: Со стороны ориентирования мы можем использовать алгоритм, который будет выбирать два конца рёбер и направлять рёбра от одного конца к другому, или наоборот, таким образом, чтобы поддерживать четность степеней. Есть возможность взять любое ребро и "перевернуть" его, направив в нужную сторону, что позволит контролировать количество ориентированных рёбер, чтобы соответствовать условиям.

На практике мы можем поступить следующим образом:

Начнём с произвольной вершины и будем поочерёдно проходить по всем рёбрам, точно определяя направление каждого ребра, чтобы соответствовать условиям четного числа исходящих рёбер.При необходимости, если находим, что степень исходящих рёбер становится нечётной, можем изменить направление одного выбранного ребра, пока не добьёмся желаемого результата.

Таким образом, мы завершаем процесс, когда все города (все вершины графа) имеют чётное количество исходящих рёбер.

В итоге, мы продемонстрировали, что возможно ввести одностороннее движение на всех дорогах так, чтобы из каждого города выходило чётное число дорог.