Задача 065 — Задачи на Графы

Некоторые из 2017 городов страны соединены прямыми двусторонними авиарейсами так, что из каждого города можно добраться до любого другого. Правительство хочет объявить $k$ городов стратегически значимыми так, чтобы из любого города (включая стратегически значимые), совершив ровно один перелет, можно было попасть в стратегически значимый город. При каком наименьшем $k$ это наверняка можно будет сделать?

Подсказка

Очевидно, достаточно разобрать случай, когда граф — дерево (в произвольном связном графе можно выделить дерево, содержащее все его вершины; если $k$ стратегически значимых вершин будет достаточно для этого дерева, их будет достаточно и для исходного графа).

Докажем, что в графе с $n \geq 3$ вершинами можно указать несколько вершин и выделить из них несколько стратегически значимых так, что каждая выделенная вершина будет смежна с выделенной стратегически значимой, доля стратегически значимых среди выделенных будет не больше $2 / 3$ и после удаления выделенных вершин граф останется связным.

Рассмотрим две вершины $A$ и $B$ , путь между которыми содержит наибольшее количество рёбер.

Решение

Ответ. При $k=1344$ . Решение. Введём граф городов и авиарейсов. Для начала приведём пример графа, в котором меньше чем 1344 стратегически значимыми вершинами не обойтись. Пусть в графе имеются вершины $A$ , а также $B_{k}, C_{k}$ и $D_{k}, k=1,2, \ldots, 672$ ; для каждого $k$ проведём рёбра между вершиной $A$ и $B_{k}, B_{k}$ и $C_{k}$ , $C_{k}$ и $D_{k}$ . Легко видеть, что этот граф связен. Поскольку вершина $D_{1}$ связана только с вершиной $C_{1}$ , то вершина $C_{1}$ должна быть объявлена стратегически значимой. Кроме того, применяя условие задачи для вершины $C_{1}$ получаем, что либо вершина $B_{1}$ , либо вершина $D_{1}$ должна быть объявлена стратегически значимой. Итак, из вершин $B_{1}, C_{1}, D_{1}$ хотя бы две вершины должны быть стратегически значимыми. Рассуждая аналогично для каждой тройки $B_{k}, C_{k}, D_{k}$ , получаем требуемое.

Докажем теперь, что 1344 стратегически значимыми вершинами можно обойтись. Очевидно, достаточно разобрать случай, когда граф — дерево (в произвольном связном графе можно выделить дерево, содержащее все его вершины; если $k$ стратегически значимых вершин будет достаточно для этого дерева, их будет достаточно и для исходного графа).

Рассмотрим две вершины $A$ и $B$ , путь между которыми содержит наибольшее количество рёбер. Пусть $X$ — последняя перед $B$ вершина на пути из $A$ в $B$ . Очевидно, $B$ соединена только с $X$ . Если $X$ соединена с какимито висячими вершинами, кроме $B$ , выделим $X$ и все смежные с ней висячие вершины, а стратегически значимыми среди них объявим $X$ и $B$ . Очевидно, удаление этих вершин не нарушит связности графа, и стратегически значимые составляют среди них не более $2 / 3$ .

Пусть $B$ — единственная висячая вершина, соединённая с $X$ . Рассмотрим последнюю вершину $Y$ на пути из $A$ в $X$ . Если все отличные от $B$ вершины, путь из которых в $A$ проходит через $Y$ , смежны с $Y$ , можно выделить эти вершины, $Y, X$ и $B$ , а стратегическими среди них объявить $X$ и $Y$ .

Наконец, разберём случай, когда путь из $A$ в $Y$ можно продолжить несколькими путями $Y X_{i} B_{i}$ длины 2 (путями большей длины продолжить не удастся в силу максимальности выбранного выше пути из $A$ в $B$ ). Пусть таких путей $k$ . Тогда нужно выделить все вершины этих путей и все висячие вершины, смежные с $Y$ , а стратегически значимыми объявить $Y$ и все $X_{i}$ . При этом из графа будет удалено не менее $2 k+1$ вершин, из которых $k+1$ стратегически значимых, а $\frac{k+1}{2 k+1} \leq \frac{2}{3}$ .

Будем продолжать эту деятельность, пока от графа не останется огрызок, содержащий не более двух вершин. Если вершин не осталось вообще, то мы объявили стратегически значимыми не более $[2 \cdot 2017 / 3]=1344$ вершин, и процесс завершился. Если осталась одна вершина, то на предыдущем шаге нашего алгоритма она называлась $A$ и была соединена с вершиной $X$ или $Y$ , которую объявили стратегически значимой, значит, для нее условие выполнено, и стратегически значимыми было объявлено не более $[2 \cdot 2016 / 3]=1344$ вершин. Если же осталось две вершины, то, во-первых, они смежны, так как граф связности не теряет; во-вторых, одна из этих двух вершин была соединена с вершиной $X$ или $Y$ , объявленной стратегически значимой на предыдущем шаге. Поэтому достаточно объявить стратегически значимой лишь одну из этих двух вершин, чтобы условие выполнялось. Значит, и в этом случае стратегически значимыми будет объявлено не более $[2 \cdot 2015 / 3]+1=1344$ вершин.