Паросочетания и лемма Холла

Назовём спариванием разбиение архипелага на пары островов, соединённых катером, и отдельные острова. Рассмотрим максимальное спаривание (с наибольшим числом пар). Прилетим на какой-нибудь отдельный остров (такой очевидно есть). Если Максим ходит на остров из какой-то пары, Оля отвечает ходом на второй остров этой пары. Предположим, что Максиму удастся сделать ход на отдельный остров. Путь с начала до этого острова состоит из чётного числа островов: из пары и двух отдельных островов. Но этот путь можно было разбить на пар, что увеличило бы спаривание. Противоречие.

Значит, ход Максима на отдельный остров невозможен, и Оля выиграет.

Рассмотрим максимальное паросочетание, пусть в нём вершин. Любая из оставшихся вершин может быть соединена ребром лишь с вершинами паросочетания, причём из различных оставшихся вершин не могут вести рёбра в различные вершины пары (иначе ребро в паросочетании можно заменить на два). Так как в минимальном рёберном покрытии из каждой не входящей в паросочетание вершины выходит хотя бы по ребру, выделим сперва ровно по одному такому, их получилось рёбер. Теперь заметим, что для этого рёберного покрытия существует также минимальное рёберное покрытие, которое помимо выделенных рёбер содержит лишь рёбра паросочетания.

Допустим, есть какое-то меньшее реберное покрытие. Назовём ребром если оно соединяет какие-то вершины из паросочетания. Посмотрим, как покрыты вершины из паросочетания. Допустим, вершина в паре с Тогда пусть вершина накрыта ребром, которое торчит наружу из паросочетания и никаким из торчащих внутрь(иначе внутренних ребёр покрытия хотя бы столько же, сколько в паросочетании, победа). Посмотрим на вершину Она покрыта не соответствующим ребром паросочетания (из выбора ), при этом её ребро не торчит наружу. Допустим, она покрыта ребром в Рассмотрим Если из неё есть ребро наружу, то мы можем увеличить начальное паросочетание (взяв ребро в с ребром из неё). Получаем, что опять ребро идёт куда-то дальше. Когда-нибудь цикл замкнётся. Тогда мы накрыли вершин паросочетания внутренними рёбрами (наружу ведь выйти нельзя!), что даёт нужную нам оценку на внутренних рёбер в покрытии.

Таким образом, существует минимальное рёберное покрытие из рёбер и ещё рёбер паросочетания. Итого, сумма числа рёбер в максимальном паросочетании и числа рёбер в минимальном покрытии действительно равна

Рассмотрим двудольный граф, в одной доле которого — сочетания из по в другой — размещения из по и ребро соединяет размещение с сочетанием, если все элементы размещения входят в сочетание.

Подсчитаем степень произвольной вершины из первой доли. Здесь нужно ответить на вопрос: сколько вариантов действия у первого участника фокуса? Он может убрать любую из четырёх карт, а три оставшиеся положить в ряд одним из способов. Значит, степень вершины первой доли равна Степень произвольной вершины второй доли равна количеству способов действия второго участника фокуса. Поскольку он может назвать любое из чисел, кроме тех трёх, которые он видит на карточках, и здесь степень вершины равна Тогда по лемме Холла существует паросочетание. Действительно, выберем из первой доли вершин, тогда их суммарная степень равна Пусть они соединены с вершинами из другой доли, тогда

Аналогично во втором пункте. Давайте сделаем биекцию между наборами из карт, которые видит первый, и наборами из карт который видит второй следующим образом. Рассмотрим двудольный граф, в одной доле которого — сочетания из по в другой — сочетания из по и ребро соединяет сочетания, если набор карт является подмножеством Тогда степени всех вершин в графе равны а еще тогда по лемме Холла существует паросочетание.

Иными словами, нам дан граф, в котором степень каждой вершины не больше а всего рёбер хотя бы Нас просят найти паросочетание из хотя бы рёбер. Предположим, что такого нет. Выделим максимальное паросочетание в графе, в нём не более рёбер. Назовём вершины, вошедшие в паросочетание, хорошими, а остальные — плохими. Заметим, что плохие вершины не соединены между собой рёбрами, иначе мы сможем увеличить максимальное паросочетание. То есть рёбра могут быть либо между хорошими вершинами, либо между хорошей и плохой вершиной.

Степень каждой вершины не более а значит между хорошими вершинами проведено не более рёбер. То есть хотя бы ребро проведено между хорошей и плохой вершинами.

Рассмотрим ребро из паросочетания. Заметим, что если вершина соединена с некоторой плохой вершиной а вершина — с другой плохой вершиной то мы можем удалить из паросочетания ребро и добавить рёбра и тем самым оно увеличится, то есть такая ситуация невозможна. Значит, если вершина соединена с плохой вершиной то возможны два случая. Либо вершина не соединена с плохими вершинами, тогда из в плохие вершины идёт не более рёбер. Либо соединена с и не соединена с другими плохими вершинами. Следовательно, суммарно из и выходит не более рёбер в плохие вершины. Тогда суммарно из хороших вершин выходит не более рёбер в плохие (потому что в паросочетании не более рёбер). Но ранее мы выяснили, что таких рёбер хотя бы противоречие.

Построим граф, вершинами которого будут теннисисты, а ребрами — партии (кратные ребра разрешены). Рассмотрим максимальное паросочетание. Пусть в нем ребер, то есть теннисистов. Рассмотрим оставшихся теннисистов. Между ними не может быть ребер, иначе наше паросочетание было бы не максимальным. Но по условию из каждой вершины выходит хотя бы одно ребро. Тогда из этих вершин выходит хотя бы ребер в выбранное паросочетание. Тогда всего ребер не меньше, чем откуда что и требовалось доказать.

Рассмотрим граф, вершинами которого являются люди, а рёбрами (не ориентированными) — письма. Степень каждой вершины в нашем графе хотя бы и среди любых вершин есть ребро. Наша задача равносильна тому поиску минимального для которого можно выбрать рёбер, покрывающих все вершины (чтобы каждая вершина была концом некоторого ребра).

Докажем оценку. Выберем наибольшее паросочетание Тогда так как среди любых вершин есть ребро, то в паросочетание не вошло не более вершин. А так как и в нашем графе, и в чётное число вершин, то в не вошло не более вершин. Добавим к по одному ребру из каждой вершины, не вошедшей в максимальное паросочетание. Пусть в не вошло вершин. Тогда получившееся множество рёбер имеет не более

Приведём пример, где меньше рёбер взять не получится. Разобьем людей на троек и группу из человек. Пусть люди в тройках обменяются письмами по циклу, а в группе из человек (один из которых Дед Мороз) все послали письмо Деду Морозу, а Дед Мороз любому из остальных девяти людей. Тогда в каждой тройке мы должны взять минимум два ребра, а в группе из человек мы должны взять хотя бы рёбер. Итого Осталось доказать, что пример подходит под условие. Это так, потому что среди любых человек найдется или человека из какой-то тройки, или вся группа из человек, внутри которой аж рёбер.

Рассмотрим двудольный граф, вершинами левой доли — строчки, правой доли — столбцы, а рёбра — оставшиеся клетки. Докажем, что для доли, соответствующей строчкам, выполняется условие леммы Холла, откуда и будет следовать решение задачи. Выберем любые строчек. Если столбец не соединён ребром ни с одной из выбранных строчек, то в нём вырезали хотя бы клеток. Тогда таких столбцов не более Следовательно, выбранные строчек соединены с хотя бы строчками. Но для всех Условие леммы Холла доказано.

Рассмотрим двудольный граф, в котором вершины левой доли — -элементные множества, правой доли — -элементные множества, а рёбра проведены между всеми парами множеств, в которых одно содержит другое. Тогда степень каждой вершины левого множества — степени каждой вершины правого множества — а вершин в правой доле больше, чем в левой. Тогда воспользуемся таким следствием из леммы Холла. Если в двудольном графе в одной доле вершин, а в другой не меньше причём степени вершин в каждой доле одинаковые между собой, то тогда можно выделить паросочетание в доле с вершинами. Значит, в данном графе есть паросочетание, покрывающее левую долю. откуда и следует решение задачи.

Рассмотрим двудольный граф, в которой вершины левой доли — красные треугольники, правой доли — зелёные треугольники, а рёбра проведены между зелёными и красными треугольниками, которые можно проткнуть одной булавкой. Заметим, что задача равносильна поиску паросочетания в рассматриваемом графе, которое покрывает всю левую долю (а значит и правую). Для доказательства существования такого паросочетания докажем условие леммы Холла. Рассмотрим любые красных треугольников. Предположим, что из этих треугольников ведут рёбра в зелёных треугольников. Значит эти зелёных треугольников покрывают красных треугольников, а так как треугольники равновеликие, то Следовательно, условие леммы Холла выполнено.

Достаточно показать, что мы можем заполнить ещё одну строчку с соблюдением условий. Рассмотрим двудольный граф, вершинами левой доли будут числа от до вершинами правой доли — столбцы, и проведём все рёбра от чисел к тем столбцам, в которых их нет. Заметим, что степени всех вершин равны по Воспользуемся таким следствием из леммы Холла. Если в двудольном графе в одной доле вершин, а в другой не меньше причём степени вершин в каждой доле одинаковые между собой, то тогда можно выделить паросочетание в доле с вершинами. Следовательно, получаем, что в рассматриваемом графе есть паросочетание, покрывающее левую долю (а значит и правую). Тогда следуя этому паросочетанию мы можем расставить числа в строке, а значит, и во всей таблице.

Рассмотрим двудольный граф, вершинами которого будут мальчики и конфеты, а рёбра будем проводить от мальчика к конфете, если та ему нравится. Если для доли мальчиков выполняется условие леммы Холла, то найдём паросочетание, покрывающее мальчиков и раздадим конфеты мальчикам, следуя ему. Предположим, что условие леммы Холла не выполняется. Пусть — это максимальное по включению множество мальчиков, для которого не выполняется лемма Холла, а — это множество конфет, которые нравятся мальчикам из Понятно, что Удалим из графа вершины из множеств и Так как то осталось не менее конфет. Для оставшегося графа для доли мальчиков выполнено условие леммы Холла, так как иначе множество было не максимальным по включению. Значит в оставшемся графе есть паросочетание, покрывающее мальчиком. Раздадим оставшимся мальчикам конфеты, следуя этому паросочетанию, а мальчикам из раздадим оставшиеся конфеты (их хватит, так после удаления осталось не менее конфет). Нетрудно убедится, что при такой раздаче конфет все условия задачи выполнены.

Пусть язык знают меньше всего людей. Тогда возможны два случая: (a) язык знают менее человек и (b) язык знают более человек. В первом случае определим язык как язык, который знают меньше всего людей, не считая языка. Во втором случае определим язык как язык, который знают меньше всего людей среди всех людей, знающих язык. Заметим, что всего люди знают языков, а значит язык знают не более людей. Эти люди помимо языка знают ещё менее языков, а значит в случая (b) язык знают менее людей.

Рассмотрим двудольный граф, вершинами левой доли будут математиков, вершинами правой доли будут и языки, причём у каждого языка будет по клонов. Также проведём рёбра от математиков ко всем языкам, которые они знают. Заметим, что от каждого математика ведёт хотя бы рёбер. Следовательно, от любых математиков ведёт или рёбер. Докажем, что для полученного графа выполнено условие леммы Холла. Рассмотрим любых математиков. Если то условие леммы Холла выполнено. Если то условие леммы Холла не выполнено только в случае, когда эти математиков знают один и тот же язык. Но в этом случае эти математиков знают один и тот же набор из трёх языков, два из которых это и языки. Следовательно, это случай (b). Но это невозможно, так как людей, знающих одновременно и язык меньше Если то условие леммы Холла не выполнено только в случае, когда эти математиков не знают какой-то из и языков. Пусть все эти математиков не знают третий язык. Но язык знают меньше всего людей, значит это случай (a). Но тогда язык знает не более людей, а из людей, не знающих третий язык не более знают язык. Значит язык знает не менее Осталось заметить, что что противоречит выборы языка в случае (a). Мы доказали, что для рассматриваемого графа есть паросочетание, покрывающее долю математиков, а это и есть разбиение их на группы по человек с общим языком.

(a) Предположим, что в любом паросочетании не более ребра. По теореме Кёнига имеем, что в этом графе есть вершинное покрытие состоящее из не более вершины, причём степень каждой вершины в не более Следовательно, рёбер не более что противоречит условию.

(b) Рассмотрим двудольный граф, вершины левой доли — цифры в десятках, правой — цифры в единицах. Рёбра — выбранные числа. Далее применяем пункт

Предположим, что такого паросочетания нет. Тогда по теореме Кёнига есть вершинное покрытие, содержащее не более вершин. Следовательно, это вершинное покрытие содержит не более вершин в одной из долей. Но тогда это не вершинное покрытие, так как степень каждой вершины из другой доли больше Получили противоречие, значит есть паросочетание, содержащее все вершины.

Лемма. В графе степени всех вершин лежат в промежутке Тогда можно стереть несколько ребер так, что все степени будут лежать в промежутке

Доказательство. Достаточно доказать лемму для Давайте рассмотрим множество вершин такое, что в нём каждая вершина имеет степень Будем убирать ребра, которые внутри Вершины, у которых степень становится меньше убираем из множества Теперь рассмотрим все оставшиеся вершины и заметим, что выполняется условие теоремы Холла для множества и множества оставшихся вершин. А значит, есть какое-то паросочетание из в множество оставшихся вершин, которое покроет все вершины из Осталось удалить все эти ребра и понять, что максимальная степень стала а минимальная уменьшилась не более чем на один в последнем удалении.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к задаче. Давайте все степени загоним в промежуток Теперь у каждой вершины отметим соседей. Хотим, чтоб они были разных цветов. Каждая вершина отмечена не более раз, то есть есть не более вершин, про которые мы хотим, чтобы у нее цвет отличался от Значит, можно покрасить в цвет.

Доказательство 1.

Назовем множество из парней критическим, если они знакомы ровно с девушками в совокупности. Рассмотрим минимальное критическое множество и попробуем кого-нибудь поженить.

Доказательство 2.

Рассмотрим максимальное паросочетание. Назовем неудачниками тех юношей, которых мы не смогли поженить. По условию, они знакомы хотя бы с девушками. Но всех тех девушек мы обязаны были женить, добавим их мужей к тем неудачникам, и так далее.

Замечание. Сформулированная задача известна как Лемма Холла.

В одну сторону лемма очевидна. Докажем, что если для любого набора из юношей количество знакомых им в совокупности девушек не меньше то каждого из них можно поженить на знакомых девушках. Создадим для каждого юноши его клон, не считая его самого. Нетрудно убедиться, что для полученного графа выполняется условие леммы Холла. Следовательно, в полученном графе есть паросочетание, покрывающее юношей. Тогда можно каждого юношу поженить на жёнах его клонов и получить требуемое.