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