ПитерГор 2019
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Пусть между городами 
и 
есть дороги 
и 
но нет дорог 
и 
Назовем пеpecтройкой замену пары дорог
и 
на пару дорог 
и 
Изначально в стране было несколько городов, некоторые пары городов были
соединены дорогами, причем из каждого города выходило по 
дорог. Министр нарисовал новую схему дорог, в которой из
каждого города по-прежнему выходит 
дорог. Известно, что как в старой, так и в новой схемах никакие два города
не соединены более, чем одной дорогой. Докажите, что новую схему можно получить из старой с помощью нескольких
перестроек.
Источники:
Подсказка 1
Есть несколько способов доказательства подобных утверждений. Первый способ: предъявить алгоритм перестроения любой схемы дорог в любую другую. Второй способ: предположить, что существует пара непереводимых друг в друга схем, и прийти к противоречию. Подумайте, какой способ предпочтительнее.
Подсказка 2
Как в теории можно реализовать первый способ? Искать несовпадающие элементы, как-то их исправлять. В этом случае возникает несколько проблем. Во-первых, как переводить один элемент в другой? Во-вторых, почему при исправлении одного несовпадения, мы не создадим новые, или если создадим, то почему в ходе такого процесса количество несовпадений уменьшается? Первую проблему можно решить перебором, но со второй это не сработает. Так задача тоже докручивается, но мы пойдём более простым путём и предположим противное!
Подсказка 3
Рассмотрим всевозможные графы из условия (со степенями вершин, равными 100), пусть они составляют множество M. Все эти графы построены на множестве V. Так как мы хотим следить за несовпадениями, то полезно будет следующие обозначения: F(G, G') — множество необщих рёбер у графов G и G' из множества M, f(G, G') = |F(G, G')| — их количество. Какие первые замечания можно сделать про функции F(G, G') и f(G, G'), учитывая, что в любом графе из M степень каждой вершины равна 100?
Подсказка 4
Во-первых, в F(G, G') одинаковое количество рёбер из G и G'. Во-вторых, чуть менее простой факт: f(G, G') — чётно (осознайте это). Вернёмся к нашему предположению. Пусть существует два непереводимых друг в друга графа A и B. Что нужно ещё сказать про эти графы, чтоб получить противоречие при перестроении?
Подсказка 5
Воспользоваться принципом крайнего! Пусть А и B — такая пары непереводимых, что f(A,B) — минимально. Хотим переводить один граф в другой, но пока что это отдельные графы и с ними не прям удобно работать. Что можно сделать?
Подсказка 5:
Рассмотрим граф H = (V, F(A,B)), рёбра из А в H — красные, из B — синие. Вспомним условие, мы можем менять пару "противоположных сторон квадратика" (набора из 4 вершин) на другую пару. Хотим, чтоб все синие рёбра наложились на красные. Какую самую естественную конструкцию в таком случае мы хотим найти в H?
Подсказка 6
Конечно, мы хотим найти цикл на 4-ёх различных вершинах с чередующимися рёбрами (или что-то очень похожее). Осознайте, что в Н красная степень и синяя степень равны для каждой вершины. Какой моментальный вывод из этого следует?
Подсказка 7
В Н точно есть цикл с чередованием. Рассмотрим такой цикл (понятно, что он чётной длины) Z = a₁a₂...a₂ₙ вновь с применением принципа крайнего, то есть Z минимальной длины. Самостоятельно докажите, что в нём всегда найдётся 4 подряд идущих различных вершины. Не забывайте про суть графа H и F(A, B).
Подсказка 8
Не умаляя общности, это a₁, a₂, a₃, a₄. Пусть рёбра a₁-a₂, a₃-a₄ — красные, a₂-a₃ — синие. Осталось перебрать несколько случаев, относительно ребра a₁-a₄.
Подсказка 9
Все случаи легко привести к противоречию, если вспомнить про то, что мы использовали принцип крайнего. У вас всё получится! Успехов!
Рассмотрим множество 
состоящее из всех возможных 
-регулярных(степени всех вершин в графе равны 100) графов на
данном множестве вершин 
(наши две схемы дорог — среди них). Докажем что любые два графа из 
можно перевести
друг друга серией перестроек. Для двух графов 
пусть 
- множество необщих рёбер этих графов, а
. Очевидно, что число 
всегда четно, и в множестве 
поровну рёбер из 
и
Предположим, что существуют пары непереводимых друг в друга перестройками графов в 
Рассмотрим такую прару графов 
с минимальным 
Граф 
имеет в каждой вершине поровну рёбер из 
и из 
. Следовательно, в 
существует
чередующийся цикл(в котором рёбра 
и 
чередуются). Рассмотрим цикл 
с минимальным числом
вершин(это не обязательно простой цикл, вершины в нем могут повторяться). Первая наша цель - найти на этом цикле четыре
последовательные различные вершины. В самом деле, пусть среди 
есть совпадающие. Очевидно, возможно
лишь совпадение 
. Так как рёбра цикла не повторяются, тогда 
и в качестве искомой четверки подойдет
Итак, не умаляя общности будем считать, что все вершины 
различны, причем 
и 
Рассмотрим три случая.
(а) 
Тогда проведем перестройку 
в графе 
(это возможно, так как 
) и получим граф
с 
По предположению, 
можно получить из 
перестройками, значит, можно получить и
(b) 
. Тогда 
— чередующийся цикл, меньший чем 
противоречие.
(c) 
Тогда проведем перестройку 
в графе 
(это возможно, так как 
и получим
граф 
с 
По предположению, 
можно получить из 
перестройками, значит, можно получить и
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
