Паросочетания и лемма Холла
Ошибка.
Попробуйте повторить позже
В собрании клуба «Диоген» принимают участие несколько джентльменов, некоторые из которых дружат между собой (дружба взаимна). Назовём участника нелюдимым, если у него среди присутствующих на собрании ровно один друг. По правилам клуба единственный друг любого нелюдимого участника может покинуть собрание (джентльмены покидают собрание по одному). Цель собрания — добиться того, чтобы среди участников не осталось друзей. Докажите, что если цель вообще может быть достигнута, то количество оставшихся на собрании участников не зависит от того, кто и в каком порядке уходил.
Источники:
Подсказка 1
Джентльмены уходят по одному, пока не останется ни одной пары друзей. Что нужно исследовать в графе, построенном по условию, чтобы применять какие-то известные факты?
Подсказка 2
Очень похоже на условие задачи вершинного покрытия графа. Это такой набор вершин, для которого любое ребро имеет инцидентную (связанную с этим ребром) вершину в данном множестве. Какие существуют связанные понятия?
Подсказка 3
С вершинным покрытием связаны паросочетания — наборы ребер, не имеющих общих смежных с ними вершин. Попробуйте рассмотреть максимальное паросочетание, количество ребер в нем равно количеству вершин в минимальном вершинном покрытии.
Подсказка 4
Что можно сказать про количество ребер в максимальном паросочетании при уходе друга нелюдимого джентльмена?
Подсказка 5
Верно, количество ребер либо уменьшилось на 1, либо не изменилось. Если доказать, что оно обязано уменьшится на 1, то количество оставшихся джентльменов ровно на количество ребер в паросочетании меньше, чем в начале собрания.
Пусть в собрании участвовало джентльменов. Рассмотрим наибольшее возможное количество таких пар джентльменов, что
джентльмены в каждой паре знакомы и при этом джентльмен входит не более чем в одну пару. Назовём такой набор пар наибольшим
паросочетанием, пусть он состоит из
пар. Покажем, что если цель собрания была достигнута, то на нём осталось в точности
джентльменов, тогда количество оставшихся джентльменов действительно не зависит от последовательности действий
джентльменов.
Выберем наибольшее паросочетание Рассмотрим нелюдимого джентльмена
и его единственного знакомого
который
направляется к выходу. Поскольку джентльмен
мог входить только в одну пару наибольшего паросочетания, его уход уменьшит
количество пар не больше чем на
Покажем, что после ухода
размер наибольшего паросочетания уменьшится ровно на
Действительно, если это не так, то после ухода джентльмена
в паросочетании
осталось столько же пар, сколько и было ранее.
Поскольку у джентльмена
не осталось на собрании знакомых, он не может входить ни в какую пару из паросочетания
Но
тогда до ухода
паросочетание
можно было дополнить парой
что противоречит тому, что
— наибольшее
паросочетание.
Таким образом, каждый уходящий с собрания джентльмен уменьшает количество пар в наибольшем паросочетании ровно на
Поскольку при достижении цели собрания на нём не остаётся знакомых джентльменов, наибольшее паросочетание в этот момент не будет
содержать ни одной пары. Следовательно, к этому моменту ушло ровно
джентльменов и, значит, на собрании осталось
джентльменов.
Специальные программы

Программа
лояльности вер. 2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

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

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

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

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

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

