Деревья и остовные деревья
Ошибка.
Попробуйте повторить позже
В тайном обществе 
членов, и у каждого есть счет в банке (на счету целое число рублей, которое может быть отрицательным). Время
от времени один из членов общества переводит со своего счета на счет каждого из своих друзей, состоящих в обществе, по 
рублю.
Известно, что с помощью цепочки таких переводов они могут перераспределить имеющиеся на счетах средства произвольным образом.
Докажите, что в этом обществе ровно 
пар друзей.
Подсказка 1
Очевидно, задача на граф. Тогда пусть вершины — члены общества, рёбра — дружбы. Сделаем замечание, что граф связный, иначе противоречие с условием. То есть мы хотим доказать, что граф на 2020 вершинах связный и в нём 2019 рёбер. Что же это значит?
Подсказка 2
Хотим доказать, что граф — дерево. А какое основное свойство есть у графов-деревьев?
Подсказка 3
Точно! В них нет циклов, то есть мы хотим доказать, что в графе нет циклов. Доказывать прямо, что их нет сложно и непонятно, поэтому надо предположить противное...
Подсказка 4
Пусть есть цикл A₁ - A₂ - ... - Aₙ. Как бы нам применить условие? Хотим предъявить какой-то набор весов в вершинах (счета в банке) такой, что при наличии цикла его бы нельзя было получить из изначального. То есть хотим следить за каким-то процессом передачи. Но если будет слишком много различий с изначальным, то за ними будет слишком трудно уследить (граф может вести себя почти как угодно). Значит, хотим минимизировать различия. Итого, что мы хотим рассмотреть?
Подсказка 5
Минимально может быть 2 различия. Рассмотрим такой набор весов, что везде он остался прежним, а у A₁ уменьшился на 1 и у А₂ увеличился на 1. Для удобства, пусть А₁ = А, А₂ = B. По условию, существует такой алгоритм переводов, который переводит изначальную расстановку в эту. Подумаем, важен ли нам порядок переводов?
Подсказка 6
Разумеется, нет. Подумаем теперь вот о чём. Будет ли толк, если все сделают перевод ровно один раз?
Подсказка 7
Осознайте, что нет. Тогда если в нашем алгоритме в каждой вершине было сделано хотя бы по одному переводу, можно убрать из каждой вершины по переводу и ничего не изменится. Будем делать так, пока не найдутся вершины без переводов, назовём их нулевыми. Поизучаем эти нулевые вершины.
Подсказка 8
Осознайте, что A — ненулевая. Пусть C — произвольная нулевая вершина. Поисследуйте нулевые вершины и выведи их взаимосвязь с остальными вершинами.
Подсказка 9
Несложно заметить, что если вершина (не B) нулевая, то все её соседи тоже нулевые (докажите это). Какой вывод тогда можно сделать про вершину B?
Подсказка 10
Именно! B - тоже нулевая вершина. То есть все соседи B, кроме А — нулевые, при этом вес B увеличился на 1. Что это значит?
Подсказка 11
Поймите, что A — ненулевая. При этом B — нулевая и на ребре AB построен цикл. Не кажется ли вам это подозрительным?...
Подсказка 12
Выведите из этих фактов, что А — нулевая и красиво закончите решение. Успехов!
Рассмотрим граф, вершинами которого являются члены общества, а ребрами соединены пары друзей. Докажем, что этот граф является деревом. Ясно, что граф связен, иначе невозможно было бы перемещать средства между компонентами связности. Осталось доказать, что в графе нет циклов.
Предположим противное: пусть вершины 
образуют цикл. Для краткости введем обозначения 
и 
По
условию несколькими переводами можно переместить 1 рубль из 
в 
т. е. добиться того, что счет вершины 
уменьшится на 
вершины 
— увеличится на 
а счета остальных вершин не изменятся. Рассмотрим такой способ, в котором суммарное количество
переводов — наименьшее из возможных. Ясно, что порядок переводов не важен: результат определяется тем, сколько переводов сделано из
каждой вершины.
Заметим, что найдется хотя бы одна вершина, из которой переводов не делалось. Действительно, в противном случае можно
было бы уменьшить на 
количество переводов из каждой вершины, от чего результат, как легко видеть, не изменился
бы.
Назовем вершины, из которых не делалось переводов, нулевыми. Вершина 
не может быть нулевой, так как ее счет должен в итоге
уменьшиться, а уменьшение счета происходит только при переводах из этой вершины. Рассмотрим любую нулевую вершину 
Если она
отлична от 
то все ее соседи — тоже нулевые, иначе счет в этой вершине увеличился бы. Если эти соседи отличны от 
то, аналогично,
их соседи тоже нулевые, и так далее. Поскольку 
можно соединить путем с 
отсюда следует, что вершина 
тоже
нулевая.
В результате всех переводов счет в вершине 
должен увеличиться на 
и это увеличение уже достигается переводом из 
Значит,
все остальные соседи вершины 
должны быть нулевыми. В частности, вершина 
— нулевая. Поскольку 
отлична от 
все ее
соседи тоже нулевые, в том числе 
Применяя это рассуждение к вершинам цикла по очереди, в итоге получаем, что и вершина 
должна быть нулевой. Противоречие.
Полученное противоречие доказывает, что в графе нет циклов, следовательно, он является деревом. В любом дереве количество ребер на
меньше, чем количество вершин, следовательно, в нашем графе ровно 
ребер, что и требовалось.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
