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

Через где — произвольный город, обозначим число городов, соединённых беспосадочными авиалиниями с Будем рассматривать авиамаршрут, который проходит последовательно через города и все перелёты на котором централизующие. Ясно, что тогда

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

Допустим, что и Тогда то есть город соединён либо с либо с Но соединён с и а — с и

Наконец, предположим, что и Тогда соединён с соединён с и Получается, что город не соединён ни с ни с а тогда равенство невозможно. Итак, Приведём пример системы авиалиний, для которой все перелёты на маршруте, проходящем последовательно через города централизующие. Пусть города и () соединены, если выполнено хотя бы одно из следующих трёх условий: