|
|
 |
Условие
В стране N 1998 городов, и из каждого осуществляются беспосадочные перелеты в три других города (все авиарейсы двусторонние). Известно, что из каждого города, сделав несколько пересадок, можно долететь до любого другого. Министерство Безопасности хочет объявить закрытыми 200 городов, никакие два из которых не соединены авиалинией. Докажите, что это можно сделать так, чтобы можно было долететь из каждого незакрытого города в любой другой, не делая пересадок в закрытых городах.
Решение
Рассмотрим граф, вершинами которого являются города, рёбрами –
авиалинии. Получится связный граф, степени вершин которого равны 3.
Предположим, что в этом графе есть два пересекающихся (по вершине) цикла (см. рис.). Рассмотрим вершину O, в которой они разветвляются. Эта вершина, очевидно, имеет степень 3. Удалим её и три выходящих из неё ребра OA, OB, OC. При этом граф сохранит связность, так как существует путь, соединяющий вершины A, B и C.
Лемма. В связном графе с n вершинами и не менее чем 4n/3 рёбрами есть два пересекающихся цикла.
Доказательство. Предположим, что это не так. В силу связности графа, в нём можно выделить дерево с n вершинами. Будем возвращать в граф оставшиеся после выделения дерева ребра. Добавление каждого ребра увеличивает количество циклов по крайней мере на один. Однако, если какое-либо ребро добавит не менее двух циклов, они будут пересекающимися, что противоречит нашему предположению. С другой стороны, каждый цикл содержит не менее трёх вершин, и никакая вершина не входит в два цикла. Кроме того, дерево с n вершинами содержит ровно n – 1 ребро. Следовательно, рёбер не более, чем (n – 1) + n/3 < 4n/3. Противоречие.
Пусть N = 1998 – количество вершин в исходном графе, тогда исходное количество рёбер равно 3N/2. За каждую операцию выкидывания вершины количество вершин уменьшается на одну, а количество рёбер – на три. Предположим, что было сделано x операций. Тогда стало N – x вершин и 3N/2 – 3x рёбер. До тех пор, пока выполняется неравенство 3N/2 – 3x ≥ 4/3 (N – x) вершины удалять можно. Решив это неравенство, получаем x ≤ N/10, то есть можно удалить [1998/10] + 1 = 200 вершин, что и требовалось.
