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

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

Задача 1#73381

В государстве некоторые города соединены двусторонними беспересадочными авиалиниями. Из каждого города выходит не более 10  авиалиний. Всего в государстве более 190  авиалиний. Докажите, что найдутся 11  авиалиний, никакие две из которых не имеют общих концов.

Подсказки к задаче

Подсказка 1

Понятно, что хочется найти паросочетание из хотя бы 11 ребер (если переведем задачу на язык графов). В задаче есть условие на ребра, степени - поэтому попробуем решать от противного и выделим максимальное паросочетание - в нем не больше 10 ребер. Какие выводы можно сделать из этого? Что можно сказать о вершинах, которые не вошли в такое паросочетание?

Показать доказательство

Иными словами, нам дан граф, в котором степень каждой вершины не больше 10,  а всего рёбер хотя бы 191.  Нас просят найти паросочетание из хотя бы 11  рёбер. Предположим, что такого нет. Выделим максимальное паросочетание в графе, в нём не более 10  рёбер. Назовём вершины, вошедшие в паросочетание, хорошими, а остальные — плохими. Заметим, что плохие вершины не соединены между собой рёбрами, иначе мы сможем увеличить максимальное паросочетание. То есть рёбра могут быть либо между хорошими вершинами, либо между хорошей и плохой вершиной.

Степень каждой вершины не более 10,  а значит между хорошими вершинами проведено не более 20⋅10-
 2  =100  рёбер. То есть хотя бы 91  ребро проведено между хорошей и плохой вершинами.

Рассмотрим ребро AB  из паросочетания. Заметим, что если вершина A  соединена с некоторой плохой вершиной C,  а вершина B  — с другой плохой вершиной D,  то мы можем удалить из паросочетания ребро AB  и добавить рёбра AC  и BD,  тем самым оно увеличится, то есть такая ситуация невозможна. Значит, если вершина A  соединена с плохой вершиной C,  то возможны два случая. Либо вершина B  не соединена с плохими вершинами, тогда из A  в плохие вершины идёт не более 9  рёбер. Либо B  соединена с C  и не соединена с другими плохими вершинами. Следовательно, суммарно из A  и B  выходит не более 9  рёбер в плохие вершины. Тогда суммарно из хороших вершин выходит не более 90  рёбер в плохие (потому что в паросочетании не более 10  рёбер). Но ранее мы выяснили, что таких рёбер хотя бы 91,  противоречие.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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