Тема . Графы и турниры

Индукция в графах и теорема Турана

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела графы и турниры
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#106844

В королевстве Нечетномонголия n  городов и полностью отсутствуют дороги. Король решил соединить дорогами хотя бы какие-нибудь города, однако его ограничивает древнее предание, согласно которому юная дева, выехавшая из родного города и вернувшаяся в него, проехав по одному разу через нечётное число других городов, погубит монархию. Какое наибольшее количество дорог сможет провести король так, чтобы не дать шанса юной деве?

Показать ответ и решение

Введем граф, вершинами которого будут города, а ребрами — дороги.

Пример. Если n = 2k +1,  то k  треугольников с общей вершиной, если n =2k  , то k− 1  треугольников с общей вершиной и висячее ребро из той же вершины.

Оценка. Будем доказывать формулу, данную в ответе, индукцией по количеству вершин. База для n= 1  и n= 2  очевидна. Проведем переход от всех k <n  к n.  Рассмотрим в графе произвольный нечетный цикл. Если таких нет, то в графе вообще нет циклов, значит, и ребер в нем не больше n − 1,  что меньше нашего ответа. Никакие две вершины этого цикла не могут быть соединены с одной и той же вершиной из оставшихся, иначе образуется четный цикл. Стянем этот цикл в одну вершину V,  проведя все ребра, которые соединяли вершины цикла с остальными вершинами графа, из вершины V.  Если при такой операции появился четный цикл, то он проходит через новую вершину V.  Пусть в старом графе вершины цикла, смежные с V,  соединялись с вершинами A  и B  стянутого цикла. Тогда, пройдя между A  и B  по циклу путь четной длины, мы получим четный цикл, который был в исходном графе, чего не может быть. Итак, после операции стягивания граф все еще удовлетворяет условиям задачи, поэтому для него верно предположение индукции. Пусть в графе осталось k  вершин. Тогда в нем ребер не больше [3(k− 1)∕2]  по предположению индукции. Мы удалили n− k  вершин и n− k+ 1  ребер, так как вершины стянутого цикла не могли быть соединены друг с дружкой ребрами, отличными от ребер цикла, иначе образуется четный цикл. Поэтому в исходном графе на n  вершинах ребер не больше, чем [3(k− 1)∕2]+ n− k+1 ≤[3(n − 1)∕2],  так как n> k+ 2,  что и требовалось доказать.

Ответ:

 [3(n− 1)∕2]

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

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

Бесплатное онлайн-обучение

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

Налоговые вычеты

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

Специальное предложение
для учителей

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

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!