Паросочетания и лемма Холла
Ошибка.
Попробуйте повторить позже
Лемма Холла. Даны юношей и несколько девушек. Если для любого
…,
любые
юношей знакомы в совокупности
хотя бы с
девушками, то можно одновременно поженить каждого юношу на знакомой девушке (иными словами, существует
паросочетание, покрывающее всех мальчиков).
Рассмотрим граф знакомств. Обозначим доли юношей и девушек, как и
соответственно. Предположим, что максимальное
паросочетание имеет размер
— множество юношей покрытых данным паросочетанием,
— покрытые им
девушки,
— оставшиеся юноши и девушки, соответственно. Так как паросочетание максимальное, то нет ребер между
Будем рассматривать разделяющие множества и пути между это просто ребра. Паросочетание — множество
непересекающихся путей из
в
получается, между долями
максимум
не пересекающихся путей, тогда
по теореме Геринга, максимальное разделяющее множество содержит ровно
вершин. Так же оно содержит хотя бы
один из концов любого ребра из паросочетания, но причем только один (иначе их будет больше чем
). Пусть
—
разделяющее множество из
вершин,
— разделяющие юноши, аналогично
— разделяющие девушки.
Так как это множество разделяющее, значит, нет ребер между
Рассмотрим на множество
его
размер равен
а юноши из данного множества знакомы только с девушками из
чей размер равен
противоречие.
Специальные программы

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

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

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

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

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

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

