Top.Mail.Ru

Часто ищут

Разделы

Бесплатно

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

Паросочетания и лемма Холла

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

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

Задача 1#82773

Даны n  мальчиков и 2n − 1  конфета. Докажите, что можно дать каждому мальчику по конфете так, чтобы мальчику, которому не нравится его конфета, не нравились и конфеты остальных мальчиков.

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

Подсказка 1

Рассмотрим граф, в котором вершинами являются конфеты и мальчики, ребро проводится между конфетой и мальчиком, если конфета этому мальчику нравится. Конечно, если выполняется условие леммы Холлы, то легко указать паросочетание, покрывающее мальчиков. А что, если это условие неверно?

Подсказка 2

Посмотрим на максимальное множество мальчиков, для которого условие леммы Холла неверно. Для него можно указать соответствующее множество конфет, которое, конечно, строго меньше. Что можно сказать о графе, если из него удалить все указанные вершины и соответствующие ребра?

Подсказка 3

Конечно! Множество удаленных конфет по мощности не превосходило n - 1, так что сейчас осталось хотя бы n конфет. Можно ли тогда указать в этом графе паросочетание?

Подсказка 4

Можно! Ведь в этом графе, конечно, выполняется условие леммы Холла (а иначе было удалено не максимальное множество мальчиков, которое ему не удовлетворяет). Как тогда можно раздать конфеты?

Сообщить об ошибке
Подсказки
Доказательство
Сообщить об ошибке

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

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

Программа
лояльности вер. 2.0

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

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

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

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

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

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

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

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

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

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

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

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