Индукция в графах и теорема Турана
Ошибка.
Попробуйте повторить позже
В связном графе 
вершин. В каждой из них лежит некоторое количество монет, в сумме 
За один ход разрешается переложить
некоторое количество монет из одной вершины в соседнюю. Докажите, что из любого расположения монет можно разложить монеты
поровну во все вершины не более чем за 
ходов.
Подсказка 1
Для произвольного графа решить задачу сложно. Попробуйте решить еë для графа какой-то простой конструкции.
Подсказка 2
Решите задачу для дерева индукцией по количеству вершин. Подумайте, почему это равносильно решению для любого графа.
Подсказка 3
Давайте вспомним известный факт про связный граф: в нëм можно удалить некоторую вершину без потери связности. Как это поможет для доказательства перехода?
Будем считать, что в некоторых вершинах графа может быть целое отрицательное количество монет, но суммарное количество монет равно
Докажем задачу индукцией по 
База для 
очевидна, так как имеется всего одна вершина и в ней ровно 
монет. Пусть теперь в графе 
вершина. В любом
связном графе есть некоторая вершина 
при удалении которой граф не теряет связности. Если в ней ровно 
монет, удалим её и
воспользуемся предположением индукции. Если в ней больше 
монет, то переместим лишние в соседнюю вершину 
чтобы в 
осталось ровно 
монет. Далее удалим её. В оставшемся графе по предположению справимся за не более чем 
ход. Суммируя с одним
ходом из 
в 
получаем не более 
ходов. Если же в 
менее 
монет, докинем в неё из соседней вершины, чтобы стало
ровно 
и далее как в предыдущем случае. В соседней вершине количество монет может стать отрицательным, но это
учтено.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
