Дано: связный неориентированный граф, степени всех вершин четны.
Найти: доказать, что на ребрах этого графа можно расставить стрелки так, чтобы выполнялись условия: а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой; б) для каждой вершины числа входящих и выходящих ребер равны.
Решение:
a) Поскольку степени всех вершин четны, то существует эйлеров цикл, проходящий по каждому ребру графа ровно один раз. Таким образом, можем пройти по всем ребрам графа, двигаясь только в одном направлении, и вернуться в начальную вершину.
b) Для каждой вершины степень входящих ребер равна степени исходящих ребер, так как граф неориентированный и все степени вершин четные, значит количество входящих и исходящих ребер равно.
Ответ:
На ребрах этого графа можно расставить стрелки так, чтобы выполнялись условия: а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой; б) для каждой вершины числа входящих и выходящих ребер равны.