Задание олимпиады: дорога на ремонте и связность городов
В стране из каждого города выходит 100 дорог и от каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт.
Докажите, что и теперь от каждого города можно добраться до любого другого.
Разобрать решение
Если закрыта дорога AB, то нам достаточно доказать, что и после этого можно добраться из A в B. Если это не так, то в компоненте связности, содержащей A, все вершины, кроме A, – чётные. Но наличие ровно одной нечётной вершины противоречит задаче 187972 б).
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.