Подвешивание, ранжирование, упорядочивание в графах

Построим граф, вершинами которого будут города, а рёбрами — дороги. Заметим, что по условию в графе нет циклов. То есть он состоит из нескольких деревьев.

Будем доказывать индукцией по , что в дереве на вершинах можно выбрать не меньше вершин так, чтобы каждая выбранная вершина была соединена не более чем с одной из остальных выбранных. База для действительно верна. Пусть утверждение верно для . Докажем для . Подвесим дерево за вершину и выберем самую низкую висячую вершину из всех. Рассмотрим её предка. Если он соединён с еще хотя бы одной висячей вершиной, то выкинем его и все висячие вершины, являющиеся его соседями. В оставшемся дереве по предположению индукции можно выбрать хотя бы вершин с сохранением условия. Теперь достаточно добавить к ним всех выкинутых соседей предка.

Если же у предка висячей вершины нет других висячих соседей, то можно считать, что у предков всех самых низких висячих вершин есть ровно один висячий сосед (сами эти вершины). Вернёмся к нашей висячей вершине. Если у её предка есть предок, то выкинем его и всё его поддерево. В оставшемся дереве снова выберем не менее вершин и добавим к ним все выкинутые вершины, кроме предка предка исходной висячей вершины.

Наконец, если предка предка не существует, то наше дерево состоит всего из 2 вершин, соединённых ребром, тогда можно взять его целиком.

Для решения задачи осталось лишь выбрать не менее вершин из каждого дерева, а затем, если вершин получилось больше чем нужно, выкинуть лишние.