|
|
 |
Условие
В стране есть N городов. Некоторые пары из них соединены беспосадочными двусторонними авиалиниями. Оказалось, что для любого k (2 ≤ k ≤ N) при любом выборе k городов количество авиалиний между этими городами не будет превосходить 2k – 2. Докажите, что все авиалинии можно распределить между двумя авиакомпаниями так, что не будет замкнутого авиамаршрута, в котором все авиалинии принадлежат одной компании.
Решение
Рассмотрим граф, вершины которого – это города, а рёбра – авиалинии. Обобщим задачу – разрешим графу иметь кратные рёбра. При этом для каждого набора из k вершин количество рёбер между ними не превосходит 2k – 2. Требуется доказать, что можно покрасить рёбра графа в два цвета так, чтобы не было одноцветных циклов.
Назовём непустое подмножество A вершин графа критическим,
если количество рёбер графа между вершинами множества A – ровно 2|A| – 2.
Лемма. Если A и B – критические подмножества, причём A ∩ B ≠ ∅, то A ∪ B – тоже критическое.
Доказательство. Пусть C = A ∩ B, D = A ∪ B и D – не критическое. Пусть |A| = a, |B| = b, |C| = c, |D| = d = a + b – c. Так как количество рёбер в A равно 2a – 2, а количество рёбер в D меньше чем 2d – 2, то число рёбер, соединяющих вершины из D, у которых не оба конца лежат в A, меньше
(2d – 2) – (2a – 2) = 2(d – a) = 2(b – c). В частности, в число этих рёбер входят все рёбра, соединяющие вершины B, не обе из которых лежат в C. Поэтому их число также меньше 2(b – c), а число остальных рёбер среди вершин B – больше (2b – 2) – 2(b – c) = 2c – 2. Но это в точности рёбра, соединяющие вершины множества C; значит, C не удовлетворяет условию задачи. Противоречие.
Заметим, что в условиях леммы множество C также будет критическим.
Перейдём к решению задачи. Предположим противное и рассмотрим граф с минимальным числом вершин n, для которого утверждение задачи не выполняется. Рассмотрим все его вершины. Число рёбер между ними не больше 2n – 2. Если степень каждой вершины не меньше 4, то общее количество рёбер не меньше 4n : 2 = 2n > 2n – 2, что невозможно. Значит, найдётся вершина a степени не больше 3. Если её степень меньше 3, то выкинем её; рёбра оставшегося графа можно покрасить требуемым образом, так как он, очевидно, удовлетворяет условию. Покрасив после этого ребра из вершины a в разные цвета, мы, очевидно, не образуем одноцветных циклов, и требуемая раскраска получена.
Итак, степень a равна 3, и она соединена с вершинами b, c, d. Все три вершины b, c, d не могут совпадать, так как иначе между двумя вершинами a и b было бы больше 2·2 – 2 рёбер, что невозможно. Тогда среди b, c и d есть вершина, отличная от обеих остальных – пусть это вершина c.
Выбросим из графа вершину a. Если в оставшемся графе пара вершин b и c не принадлежит одновременно никакому критическому подмножеству, то после добавления фиктивного ребра (b, c) мы получим граф, удовлетворяющий условию задачи, число вершин в котором меньше, чем в нашем (см. рис.). Покрасим его рёбра требуемым образом, потом удалим добавленное ребро, вернём вершину a и покрасим рёбра (a, b) и (a, c) в цвет фиктивного ребра, а ребро (a, d) в другой. Очевидно, одноцветных циклов не появится.
