|
|
 |
Условие
В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.
Решение 1
Разобьём все города на пары и соединим каждую пару своим маршрутом. Посчитаем для каждой дороги кратность: число маршрутов, в которые она вошла. Сумма кратностей для выходящих из города дорог нечётна: "свой" маршрут даёт вклад 1, а остальные – 0 или 2. Значит, из каждого города выходит нечётное число дорог нечётной кратности. Их и объявим главными.
Решение 2
Рассмотрим граф городов и дорог и докажем по индукции, что факт верен для любого связного графа с чётным числом вершин.
База. При n = 1 утверждение очевидно.
Шаг индукции. Пусть утверждение доказано для всех графов с меньших чем 2n (чётным) числом вершин. Возьмём связный граф на 2n вершинах и выделим в нём остовное дерево. В этом дереве возьмём любую висячую вершину А и рассмотрим вершину B, к которой она прикреплена. Если к вершине B прикреплено нечётное число висячих вершин, объявим главными все рёбра, ведущие из B в висячие вершины, удалим B и эти висячие вершины вместе со всеми выходящими из них рёбрами и применим предположение индукции к оставшемуся графу. В противном случае применим предположение индукции к графу, который получается удалением всех висячих вершин, прикреплённых к B, а потом дополнительно объявим главными все рёбра, ведущие из B в висячие вершины.
Замечания
1. См. также задачу М2232 из Задачника "Кванта" ("Квант", 2011, №4).
2. 5 баллов.
