Паросочетания и лемма Холла
по каждой теме
каждый день
решения
«Школково» — ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Фокусник и его ассистент готовятся показать следующий фокус. У них есть колода из 2026 различных карт. Они сообщают зрителю
натуральное число Зритель выбирает
произвольных карт из колоды, убирает их в конверт и заклеивает его. Затем ассистент
выбирает
карт из оставшихся и передает их зрителю. Тот перетасовывает эти карты как хочет и отдает фокуснику. Задача фокусника —
отгадать карты, которые лежат в конверте. Для каких
фокусник и ассистент могут договориться действовать так, чтобы фокус
гарантированно удался?
Источники:
Подсказка 1
Ассистент видит k карт зрителя. Что он должен показать, чтобы фокусник восстановил набор?
Подсказка 2
Попробуйте представить процесс как соответствие между наборами. Как можно изобразить такое соответствие?
Подсказка 3
Используйте граф: вершины одной доли — наборы зрителя, другой — наборы ассистента. Когда между ними стоит проводить ребро?
Подсказка 4
Когда наборы не пересекаются. Сколько соседей будет у каждой вершины?
Подсказка 5
Степень равна Cₙⁿ⁻ᵏ. Что можно сказать про доли и сам граф?
Подсказка 6
Лемма Холла: паросочетание, покрывающее все вершины левой доли, существует, если для любого множества X наборов зрителя число соседей (наборов ассистента, не пересекающихся хотя бы с одним набором из X) не меньше |X|. В регулярном графе с равными долями это условие выполняется автоматически. Что из этого следует?
Подсказка 7
Следует, что есть совершенное паросочетание. Как фокусник и ассистент могут его использовать?
Подсказка 8
Если они заранее договорятся о конкретном паросочетании, то каждому набору зрителя будет соответствовать ровно один набор ассистента. Что тогда делает ассистент, увидев набор зрителя?
Подсказка 9
Он находит соответствующий набор в паросочетании и показывает его. Что делает фокусник? Для каких k это работает?
Обозначим Зафиксируем
и рассмотрим двудольный граф, вершинами одной доли которого являются всевозможные
комбинации из
зрительских карт, а второй долей являются всевозможные комбинации из
ассистентских карт (эти доли идентичны и
по существу являются всевозможными наборами из
различных карт колоды), а ребра проведены между вершинами разных долей, если
соответствующие наборы карт не пересекаются.
По вершине, соответствующей набору зрительских, ассистент должен выдать набор карт, соответствующих смежной вершине. Степени
всех вершин в этом графе равны так как каждой вершине одной доли сопоставляются всевозможные наборы из
карт из остатка
колоды размером
Это двудольный граф с равными по размерам долями, в котором степени всех вершин равны, поэтому согласно следствию из леммы
Холла в этом графе существует паросочетание, покрывающее все вершины обеих долей (совершенное паросочетание). Для каждого
фокусник и ассистент договариваются о выборе конкретного паросочетания, поэтому по картам ассистента всегда можно будет восстановить
карты зрителя.
Ошибка.
Попробуйте повторить позже
В графе вершин, все вершины имеют одинаковую степень. Докажите, что в этом графе есть паросочетание, содержащее не менее, чем
рёбер.
Подсказка 1:
Если требуемое в задаче верно, то наибольшее по числу рёбер паросочетание точно будет удовлетворять этому. Почему бы его не рассмотреть.
Подсказка 2:
Что делать дальше? Изучить ситуацию. Пусть в паросочетании менее n / 3 рёбер. Сколько тогда вершин вне паросочетания? Могут ли между ними быть рёбра, сколько рёбер от этих вершин проведено в вершины, вошедшие в паросочетание?
Подсказка 3:
Обозначим степень вершин через d. Вне паросочетания будет хотя бы [n / 3] + 1 вершина. Между ними рёбер нет. Из них выходит хотя бы d([n / 3] + 1) рёбер в вершины паросочетания. Не получится ли, например, для какого-то ребра AB в паросочетания найти две вершины X и Y вне паросочетания такие, что проведены рёбра AX и BY. Что можно сделать с такой конструкцией?
Пусть степень каждой вершины Рассмотрим наибольшее по числу рёбер паросочетание. Предположим, что в нём менее
рёбер. Тогда
вне паросочетания осталось хотя бы
вершин. Между этими вершинами нет рёбер, так что из них исходит хотя бы
рёбер в паросочетание. Тогда по принципу Дирихле найдётся пара
в которую пришло хотя бы
ребро. Поскольку степени
вершин
и
также равны
найдутся рёбра
и
где
и
— различные вершины, не лежащие в паросочетании. Тогда
можно увеличить исходное паросочетание, заменив
на
и
Противоречие. Значит, в наибольшем паросочетании хотя бы
вершин, что и требовалось доказать.
Ошибка.
Попробуйте повторить позже
Лемма Холла. Даны юношей и несколько девушек. Если для любого
…,
любые
юношей знакомы в совокупности
хотя бы с
девушками, то можно одновременно поженить каждого юношу на знакомой девушке (иными словами, существует
паросочетание, покрывающее всех мальчиков).
Рассмотрим граф знакомств. Обозначим доли юношей и девушек, как и
соответственно. Предположим, что максимальное
паросочетание имеет размер
— множество юношей покрытых данным паросочетанием,
— покрытые им
девушки,
— оставшиеся юноши и девушки, соответственно. Так как паросочетание максимальное, то нет ребер между
Будем рассматривать разделяющие множества и пути между это просто ребра. Паросочетание — множество
непересекающихся путей из
в
получается, между долями
максимум
не пересекающихся путей, тогда
по теореме Геринга, максимальное разделяющее множество содержит ровно
вершин. Так же оно содержит хотя бы
один из концов любого ребра из паросочетания, но причем только один (иначе их будет больше чем
). Пусть
—
разделяющее множество из
вершин,
— разделяющие юноши, аналогично
— разделяющие девушки.
Так как это множество разделяющее, значит, нет ребер между
Рассмотрим на множество
его
размер равен
а юноши из данного множества знакомы только с девушками из
чей размер равен
противоречие.
Ошибка.
Попробуйте повторить позже
Обобщенная лемма Холла. Даны натуральное число а также
юношей и несколько девушек. Если Для любого
любые
юношей знают не меньше, чем
девушек, то можно одновременно поженить хотя бы
юношей.
Добавим «общительных» девушек, каждая из которых связана со всеми
юношами.
Покажем, что в модифицированном графе выполняется условие Холла. Для любого подмножества юношей если
то
так как
содержит всех
«общительных» девушек. Если
то по условию исходной леммы
Добавленные
девушек дают
Таким образом, условие Холла выполнено. По стандартной лемме Холла существует паросочетание, покрывающее всех
юношей.
В полученном паросочетании удалим добавленных девушек. При этом: каждая добавленная девушка могла быть связана не более чем с
одним юношей, их удаление «развести» не более юношей. Следовательно, останется паросочетание, покрывающее не менее
юношей.
Ошибка.
Попробуйте повторить позже
Теорема Кёнига. Наибольшее количество рёбер в паросочетании в двудольном графе равно наименьшему количеству вершин в вершинном
покрытии графа (вершинное покрытие — это такое множество вершин, что каждое ребро содержит хотя бы одну из
них).
Размер максимального паросочетания равен количеству непересекающихся путей между долями графа (эти пути в точности его ребра).
Любое множество, разделяющее доли графа, обязано покрывать все ребра, то есть является вершинным покрытием. Тогда минимальное вершинное покрытие — минимальное разделяющее множество. По теореме Геринга его размер равен максимальному количеству непересекающихся путей между долями, а это и есть количество рёбер в наибольшем паросочетании.
Ошибка.
Попробуйте повторить позже
Из графа удалили
ребро. Докажите, что в нем все равно найдется совершенное паросочетание.
Пусть — множество удалённых рёбер. По условию
Для каждого удалённого ребра
обозначим через
событие,
заключающееся в том, что наше случайное паросочетание
содержит ребро
Оценим вероятность события Количество совершенных паросочетаний, содержащих конкретное фиксированное ребро, равное
количеству паросочетаний на оставшихся вершинах, то есть
Следовательно:
Рассмотрим событие: выбранное паросочетание содержит хотя бы одно удалённое ребро. Это событие есть объединение событий по
всем
Тогда имеем оценку:
Дробь строго меньше
Таким образом, вероятность выбрать паросочетание, содержащее удалённые рёбра, строго меньше единицы. Следовательно, существует хотя бы одно совершенное паросочетание, не содержащее удалённых рёбер.
Ошибка.
Попробуйте повторить позже
Оля и Максим оплатили путешествие по архипелагу из островов, где некоторые острова связаны двусторонними маршрутами катера.
Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по
очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл. Докажите, что
Оля может выиграть.
Подсказка 1
Попробуем разбить острова на пары связанных маршрутом катера и отдельные острова. Рассмотрим такое разбиение с максимальным числом пар. Какую стратегию может выбрать Оля?
Подсказка 2
Верно! Сначала она выбирает прилет на отдельный остров. Затем, если Максим выбирает остров из какой-то пары, то Оля отвечает островом из этой пары. А может ли Максим сходить на отдельный остров?
Подсказка 3
Рассмотрим путь от начального острова до этого отдельного острова. Из скольки островов он состоит?
Подсказка 4
Верно! Ровно из 2k островов: k-1 пара островов и 2 отдельных острова. А можно ли разбить этот путь так, чтобы увеличить наше разбиение?
Назовём спариванием разбиение архипелага на пары островов, соединённых катером, и отдельные острова. Рассмотрим максимальное
спаривание (с наибольшим числом пар). Прилетим на какой-нибудь отдельный остров (такой очевидно есть). Если Максим ходит на остров
из какой-то пары, Оля отвечает ходом на второй остров этой пары. Предположим, что Максиму удастся сделать ход на отдельный остров.
Путь с начала до этого острова состоит из чётного числа островов: из
пары и двух отдельных островов. Но этот путь можно было
разбить на
пар, что увеличило бы спаривание. Противоречие.
Значит, ход Максима на отдельный остров невозможен, и Оля выиграет.
Ошибка.
Попробуйте повторить позже
Набор ребер в графе называется покрытием, если каждая вершина графа принадлежит хотя бы одному ребру набора. Дан граф на
вершинах, среди которых нет изолированных. Докажите, что сумма размеров максимального паросочетания и минимального реберного
покрытия равна
Подсказка 1
Рассмотрим максимальное паросочетание, и пусть в нем ровно 2k вершин. По условию из каждой вершины выходит по ребру. А что можно сказать о ребрах, которые выходят из вершин, не вошедших в паросочетание?
Подсказка 2
Конечно! Любые две вершины не из паросочетания не соединены ребром (иначе паросочетание не максимальное). Кроме того, из двух различных вершин не из паросочетания ребра не могут вести в две различные вершины, связанные ребром, из паросочетания (иначе оно не максимальное). Попробуем выделить по ребру у каждой вершины не из паросочетания. Что можно сказать о минимальном покрытии этой конструкции?
Подсказка 3
Все верно! Оно содержит только ребра паросочетания и выделенные ребра, причем оно точно содержит все ребра паросочетания! Какова тогда сумма размеров максимального паросочетания и минимального покрытия?
Рассмотрим максимальное паросочетание, пусть в нём вершин. Любая из оставшихся вершин может быть соединена ребром лишь с
вершинами паросочетания, причём из различных оставшихся вершин не могут вести рёбра в различные вершины пары (иначе ребро в
паросочетании можно заменить на два). Так как в минимальном рёберном покрытии из каждой не входящей в паросочетание вершины
выходит хотя бы по ребру, выделим сперва ровно по одному такому, их получилось
рёбер. Теперь заметим, что для этого рёберного
покрытия существует также минимальное рёберное покрытие, которое помимо выделенных
рёбер содержит лишь рёбра
паросочетания.
Допустим, есть какое-то меньшее реберное покрытие. Назовём ребром если оно соединяет какие-то вершины из
паросочетания. Посмотрим, как покрыты вершины из паросочетания. Допустим, вершина
в паре с
Тогда пусть вершина
накрыта ребром, которое торчит наружу из паросочетания и никаким из торчащих внутрь(иначе внутренних ребёр покрытия хотя бы
столько же, сколько в паросочетании, победа). Посмотрим на вершину
Она покрыта не соответствующим ребром
паросочетания (из выбора
), при этом её ребро не торчит наружу. Допустим, она покрыта ребром в
Рассмотрим
Если из неё есть ребро наружу, то мы можем увеличить начальное паросочетание (взяв ребро в
с ребром
из неё). Получаем, что опять ребро идёт куда-то дальше. Когда-нибудь цикл замкнётся. Тогда мы накрыли
вершин
паросочетания
внутренними рёбрами (наружу ведь выйти нельзя!), что даёт нужную нам оценку на
внутренних рёбер в
покрытии.
Таким образом, существует минимальное рёберное покрытие из рёбер и ещё
рёбер паросочетания. Итого,
сумма числа рёбер в максимальном паросочетании
и числа рёбер в минимальном покрытии
действительно равна
Ошибка.
Попробуйте повторить позже
Имеются карточек с числами от
до
Двое показывают следующий фокус. Первый получает
карточек, выбранные
случайным образом. Одну из них он убирает, а
оставшихся выкладывает в ряд. Второй должен назвать спрятанную
карточку. Могут ли участники договориться так, чтобы по выложенным карточкам можно было определить спрятанную,
если
(b)
Подсказка 1
Фокусник должен по какому-то набору карт, понять какой-то другой набор карт. Как это можно сделать?
Подсказка 2 пункт а
Постройте биекцию между наборами четверок и упорядоченными тройками карт.
Подсказка 2 пункт б
Постройте биекцию между наборами из 13 и из 14 карт.
Рассмотрим двудольный граф, в одной доле которого — сочетания из по
в другой — размещения из
по
и ребро соединяет
размещение с сочетанием, если все элементы размещения входят в сочетание.
Подсчитаем степень произвольной вершины из первой доли. Здесь нужно ответить на вопрос: сколько вариантов действия у первого
участника фокуса? Он может убрать любую из четырёх карт, а три оставшиеся положить в ряд одним из способов. Значит, степень
вершины первой доли равна
Степень произвольной вершины второй доли равна количеству способов действия второго
участника фокуса. Поскольку он может назвать любое из
чисел, кроме тех трёх, которые он видит на карточках, и
здесь степень вершины равна
Тогда по лемме Холла существует паросочетание. Действительно, выберем из первой
доли
вершин, тогда их суммарная степень равна
Пусть они соединены с
вершинами из другой доли, тогда
Аналогично во втором пункте. Давайте сделаем биекцию между наборами из карт, которые видит первый, и наборами из
карт
который видит второй следующим образом. Рассмотрим двудольный граф, в одной доле которого — сочетания из
по
в другой —
сочетания из
по
и ребро соединяет сочетания, если набор
карт является подмножеством
Тогда степени всех вершин в
графе равны
а еще
тогда по лемме Холла существует паросочетание.
Ошибка.
Попробуйте повторить позже
В государстве некоторые города соединены двусторонними беспересадочными авиалиниями. Из каждого города выходит не более
авиалиний. Всего в государстве более
авиалиний. Докажите, что найдутся
авиалиний, никакие две из которых не имеют общих
концов.
Подсказка 1
Понятно, что хочется найти паросочетание из хотя бы 11 ребер (если переведем задачу на язык графов). В задаче есть условие на ребра, степени - поэтому попробуем решать от противного и выделим максимальное паросочетание - в нем не больше 10 ребер. Какие выводы можно сделать из этого? Что можно сказать о вершинах, которые не вошли в такое паросочетание?
Иными словами, нам дан граф, в котором степень каждой вершины не больше а всего рёбер хотя бы
Нас просят найти
паросочетание из хотя бы
рёбер. Предположим, что такого нет. Выделим максимальное паросочетание в графе, в нём не более
рёбер. Назовём вершины, вошедшие в паросочетание, хорошими, а остальные — плохими. Заметим, что плохие вершины не соединены между
собой рёбрами, иначе мы сможем увеличить максимальное паросочетание. То есть рёбра могут быть либо между хорошими вершинами, либо
между хорошей и плохой вершиной.
Степень каждой вершины не более а значит между хорошими вершинами проведено не более
рёбер. То есть хотя бы
ребро проведено между хорошей и плохой вершинами.
Рассмотрим ребро из паросочетания. Заметим, что если вершина
соединена с некоторой плохой вершиной
а
вершина
— с другой плохой вершиной
то мы можем удалить из паросочетания ребро
и добавить рёбра
и
тем самым оно увеличится, то есть такая ситуация невозможна. Значит, если вершина
соединена с плохой
вершиной
то возможны два случая. Либо вершина
не соединена с плохими вершинами, тогда из
в плохие вершины
идёт не более
рёбер. Либо
соединена с
и не соединена с другими плохими вершинами. Следовательно, суммарно
из
и
выходит не более
рёбер в плохие вершины. Тогда суммарно из хороших вершин выходит не более
рёбер в плохие (потому что в паросочетании не более
рёбер). Но ранее мы выяснили, что таких рёбер хотя бы
противоречие.
Ошибка.
Попробуйте повторить позже
В собрании клуба «Диоген» принимают участие несколько джентльменов, некоторые из которых дружат между собой (дружба взаимна). Назовём участника нелюдимым, если у него среди присутствующих на собрании ровно один друг. По правилам клуба единственный друг любого нелюдимого участника может покинуть собрание (джентльмены покидают собрание по одному). Цель собрания — добиться того, чтобы среди участников не осталось друзей. Докажите, что если цель вообще может быть достигнута, то количество оставшихся на собрании участников не зависит от того, кто и в каком порядке уходил.
Источники:
Подсказка 1
Джентльмены уходят по одному, пока не останется ни одной пары друзей. Что нужно исследовать в графе, построенном по условию, чтобы применять какие-то известные факты?
Подсказка 2
Очень похоже на условие задачи вершинного покрытия графа. Это такой набор вершин, для которого любое ребро имеет инцидентную (связанную с этим ребром) вершину в данном множестве. Какие существуют связанные понятия?
Подсказка 3
С вершинным покрытием связаны паросочетания — наборы ребер, не имеющих общих смежных с ними вершин. Попробуйте рассмотреть максимальное паросочетание, количество ребер в нем равно количеству вершин в минимальном вершинном покрытии.
Подсказка 4
Что можно сказать про количество ребер в максимальном паросочетании при уходе друга нелюдимого джентльмена?
Подсказка 5
Верно, количество ребер либо уменьшилось на 1, либо не изменилось. Если доказать, что оно обязано уменьшится на 1, то количество оставшихся джентльменов ровно на количество ребер в паросочетании меньше, чем в начале собрания.
Пусть в собрании участвовало джентльменов. Рассмотрим наибольшее возможное количество таких пар джентльменов, что
джентльмены в каждой паре знакомы и при этом джентльмен входит не более чем в одну пару. Назовём такой набор пар наибольшим
паросочетанием, пусть он состоит из
пар. Покажем, что если цель собрания была достигнута, то на нём осталось в точности
джентльменов, тогда количество оставшихся джентльменов действительно не зависит от последовательности действий
джентльменов.
Выберем наибольшее паросочетание Рассмотрим нелюдимого джентльмена
и его единственного знакомого
который
направляется к выходу. Поскольку джентльмен
мог входить только в одну пару наибольшего паросочетания, его уход уменьшит
количество пар не больше чем на
Покажем, что после ухода
размер наибольшего паросочетания уменьшится ровно на
Действительно, если это не так, то после ухода джентльмена
в паросочетании
осталось столько же пар, сколько и было ранее.
Поскольку у джентльмена
не осталось на собрании знакомых, он не может входить ни в какую пару из паросочетания
Но
тогда до ухода
паросочетание
можно было дополнить парой
что противоречит тому, что
— наибольшее
паросочетание.
Таким образом, каждый уходящий с собрания джентльмен уменьшает количество пар в наибольшем паросочетании ровно на
Поскольку при достижении цели собрания на нём не остаётся знакомых джентльменов, наибольшее паросочетание в этот момент не будет
содержать ни одной пары. Следовательно, к этому моменту ушло ровно
джентльменов и, значит, на собрании осталось
джентльменов.
Ошибка.
Попробуйте повторить позже
теннисистов сыграли
партий так, что каждый участвовал хотя бы в одной. Докажите, что найдутся
партий, в которых
участвовали
различных теннисистов.
Подсказка 1
Попробуем построить граф, в котором ребра — партии, а вершины — теннисисты. Пусть в его максимальном паросочетании x ребер. Тогда в нем 2x вершин. А можно ли оценить число ребер, которые выходят из оставшихся 200 - 2x вершин?
Подсказка 2
Ясно, что между этими теннисистами не может быть ребер, а иначе рассматриваемое паросочетание не является максимальным! При этом у каждой вершины есть по ребру, так что все они выходят в наше паросочетание. А сколько этих ребер?
Подсказка 3
Верно, 200 - 2x! А можем ли мы теперь снизу оценить число ребер и использовать число ребер из условия?
Построим граф, вершинами которого будут теннисисты, а ребрами — партии (кратные ребра разрешены). Рассмотрим максимальное
паросочетание. Пусть в нем ребер, то есть
теннисистов. Рассмотрим оставшихся
теннисистов. Между ними не может быть
ребер, иначе наше паросочетание было бы не максимальным. Но по условию из каждой вершины выходит хотя бы одно ребро. Тогда из этих
вершин выходит хотя бы
ребер в выбранное паросочетание. Тогда всего ребер не меньше, чем
откуда
что и требовалось доказать.
Ошибка.
Попробуйте повторить позже
Каждый из человек отправил кому-то другому из этих
человек письмо. Известно, что, если выбрать любых
человек, среди них найдутся отправитель и получатель одного и того же письма. При каком наименьшем
заведомо можно
выбрать
писем так, чтобы каждый из
человек оказался либо отправителем, либо получателем хотя бы одного из этих
писем?
Рассмотрим граф, вершинами которого являются люди, а рёбрами (не ориентированными) — письма. Степень каждой вершины в
нашем графе хотя бы и среди любых
вершин есть ребро. Наша задача равносильна тому поиску минимального
для которого можно выбрать
рёбер, покрывающих все вершины (чтобы каждая вершина была концом некоторого
ребра).
Докажем оценку. Выберем наибольшее паросочетание Тогда так как среди любых
вершин есть ребро, то в паросочетание не
вошло не более
вершин. А так как и в нашем графе, и в
чётное число вершин, то в
не вошло не более
вершин. Добавим к
по одному ребру из каждой вершины, не вошедшей в максимальное паросочетание. Пусть в
не вошло
вершин. Тогда
получившееся множество рёбер имеет не более
Приведём пример, где меньше рёбер взять не получится. Разобьем людей на
троек и группу из
человек. Пусть люди в
тройках обменяются письмами по циклу, а в группе из
человек (один из которых Дед Мороз) все послали письмо Деду Морозу, а Дед
Мороз любому из остальных девяти людей. Тогда в каждой тройке мы должны взять минимум два ребра, а в группе из
человек мы
должны взять хотя бы
рёбер. Итого
Осталось доказать, что пример подходит под условие. Это так, потому что среди
любых
человек найдется или
человека из какой-то тройки, или вся группа из
человек, внутри которой аж
рёбер.
Ошибка.
Попробуйте повторить позже
Из шахматной доски вырезали клеток. Докажите, что на оставшиеся клетки можно поставить
не бьющих друг друга
ладей.
Подсказка 1
Попробуем применить лемму Холла. Для этого нужно построить двудольный граф. Что можно считать вершинами, а что ребрами?
Подсказка 2
Верно! Пусть в одной доле будут вершины-строки, а в другой — вершины-столбцы, а ребра — невырезанные клетки, стоящие на пересечении соответствующих столбцов и строк. Попробуем теперь доказать условие леммы Холла для вершин-строчек.
Подсказка 3
Как и полагается в условии леммы, выберем любые k строчек. Нам нужны столбцы, которые с этими строчками соединяются. А можно ли оценить число столбцов, которые с нашими строчками не имеют общих ребер?
Подсказка 4
Конечно! Если столбец не имеет общих ребер с нашими строчками, то в нем вырезано хотя бы k клеток, а значит таких столбцов не более 7/k. Тогда столбцов, соединенных с нашими строчками хотя бы 8 - 7/k. Что остается проверить для леммы Холла?
Рассмотрим двудольный граф, вершинами левой доли — строчки, правой доли — столбцы, а рёбра — оставшиеся клетки. Докажем, что для
доли, соответствующей строчкам, выполняется условие леммы Холла, откуда и будет следовать решение задачи. Выберем любые
строчек. Если столбец не соединён ребром ни с одной из выбранных строчек, то в нём вырезали хотя бы
клеток. Тогда таких столбцов не
более
Следовательно, выбранные
строчек соединены с хотя бы
строчками. Но
для всех
Условие леммы
Холла доказано.
Ошибка.
Попробуйте повторить позже
В множестве
элементов. Докажите, что ко всем
-элементным подмножествам добавить по одному элементу так, чтобы все
получившиеся
-элементные подмножества были бы различны.
Рассмотрим двудольный граф, в котором вершины левой доли — -элементные множества, правой доли —
-элементные
множества, а рёбра проведены между всеми парами множеств, в которых одно содержит другое. Тогда степень каждой вершины левого
множества —
степени каждой вершины правого множества —
а вершин в правой доле больше, чем в левой.
Тогда воспользуемся таким следствием из леммы Холла. Если в двудольном графе в одной доле
вершин, а в другой не
меньше
причём степени вершин в каждой доле одинаковые между собой, то тогда можно выделить паросочетание в
доле с
вершинами. Значит, в данном графе есть паросочетание, покрывающее левую долю. откуда и следует решение
задачи.
Ошибка.
Попробуйте повторить позже
Из бумаги вырезан квадрат. Сверху на нем красным цветов нарисовано разбиение на равновеликих треугольников, а снизу зеленым
цветом нарисовано разбиение на
равновеликих треугольников. Докажите, что можно проткнуть квадрат
булавками так, чтобы
каждая булавка протыкала во внутренней точке один зеленый и один красный треугольник, и каждый треугольник был проткнут ровно
один раз.
Рассмотрим двудольный граф, в которой вершины левой доли — красные треугольники, правой доли — зелёные треугольники, а рёбра
проведены между зелёными и красными треугольниками, которые можно проткнуть одной булавкой. Заметим, что задача
равносильна поиску паросочетания в рассматриваемом графе, которое покрывает всю левую долю (а значит и правую). Для
доказательства существования такого паросочетания докажем условие леммы Холла. Рассмотрим любые красных треугольников.
Предположим, что из этих
треугольников ведут рёбра в
зелёных треугольников. Значит эти
зелёных треугольников
покрывают
красных треугольников, а так как треугольники равновеликие, то
Следовательно, условие леммы Холла
выполнено.
Ошибка.
Попробуйте повторить позже
Дана таблица Её первые
строчек заполнены натуральными числами от
до
так, что в каждой строке и в каждом
столбце все числа различны. Докажите, что можно расставить натуральные числа от
до
в оставшиеся клетки таблицы так, чтобы
по-прежнему выполнялось это условие.
Подсказка 1
Достаточно доказать, что можно заполнить еще одну строку. Попробуем рассмотреть для чисел от 1 до n столбцы, в которых их нет. Как удобно по-другому представить эту информацию?
Подсказка 2
Верно! Представим это в виде двудольного графа, в котором вершины одной доли — числа, а вершины другой доли — столбцы. Ребро проводится между числом и столбцом, в котором этого числа нет. Какие будут степени у вершин?
Подсказка 3
Точно! Степень каждой вершины равна n - k. Тогда в каждой доле степени вершин одинаковы. Можно ли выделить паросочетание, покрывающее долю столбцов?
Подсказка 4
Верно, по лемме Холла получается нужное паросочетание! Как теперь расставить числа, чтобы они соответствовали условию?
Достаточно показать, что мы можем заполнить ещё одну строчку с соблюдением условий. Рассмотрим двудольный граф, вершинами левой
доли будут числа от до
вершинами правой доли — столбцы, и проведём все рёбра от чисел к тем столбцам, в которых их нет.
Заметим, что степени всех вершин равны по
Воспользуемся таким следствием из леммы Холла. Если в двудольном графе в одной
доле
вершин, а в другой не меньше
причём степени вершин в каждой доле одинаковые между собой, то тогда можно выделить
паросочетание в доле с
вершинами. Следовательно, получаем, что в рассматриваемом графе есть паросочетание, покрывающее левую
долю (а значит и правую). Тогда следуя этому паросочетанию мы можем расставить числа в
строке, а значит, и во всей
таблице.
Ошибка.
Попробуйте повторить позже
Даны мальчиков и
конфета. Докажите, что можно дать каждому мальчику по конфете так, чтобы мальчику, которому не
нравится его конфета, не нравились и конфеты остальных мальчиков.
Подсказка 1
Рассмотрим граф, в котором вершинами являются конфеты и мальчики, ребро проводится между конфетой и мальчиком, если конфета этому мальчику нравится. Конечно, если выполняется условие леммы Холлы, то легко указать паросочетание, покрывающее мальчиков. А что, если это условие неверно?
Подсказка 2
Посмотрим на максимальное множество мальчиков, для которого условие леммы Холла неверно. Для него можно указать соответствующее множество конфет, которое, конечно, строго меньше. Что можно сказать о графе, если из него удалить все указанные вершины и соответствующие ребра?
Подсказка 3
Конечно! Множество удаленных конфет по мощности не превосходило n - 1, так что сейчас осталось хотя бы n конфет. Можно ли тогда указать в этом графе паросочетание?
Подсказка 4
Можно! Ведь в этом графе, конечно, выполняется условие леммы Холла (а иначе было удалено не максимальное множество мальчиков, которое ему не удовлетворяет). Как тогда можно раздать конфеты?
Рассмотрим двудольный граф, вершинами которого будут мальчики и конфеты, а рёбра будем проводить от мальчика к конфете, если та
ему нравится. Если для доли мальчиков выполняется условие леммы Холла, то найдём паросочетание, покрывающее мальчиков и раздадим
конфеты мальчикам, следуя ему. Предположим, что условие леммы Холла не выполняется. Пусть — это максимальное по включению
множество мальчиков, для которого не выполняется лемма Холла, а
— это множество конфет, которые нравятся мальчикам из
Понятно, что
Удалим из графа вершины из множеств
и
Так как
то осталось не менее
конфет. Для оставшегося графа для доли мальчиков выполнено условие леммы Холла, так как иначе множество
было не
максимальным по включению. Значит в оставшемся графе есть паросочетание, покрывающее мальчиком. Раздадим оставшимся
мальчикам конфеты, следуя этому паросочетанию, а мальчикам из
раздадим оставшиеся конфеты (их хватит, так
после удаления
осталось не менее
конфет). Нетрудно убедится, что при такой раздаче конфет все условия задачи
выполнены.
Ошибка.
Попробуйте повторить позже
На конференцию приехали математиков, каждый знает
языка из
разрешенных на конференции. Докажите, что их можно
разбить на три секции по
человек, говорящих на одном языке.
Подсказка 1
Попробуем реализовать следующую идею: возьмем три самых популярных языка (назовем их первым, вторым и третьим) и рассмотрим граф, в котором только эти три языка и все математики. Если найти в нем паросочетание, то распределить математиков на группы легко. А как доказать, что в этом графе есть паросочетание?
Подсказка 2
Рассмотрим любых k математиков. В случае k ≤ 100 условие леммы Холла очевидно. Попробуем разбить доказательство еще на два случая: 101 ≤ k ≤ 200 и 201 ≤ k ≤ 300. Предположим, что в первом из этих двух случаев условие леммы Холла не выполняется. Что тогда можно сказать о языковых знаниях математиков?
Подсказка 3
Действительно, условие леммы Холла не выполнится, только если все эти k математиков знают ровно 1 язык. Попробуем доказать, что это невозможно. Для этого пойдем от непопулярных языков: пусть пятый язык знают меньше всего людей. Если его знают более 100 человек, то четвертый язык - язык, который знают меньше всего людей после пятого, а в если не более 100 человек, то это язык, который знает меньше всего людей среди знающих пятый (в этот момент мы начинаем полагать, что 1, 2 и 3 языки являются просто всеми остальными). Теперь нам фактически нужно оценить число людей, знающих одновременно четвертый и пятый язык. Как это сделать?
Подсказка 4
Все верно! В первом случае это сразу ясно, а во втором это оценивается так: люди знают всего 900 языков (3 * 300 = 900), тогда пятый язык знают не более 900/5 < 200 человек, тогда эти люди знают менее 400 языков, помимо пятого, следовательно, сам четвертый язык знают менее 400/4 = 100 человек. Тогда невыполнение леммы Холла в случае 101 ≤ k <= 200 невозможно. А при каких условиях она может не выполняться для случая 201 ≤ k < 300?
Подсказка 5
Верно! Лемма Холла неверна, только если все эти k математиков не знают какой-то из языков: 1-ый, 2-ой или 3-ий. Однако меньше всего математиков знают пятый язык. Тогда в этом случае пятый язык знают менее ста человек. Как можно теперь доказать, что этот случай невозможен?
Подсказка 6
Пусть все эти k математиков не знают третий язык. Тогда его знает не более 300-k человек. Из наших k математиков не более 100 знают пятый язык, а можно ли тогда оценить число знающих четвертый язык и использовать условие его выбора для этой ситуации?
Пусть язык знают меньше всего людей. Тогда возможны два случая: (a)
язык знают менее
человек и (b)
язык знают более
человек. В первом случае определим
язык как язык, который знают меньше всего людей, не
считая
языка. Во втором случае определим
язык как язык, который знают меньше всего людей среди всех людей,
знающих
язык. Заметим, что всего люди знают
языков, а значит
язык знают не более
людей. Эти
люди помимо
языка знают ещё менее
языков, а значит в случая (b)
язык знают менее
людей.
Рассмотрим двудольный граф, вершинами левой доли будут математиков, вершинами правой доли будут
и
языки, причём у
каждого языка будет по
клонов. Также проведём рёбра от математиков ко всем языкам, которые они знают. Заметим, что
от каждого математика ведёт хотя бы
рёбер. Следовательно, от любых
математиков ведёт
или
рёбер. Докажем, что для полученного графа выполнено условие леммы Холла. Рассмотрим любых
математиков. Если
то условие леммы Холла выполнено. Если
то условие леммы Холла не выполнено только в случае,
когда эти
математиков знают один и тот же язык. Но в этом случае эти
математиков знают один и тот же набор
из трёх языков, два из которых это
и
языки. Следовательно, это случай (b). Но это невозможно, так как людей,
знающих одновременно
и
язык меньше
Если
то условие леммы Холла не выполнено только в
случае, когда эти
математиков не знают какой-то из
и
языков. Пусть все эти
математиков не знают третий
язык. Но
язык знают меньше всего людей, значит это случай (a). Но тогда
язык знает не более
людей, а
из
людей, не знающих третий язык не более
знают
язык. Значит
язык знает не менее
Осталось
заметить, что
что противоречит выборы
языка в случае (a). Мы доказали, что для рассматриваемого
графа есть паросочетание, покрывающее долю математиков, а это и есть разбиение их на группы по
человек с общим
языком.
Ошибка.
Попробуйте повторить позже
(a) Пусть — двудольный граф, в каждой доле по
вершин, и в нём больше чем
рёбер. Докажите, что в нём найдётся
паросочетание, в котором хотя бы
рёбер.
(b) Докажите, что из различного натурального числа, меньшего
можно выбрать
чисел, попарно отличающихся в обоих
разрядах (считаем, что у однозначных чисел в разряде десятков стоит
).
Подсказка 1, пункт (a)
Попробуем предположить противное. Какой вывод можно сделать по теореме Кенига?
Подсказка 2, пункт (a)
Верно! Найдется вершинное покрытие из k-1 вершины. Причем степени этих вершин мы можем оценить. Какое максимальное число ребер может содержать граф?
Подсказка 1, пункт (b)
Попробуем построить двудольный граф, который удовлетворял бы условию предыдущего пункта. Как это можно сделать?
Подсказка 2, пункт (b)
Верно! Вершины одной доли будут цифрами десятков, а вершины другой доли будут цифрами единиц. Что можно сказать о числе ребер в этом графе?
(a) Предположим, что в любом паросочетании не более ребра. По теореме Кёнига имеем, что в этом графе есть вершинное покрытие
состоящее из не более
вершины, причём степень каждой вершины в
не более
Следовательно, рёбер не более
что противоречит условию.
(b) Рассмотрим двудольный граф, вершины левой доли — цифры в десятках, правой — цифры в единицах. Рёбра — выбранные числа.
Далее применяем пункт




