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

В стране из 1000 городов некоторые города соединены дорогами, по которым можно двигаться в обе стороны. Известно, что в этой стране нет циклического маршрута. При каком наибольшем $k$ всегда можно выбрать $k$ городов так, чтобы каждый выбранный город был соединен не более чем с двумя из остальных выбранных?

Подсказка

Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если $k \geqslant 751$ , то в одном из пауков выбраны все 4 города, что противоречит условию.

Решение

Ответ. $k=750$ . Решение. Пример. Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если $k \geqslant 751$ , то в одном из пауков выбраны все 4 города, что противоречит условию.

Оценка. Рассмотрим граф: вершины — города, рёбра — дороги. Если граф не связный, будем проводить по ребру между компонентами связности, пока он не станет связным. Ясно, что такая процедура не увеличит искомое число $k$ и не добавит в граф циклы.

Итак, мы можем считать, что рассматриваемый граф — дерево. Индукцией по $n$ докажем, что в дереве на $n$ вершинах можно выбрать $k \geqslant 3 n / 4$ вершин так, чтобы выполнялось условие задачи. Такое множество вершин будем называть хорошим.

База: $n=1,2,3,4$ очевидна.
Переход: от всех меньших $n$ к $n$ . Подвесим дерево за вершину и рассмотрим вершину $v$ самого нижнего уровня. Если у ее предка $u$ не менее трёх потомков, то выкинем $u$ и всех ее потомков.

В оставшемся дереве выберем хорошее множество и добавим всех потомков $u$ . Полученное множество будет хорошим для исходного дерева, и в нём не менее $\frac{3}{4}(n-4)+3$ вершины.

Если у вершины $u$ ровно 2 потомка $v$ и $w$ , то рассмотрим её предка $t$ . Выкинем вершины $u, v, w$ и $t$ и, если понадобится, добавим рёбра для того, чтобы получилось дерево. В получившемся дереве выберем хорошее множество из не менее $\frac{3}{4}(n-4)$ вершин, после чего добавим к нему вершины $u, v$ и $w$ .

Итак, мы можем считать, что у любой вершины с нижнего уровня предок имеет степень ровно 2. Пусть $v$ — вершина нижнего уровня, $u$ — её предок, $w$ — предок $u$ . У всех потомков (не обязательно прямых) $w$ степень 1 или 2 . Если у $w$ всего $k \geqslant 3$ потомков (не обязательно прямых). Выкинем $w$ и всех её (не обязательно прямых) потомков. В оставшемся графе хорошее множество содержит не менее $3(n-k-1) / 4$ вершин. Добавим к ним всех $k$ потомков $w$ . Получим хорошее множество из не менее $3(n-k-1) / 4+k \geqslant 3 n / 4$ вершин в исходном дереве.

Наконец, если $k \leqslant 2$ , то единственные потомки $w$ — это $u$ и $v$ . Пусть $t$ — предок $w$ . Выкинем вершины $u, v, w$ и $t$ . В получившемся графе выберем хорошее множество из не менее $\frac{3}{4}(n-4)$ вершин, после чего добавим к нему вершины $u, v$ и $w$ .