Деревья и остовные деревья

Рассмотрим граф, вершинами которого являются члены общества, а ребрами соединены пары друзей. Докажем, что этот граф является деревом. Ясно, что граф связен, иначе невозможно было бы перемещать средства между компонентами связности. Осталось доказать, что в графе нет циклов.

Предположим противное: пусть вершины образуют цикл. Для краткости введем обозначения и По условию несколькими переводами можно переместить 1 рубль из в т. е. добиться того, что счет вершины уменьшится на вершины — увеличится на а счета остальных вершин не изменятся. Рассмотрим такой способ, в котором суммарное количество переводов — наименьшее из возможных. Ясно, что порядок переводов не важен: результат определяется тем, сколько переводов сделано из каждой вершины.

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

Назовем вершины, из которых не делалось переводов, нулевыми. Вершина не может быть нулевой, так как ее счет должен в итоге уменьшиться, а уменьшение счета происходит только при переводах из этой вершины. Рассмотрим любую нулевую вершину Если она отлична от то все ее соседи — тоже нулевые, иначе счет в этой вершине увеличился бы. Если эти соседи отличны от то, аналогично, их соседи тоже нулевые, и так далее. Поскольку можно соединить путем с отсюда следует, что вершина тоже нулевая.

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

Полученное противоречие доказывает, что в графе нет циклов, следовательно, он является деревом. В любом дереве количество ребер на меньше, чем количество вершин, следовательно, в нашем графе ровно ребер, что и требовалось.