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