Разделы 
Дополнительно
Задача по математике - 1898
2019-01-21 
В стране N 1998 городов и из каждого осуществляются беспосадочные перелеты в три других города (все авиарейсы двусторонние). Известно, что из любого города, сделав несколько пересадок, можно долететь до любого другого. Министерство Безопасности хочет объявить закрытыми 200 городов, никакие два из которых не соединены авиалинией. Докажите, что это можно сделать так, чтобы можно было долететь из любого незакрытого города в любой другой, не делая пересадок в закрытых разности?
Решение:
Рассмотрим граф, вершинами которого являются города, ребрами - авиалинии. По условию получится связный граф, степени вершин которого равны трем.
Предположим, что в графе, степени вершин которого не превосходят трех, есть два пересекающихся (по вершине) цикла (см. рис.). Тогда рассмотрим вершину $O$, в которой они «разветвляются». Эта вершина, очевидно, имеет степень три. Удалим эту вершину и три выходящих из нее ребра $OA, OB, OC$. Нетрудно заметить, что граф сохранил связность, так как существует путь, соединяющий вершины $A, B$ и $C$.
Рассмотрим полученный граф. Если в нем есть два пересекающихся цикла, то повторим операцию. И так далее. Очевидно, что никакие две удаленные вершины не соединены ребром в исходном графе, так как мы удаляли только вершины степени три, а после каждой операции степени вершин, соседних с удаленной, уменьшались, т. е. они не могут стать равными трем.
Предположим, что в связном графе $n$ вершин и не менее чем $\frac{4}{3} \cdot n$ ребер. Докажем, что в таком графе обязательно есть два пересекающихся цикла. Предположим, что это не так. В силу связности графа, в нем можно выделить дерево с $n$ вершинами. Будем «возвращать» в граф оставшиеся после выделения дерева ребра. Добавление каждого ребра увеличивает количество циклов по крайней мере на один. Однако, если какое-либо ребро добавит не менее двух циклов, они будут пересекающимися, что противоречит нашему предположению. С другой стороны, каждый цикл содержит не менее трех вершин, и никакая вершина не входит в два цикла. Кроме того, дерево с $n$ вершинами содержит ровно $n - 1$ ребро. Следовательно, ребер не более, чем $(n - 1) + \frac{n}{3} < \frac{4n}{3}$. Противоречие.
Пусть $N = 1998$ - количество вершин в исходном графе, тогда исходное количество ребер равно $\frac{3}{2}N$. За каждую операцию выкидывания вершины количество вершин уменьшается на одну, а количество ребер уменьшается на три. Предположим, что было сделано $x$ операций. Тогда стало $N - х$ вершин и $\frac{3}{2} N - Зx$ ребер. До тех пор, пока выполняется неравенство $\frac{3}{2} N - 3x \geq \frac{4}{3} (N - x)$, вершины удалять можно. Решив это неравенство, получаем $x \leq \frac{N}{10}$, т. е. можно удалить $\left [ \frac{1998}{10} \right ] + 1 = 200$ вершин.
Отсюда и следует утверждение задачи.
В стране N 1998 городов и из каждого осуществляются беспосадочные перелеты в три других города (все авиарейсы двусторонние). Известно, что из любого города, сделав несколько пересадок, можно долететь до любого другого. Министерство Безопасности хочет объявить закрытыми 200 городов, никакие два из которых не соединены авиалинией. Докажите, что это можно сделать так, чтобы можно было долететь из любого незакрытого города в любой другой, не делая пересадок в закрытых разности?
Решение:
Рассмотрим граф, вершинами которого являются города, ребрами - авиалинии. По условию получится связный граф, степени вершин которого равны трем.
Предположим, что в графе, степени вершин которого не превосходят трех, есть два пересекающихся (по вершине) цикла (см. рис.). Тогда рассмотрим вершину $O$, в которой они «разветвляются». Эта вершина, очевидно, имеет степень три. Удалим эту вершину и три выходящих из нее ребра $OA, OB, OC$. Нетрудно заметить, что граф сохранил связность, так как существует путь, соединяющий вершины $A, B$ и $C$.
Рассмотрим полученный граф. Если в нем есть два пересекающихся цикла, то повторим операцию. И так далее. Очевидно, что никакие две удаленные вершины не соединены ребром в исходном графе, так как мы удаляли только вершины степени три, а после каждой операции степени вершин, соседних с удаленной, уменьшались, т. е. они не могут стать равными трем.
Предположим, что в связном графе $n$ вершин и не менее чем $\frac{4}{3} \cdot n$ ребер. Докажем, что в таком графе обязательно есть два пересекающихся цикла. Предположим, что это не так. В силу связности графа, в нем можно выделить дерево с $n$ вершинами. Будем «возвращать» в граф оставшиеся после выделения дерева ребра. Добавление каждого ребра увеличивает количество циклов по крайней мере на один. Однако, если какое-либо ребро добавит не менее двух циклов, они будут пересекающимися, что противоречит нашему предположению. С другой стороны, каждый цикл содержит не менее трех вершин, и никакая вершина не входит в два цикла. Кроме того, дерево с $n$ вершинами содержит ровно $n - 1$ ребро. Следовательно, ребер не более, чем $(n - 1) + \frac{n}{3} < \frac{4n}{3}$. Противоречие.
Пусть $N = 1998$ - количество вершин в исходном графе, тогда исходное количество ребер равно $\frac{3}{2}N$. За каждую операцию выкидывания вершины количество вершин уменьшается на одну, а количество ребер уменьшается на три. Предположим, что было сделано $x$ операций. Тогда стало $N - х$ вершин и $\frac{3}{2} N - Зx$ ребер. До тех пор, пока выполняется неравенство $\frac{3}{2} N - 3x \geq \frac{4}{3} (N - x)$, вершины удалять можно. Решив это неравенство, получаем $x \leq \frac{N}{10}$, т. е. можно удалить $\left [ \frac{1998}{10} \right ] + 1 = 200$ вершин.
Отсюда и следует утверждение задачи.
