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