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