#8 Паросочетания и введение в теорему Холла

Любые два ребра звезды имеют общий центр, поэтому в паросочетание нельзя взять два ребра. Одно ребро взять можно. Ответ: \(1\).

Рёбра паросочетания не имеют общих концов. Поэтому \(a\) покрытых левых вершин соединены с \(a\) различными вершинами правой доли. Значит, справа есть хотя бы \(a\) вершин.

Каждая вершина из \(S\) покрыта своим ребром паросочетания. Эти рёбра ведут в разные вершины правой доли, и все эти вершины лежат в \(N(S)\). Поэтому в \(N(S)\) есть как минимум \(|S|\) вершин.

Например, можно выбрать \(1\in A_1\), \(2\in A_2\), \(3\in A_3\). Все представители различны, значит, это система различных представителей.

Если две непокрытые вершины соединены ребром, это ребро не имеет общих концов с выбранными рёбрами. Его можно добавить к паросочетанию, противоречие.

Для одного кружка вариантов \(2\). Для любых двух кружков объединение списков содержит все три имени или хотя бы два имени. Для трёх кружков объединение равно \(\{a,b,c\}\), имеет размер \(3\). Условие Холла выполнено, значит, существует система различных представителей. Например, \(A_1\to a\), \(A_2\to b\), \(A_3\to c\).

Возьмём любое \(S\) в левой доле. Из \(S\) выходит не меньше \(3|S|\) рёбер. Все они входят в \(N(S)\), а каждая вершина из \(N(S)\) принимает не больше \(3\) таких рёбер. Значит, \(3|S|\le3|N(S)|\), откуда \(|N(S)|\ge |S|\).

Условие Холла выполнено, следовательно, есть паросочетание, покрывающее левую долю.

Для любого \(S\) слева из него выходит ровно \(d|S|\) рёбер. Все они входят в \(N(S)\), и каждая вершина из \(N(S)\) имеет степень \(d\), значит, принимает не больше \(d\) этих рёбер. Поэтому \(d|S|\le d|N(S)|\), откуда \(|N(S)|\ge |S|\). По теореме Холла нужное паросочетание существует.

Удалим произвольный элемент \(x\). Возьмём любые \(k\) множеств. До удаления их объединение имело размер не меньше \(k+1\). После удаления \(x\) размер объединения уменьшится не более чем на \(1\), значит, останется не меньше \(k\) элементов.

Условие Холла выполнено для нового семейства, поэтому система различных представителей существует.

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

Путь начинается и заканчивается непокрытыми вершинами, поэтому невыбранных рёбер на пути на одно больше, чем выбранных. Следовательно, размер паросочетания увеличится на \(1\).

Построим двудольный граф: слева доклады, справа дни, ребро означает, что доклад можно поставить в этот день. Условие задачи говорит, что для любого набора \(S\) докладов множество соседних дней имеет размер не меньше \(|S|\). По теореме Холла есть паросочетание, покрывающее все доклады. Оно и задаёт расписание.

Если представители выбраны, то любые \(k\) секций имеют \(k\) разных представителей, все они лежат в объединении этих секций. Поэтому объединение содержит не меньше \(k\) школьников.

Обратно, условие про объединения — это условие Холла для множеств школьников, соответствующих секциям. По теореме Холла существует система различных представителей.

Удалим две правые вершины. Для любого непустого \(S\subseteq A\) его множество соседей потеряет не больше двух вершин. Поэтому новый размер соседства не меньше \(|S|+2-2=|S|\).

Условие Холла сохраняется, значит, существует паросочетание, покрывающее левую долю.

Для любого \(S\) слева из него выходит не меньше \(5|S|\) рёбер. Все эти рёбра входят в \(N(S)\), а каждая правая вершина принимает не больше \(4\) таких рёбер. Значит, \(5|S|\le4|N(S)|\), откуда \(|N(S)|\ge \frac54|S|\ge |S|\).

По теореме Холла есть паросочетание, покрывающее левую долю.

Пусть доли \(A\) и \(B\). Считая рёбра по долям, получаем \(d|A|=d|B|\), значит, \(|A|=|B|\).

По задаче о регулярном двудольном графе есть паросочетание, покрывающее \(A\). Так как доли равны, оно покрывает и \(B\). Следовательно, паросочетание совершенное.

Построим двудольный граф: экзамен соединён с днём, если его можно провести в этот день. Проверим условие Холла.

Для одного экзамена доступно хотя бы \(n-1\) дней, а при \(n\ge2\) это не меньше \(1\). Если взято \(k\ge2\) экзаменов, то любой день доступен хотя бы одному из них: ведь один день может быть запрещён не более чем для одного экзамена. Значит, объединение доступных дней равно всем \(n\) дням, а \(n\ge k\).

Условие Холла выполнено для любого набора экзаменов. Следовательно, существует расписание с разными днями.

По определению увеличивающий путь начинается и заканчивается непокрытыми вершинами, а рёбра на нём чередуются. Переключение статуса рёбер вдоль пути сохраняет свойство быть паросочетанием и добавляет на одно ребро больше, чем удаляет. Значит, размер паросочетания увеличивается на \(1\). Следовательно, исходное паросочетание не было максимальным по размеру.

Если увеличивающий путь есть, то размер паросочетания можно увеличить, значит, оно не максимально.

Обратно, пусть существует паросочетание \(M'\) большего размера, чем \(M\). Рассмотрим граф, состоящий из рёбер, которые входят ровно в одно из \(M\) и \(M'\). В этом графе степени вершин не превосходят \(2\), поэтому его компоненты — пути и циклы, где рёбра из \(M\) и \(M'\) чередуются.

Так как \(|M'|>|M|\), в какой-то компоненте рёбер из \(M'\) больше, чем рёбер из \(M\). Цикл имеет поровну рёбер обоих типов, значит, это путь. Он начинается и заканчивается рёбрами из \(M'\), а его концы не покрыты \(M\). Следовательно, это увеличивающий путь относительно \(M\). Противоречие отсутствию увеличивающих путей.

В \(d\)-регулярном двудольном графе есть совершенное паросочетание. Удалим его рёбра. У каждой вершины степень уменьшится на \(1\), поэтому оставшийся граф будет \((d-1)\)-регулярным и двудольным.

Повторяем рассуждение: находим совершенное паросочетание, удаляем его. Через \(d\) шагов все рёбра будут удалены, а найденные паросочетания попарно не пересекаются и покрывают все рёбра.

Возьмём любые \(k\) множеств. В них суммарно не меньше \(rk\) вхождений элементов, потому что каждое множество имеет размер не меньше \(r\). Каждый элемент из их объединения может быть посчитан не более \(r\) раз, так как он принадлежит не более чем \(r\) множествам всего.

Если размер объединения равен \(u\), то \(rk\le ru\), значит, \(u\ge k\). Условие Холла выполнено для любых \(k\) множеств. Следовательно, система различных представителей существует.