Графы это хорошо и здорово. Графы много где используются и существует множество олимпиадных задач про них. Но в данном случае граф будет использоваться только, как пример и никакие его свойства нам не понадобятся.
Условие:
В стране 20 городов. Авиакомпания хочет организовать двусторонние рейсы между ними так, чтобы из любого города можно было добраться в любой другой не более чем за k пересадок. При этом количество авиалиний из любого города не должно превышать четырех. При каком наименьшем k это возможно?
Решение:
Заметим, что потребуется сделать не менее двух пересадок. Действительно, из произвольного города А без пересадок можно добраться не более чем в 4 города, а ровно с одной пересадкой — не более чем в 4*3 = 12 городов (так как один из рейсов ведет из каждого из этих городов в А). Итак, если использовать не более одной пересадки, то из любого города можно долететь не более чем в 16 других городов, а требуется — в 19. На рисунке показано, как можно организовать рейсы, чтобы было не более двух пересадок.
Картинка симметрична, поэтому достаточно показать, как можно добраться из первого города в любой другой. Из него без пересадок можно добраться до городов 2, 3, 4, 5. Затем с одной пересадкой — в города 6, 7, 8 (из 5), 9 (из 2), 13 (из 3) и 17 (из 4). И с двумя пересадками — в города 10, 11, 12 (из 9), в 14, 15, 16 (из 13), в 18, 19, 20 (из 17).
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!