ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 111833
Темы:    [ Связность и разложение на связные компоненты ]
[ Степень вершины ]
[ Перестройки ]
[ Принцип крайнего (прочее) ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

В стране есть N городов. Некоторые пары из них соединены беспосадочными двусторонними авиалиниями. Оказалось, что для любого k  (2 ≤ k ≤ N)  при любом выборе k городов количество авиалиний между этими городами не будет превосходить  2k – 2.  Докажите, что все авиалинии можно распределить между двумя авиакомпаниями так, что не будет замкнутого авиамаршрута, в котором все авиалинии принадлежат одной компании.


Решение

  Рассмотрим граф, вершины которого – это города, а рёбра – авиалинии. Обобщим задачу – разрешим графу иметь кратные рёбра. При этом для каждого набора из k вершин количество рёбер между ними не превосходит  2k – 2.  Требуется доказать, что можно покрасить рёбра графа в два цвета так, чтобы не было одноцветных циклов.
  Назовём непустое подмножество A вершин графа критическим, если количество рёбер графа между вершинами множества A – ровно  2|A| – 2.

  Лемма. Если A и B – критические подмножества, причём AB ≠ ∅,  то AB – тоже критическое.
  Доказательство. Пусть  C = ABD = AB  и  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)  в другой. Очевидно, одноцветных циклов не появится.

  Аналогично можем поступить, если c и d одновременно не принадлежат критическому множеству. Если же вершины b и c принадлежат критическому множеству A1, а вершины c и d – критическому множеству A2, то  A1A2  – тоже критическое (ибо  cA1A2).  Но тогда, добавив к этому множеству вершину a, мы добавим к его внутренним рёбрам три ребра; следовательно, полученное множество противоречит условию задачи.

Замечания

Заметим, что если между какими-то k вершинами число рёбер больше  2k – 2,  то требуемая покраска невозможна. Таким образом, верно и утверждение, обратное утверждению задачи.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2007
Этап
Вариант 5
Класс
Класс 11
задача
Номер 07.5.11.8

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .