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