Олимпиадная задача по теории графов для 8-9 классов: дороги между городами
Задача
В королевстве восемь городов. Король хочет построить такую систему дорог, чтобы из каждого города можно было попасть в любой другой, минуя не более одного промежуточного города, и чтобы из каждого города выходило не более k дорог. При каких k это возможно?
Решение
Если k = 2, то из города А можно "за один ход" попасть не более чем в два города, а из них "следующим ходом" – не более чем в четыре. Итого, из А можно попасть не более чем в шесть городов, а нужно – в семь. Для k = 3 расположим города в вершинах правильного восьмиугольника, а дороги пустим по всем сторонам и большим диагоналям.
Ответ
При k > 2.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет