Индукция в графах и теорема Турана
Ошибка.
Попробуйте повторить позже
В королевстве Нечетномонголия городов и полностью отсутствуют дороги. Король решил соединить дорогами хотя бы какие-нибудь
города, однако его ограничивает древнее предание, согласно которому юная дева, выехавшая из родного города и вернувшаяся в него,
проехав по одному разу через нечётное число других городов, погубит монархию. Какое наибольшее количество дорог сможет провести
король так, чтобы не дать шанса юной деве?
Введем граф, вершинами которого будут города, а ребрами — дороги.
Пример. Если то
треугольников с общей вершиной, если
, то
треугольников с общей вершиной и висячее
ребро из той же вершины.
Оценка. Будем доказывать формулу, данную в ответе, индукцией по количеству вершин. База для и
очевидна. Проведем
переход от всех
к
Рассмотрим в графе произвольный нечетный цикл. Если таких нет, то в графе вообще нет циклов, значит, и
ребер в нем не больше
что меньше нашего ответа. Никакие две вершины этого цикла не могут быть соединены с одной и той же
вершиной из оставшихся, иначе образуется четный цикл. Стянем этот цикл в одну вершину
проведя все ребра, которые соединяли
вершины цикла с остальными вершинами графа, из вершины
Если при такой операции появился четный цикл, то он проходит через
новую вершину
Пусть в старом графе вершины цикла, смежные с
соединялись с вершинами
и
стянутого
цикла. Тогда, пройдя между
и
по циклу путь четной длины, мы получим четный цикл, который был в исходном
графе, чего не может быть. Итак, после операции стягивания граф все еще удовлетворяет условиям задачи, поэтому для
него верно предположение индукции. Пусть в графе осталось
вершин. Тогда в нем ребер не больше
по
предположению индукции. Мы удалили
вершин и
ребер, так как вершины стянутого цикла не могли
быть соединены друг с дружкой ребрами, отличными от ребер цикла, иначе образуется четный цикл. Поэтому в исходном
графе на
вершинах ребер не больше, чем
так как
что и требовалось
доказать.
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!