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