Подвешивание, ранжирование, упорядочивание в графах

Перед нами схема авиалиний страны, в которой, чтобы добраться из города в город не хватит перелёта. Основная часть схемы состоит из повторяющихся блоков по города, см. города и

Для того, чтобы попасть из города в город нужно перелёта, затем из города в город по перелёта за каждые города, то есть перелётов, и ещё перелёта, чтобы добраться из города в город итого, минимум

С другой стороны, перелёта всегда достаточно, чтобы добраться от любого города до любого.

Чтобы доказать это, поместим какой-нибудь начальный город на уровень соединённые с ним (будем называть их соседними) города — на уровень их оставшихся соседей — на уровень и так далее. Каждый раз на уровень мы помещаем города, соседние с городами на уровне если им ранее не сопоставлен другой уровень. (Приведённый выше пример нарисован как раз по этому принципу).

Каждый город на уровне может быть соединён только с городами на уровнях и

Это значит, что на каждых трёх подряд идущих уровнях в сумме хотя бы города. Кроме того, на двух первых уровнях не менее городов, как и на двух последних.

Это означает, что у нас не может быть более

уровней, то есть максимально возможный номер уровня равен Но номер уровня — это и есть количество перелётов, необходимое, чтобы добраться в город на этом уровне из начального города. Поскольку в качестве начального города можно выбрать любой из городов, это значит, что от любого города до любого можно добраться не более, чем за перелёта.