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

В стране несколько городов, один из которых — Москва. Некоторые пары городов соединены двусторонними дорогами. Мэр хочет обгединить Москву ещё с п городами в большую Москву так, чтобы (1) между любыми двумя городами большой Москвы можно было проехать по дорогам, не попадая в города вне неё, и (2) было ровно $k$ городов вне большой Москвы, соединённых хотя бы одной дорогой с большой Москвой. Докажите, что есть не более $C_{n+k}^{k}$ способов совершить такое обгединение.

Подсказка

Пронумеруем вершины, кроме Москвы, произвольным образом.
Будем красить города из большой Москвы в красный цвет, а их соседей в зелёный цвет. То есть мэру нужно покрасить $n$ городов в красный, а $k$ других городов в зелёный.

Теперь построим соответствие способу покраски способ расставить в ряд $k$ зелёных и $n$ красных символов (способов сделать это $C_{n+k}^{k}$ ). Для удобства сначала будем писать не просто символы, а номера городов, после чего забудем сами номера, оставив только строчку цветных символов.

Решение

На первом этапе алгоритма выпишем в возрастающем порядке номера городов, соседних с Москвой (все они покрашены!). При этом мы покрасим красные в розовый, а зелёные так и оставим зелёными. На очередном шаге будем брать строчку, брать в ней самый левый розовый номер $x$ , и записывать в конец строки номера всех его ещё не выписанных соседей (все они покрашены!) в порядке возрастания номеров, причём номера красных городов запишем розовым, а зелёных — зелёным. После чего поменяем цвет номера $x$ на красный.

Так как на каждом шаге количество красных номеров увеличивалось на 1 , то процесс закончится.
Докажем, что полученное отображение инъективно. Предположим, есть две покраски городов, дающие одну и ту же последовательность. Тогда существует символ, который соответствует разным номерам в раскрасках; рассмотрим самый левый такой символ. Пусть до него последовательности имели вид $a_{1} a_{2} \ldots a_{t} x$ и $a_{1} a_{2} \ldots a_{t} y$ . В каждой из раскрасок номера $x$ и $y$ появились как соседи красных вершин с выписанными ранее номерами. Но поскольку предыдущие символы совпадали, то должен был совпасть и номер на месте $t+1$ .