Теорема Холла (или «теорема о свадьбах«) была придумана английским математиком Филипом Холлом в 1935 году. Он изучал, как можно правильно сочетать элементы из разных групп — например, женихов и невест, студентов и кружков, или даже книги и полки в библиотеке.
Теорема Холла
Или «теорема о свадьбах» — наглядное объяснение для школьников
Введение: Задача о свадьбах
Представьте, что в деревне есть несколько юношей и девушек, которые хотят пожениться. Каждый юноша знаком с некоторыми девушками и готов жениться только на тех, кого знает.
Задача
Можно ли всех юношей женить на девушках, которых они знают, так чтобы каждый женился только на одной девушке?
Эта задача известна как «задача о свадьбах», а её решение — теорема Холла, названная в честь английского математика Филипа Холла, который сформулировал её в 1935 году.
На самом деле, теорема Холла применяется не только к свадьбам, но и к множеству других задач:
- Распределение студентов по практикам
- Назначение работников на задачи
- Сопоставление доноров и реципиентов
Пример задачи
Слева — юноши (Ю), справа — девушки (Д). Линии показывают, кто кого знает.
Что говорит теорема Холла?
Теорема Холла даёт необходимое и достаточное условие для решения задачи о свадьбах.
Формулировка теоремы
В конечном двудольном графе существует совершенное паросочетание (каждая вершина левой доли соединена с вершиной правой доли) тогда и только тогда, когда для любого подмножества вершин левой доли количество соседних вершин в правой доле не меньше количества вершин в этом подмножестве.
Проще говоря:
- Возьмём любую группу юношей
- Посчитаем, сколько всего разных девушек они знают вместе
- Если для любой группы юношей количество известных им девушек не меньше количества юношей в группе, то всех можно женить
Это условие называется «условием Холла».
Проверка условия Холла
Выберите граф и группу юношей, чтобы проверить условие:
Графическая иллюстрация
Условие Холла: |N(S)| ≥ |S| для любого S ⊆ левой доли
Где S — подмножество юношей, N(S) — соседние девушки
Вопрос для размышления
Попробуйте в Графе 3 выбрать всех троих юношей. Что происходит с условием Холла?
Пример: Когда условие выполняется
Рассмотрим пример, где условие Холла выполняется, и всех юношей можно женить.
Ситуация
У нас есть 3 юноши (Ю1, Ю2, Ю3) и 3 девушки (Д1, Д2, Д3).
- Ю1 знаком с Д1 и Д2
- Ю2 знаком с Д2 и Д3
- Ю3 знаком с Д1 и Д3
Проверим условие Холла для всех возможных групп юношей:
- Ю1: знает 2 девушек (≥1) ✓
- Ю2: знает 2 девушек (≥1) ✓
- Ю3: знает 2 девушек (≥1) ✓
- Ю1+Ю2: знают 3 девушек (≥2) ✓
- Ю1+Ю3: знают 2 девушек (≥2) ✓
- Ю2+Ю3: знают 3 девушек (≥2) ✓
- Ю1+Ю2+Ю3: знают 3 девушек (≥3) ✓
Условие Холла выполняется для всех групп, значит, существует способ женить всех юношей!
Найдите паросочетание
Попробуйте найти, как можно поженить всех юношей:
Граф знакомств
Одно из возможных решений:
- Ю1 → Д2 (зеленая линия на графе)
- Ю2 → Д3 (зеленая линия на графе)
- Ю3 → Д1 (зеленая линия на графе)
Заметка: В этом графе условие Холла выполняется для всех подмножеств юношей.
Пример: Когда условие нарушается
Теперь рассмотрим пример, где условие Холла не выполняется, и женить всех юношей невозможно.
Ситуация
У нас есть 3 юноши (Ю1, Ю2, Ю3) и 3 девушки (Д1, Д2, Д3).
- Ю1 знаком только с Д1
- Ю2 знаком с Д1 и Д2
- Ю3 знаком с Д1 и Д2
Проверим условие Холла для всех возможных групп юношей:
- Ю1: знает 1 девушку (≥1) ✓
- Ю2: знает 2 девушек (≥1) ✓
- Ю3: знает 2 девушек (≥1) ✓
- Ю1+Ю2: знают 2 девушек (≥2) ✓
- Ю1+Ю3: знают 2 девушек (≥2) ✓
- Ю2+Ю3: знают 2 девушек (≥2) ✓
- Ю1+Ю2+Ю3: знают 2 девушек (≥3) ✗
Условие нарушается для группы всех трёх юношей! Они вместе знают только 2 девушек, а их трое. Значит, женить всех троих невозможно.
Максимум можно женить двоих юношей. Например, Ю1 на Д1 и Ю2 на Д2.
Граф с нарушением условия
Нарушение условия Холла
Все трое юношей знают только двоих девушек!
|S| = 3 (все юноши: Ю1, Ю2, Ю3)
|N(S)| = 2 (Д1 и Д2)
2 < 3 ⇒ условие Холла нарушено
Вывод: Нельзя женить всех троих юношей, так как они знают всего двух разных девушек.
Задачи для самостоятельной работы
Теперь попробуйте применить знания на практике! Решите эти задачи, используя теорему Холла.
Задача 1: Кружки по интересам
В школе есть 4 кружка: Математика (М), Информатика (И), Физика (Ф), Химия (Х).
4 студента хотят записаться на кружки:
- С1 хочет записаться на М или И
- С2 хочет записаться на И или Ф
- С3 хочет записаться на М или Ф
- С4 хочет записаться на Ф или Х
Вопрос: Можно ли распределить всех студентов по кружкам так, чтобы каждый получил один из желаемых кружков и в каждом кружке был не более один студент?
Решение задачи 1
Проверим условие Холла для всех возможных групп студентов:
- Каждый студент знает 2 кружка (≥1) ✓
- Любая пара студентов знает не менее 2 кружков (≥2) ✓
- Любые трое студентов знают не менее 3 кружков (≥3) ✓
- Все четверо студентов знают все 4 кружка (≥4) ✓
Условие Холла выполняется! Значит, распределение возможно.
Граф задачи и возможное паросочетание:
Пример распределения: С1→И, С2→Ф, С3→М, С4→Х
Зеленые линии показывают одно из возможных распределений.
Задача 2: Назначение на работу
Есть 4 работника (Р1, Р2, Р3, Р4) и 4 задачи (З1, З2, З3, З4).
Каждый работник может выполнять только некоторые задачи:
- Р1 может выполнять З1 или З2
- Р2 может выполнять З1 или З3
- Р3 может выполнять З2 или З3
- Р4 может выполнять только З3
Вопрос: Можно ли назначить каждого работника на свою задачу так, чтобы все задачи были выполнены?
Решение задачи 2
Проверим условие Холла. Рассмотрим группу всех работников {Р1, Р2, Р3, Р4}:
- |S| = 4 (Р1, Р2, Р3, Р4)
- N(S) = {З1, З2, З3} (все задачи, которые они могут выполнять)
- |N(S)| = 3
- 3 < 4 ✗
Условие Холла нарушается!
Граф задачи:
Задача З4 не доступна ни одному работнику!
Множество соседей всех работников имеет мощность 3 < 4 — условие Холла нарушено уже на полном множестве.
Максимум можно назначить 3 работника на задачи З1, З2, З3.
Задача 3: Свадьбы в деревне
В деревне 5 юношей (Ю1-Ю5) и 5 девушек (Д1-Д5).
Знакомства такие:
- Ю1 знает Д1, Д2
- Ю2 знает Д2, Д3
- Ю3 знает Д3, Д4
- Ю4 знает Д4, Д5
- Ю5 знает Д5, Д1
Вопрос: Можно ли всех женить? Проверьте условие Холла и найдите паросочетание, если оно существует.
Решение задачи 3
Проверим условие Холла для различных групп юношей:
- Каждый юноша знает 2 девушек (≥1) ✓
- Любые двое соседних юношей знают 3 девушек (≥2) ✓
- Любые трое последовательных юношей знают 4 девушек (≥3) ✓
- Благодаря циклической структуре, любое подмножество юношей «охватывает» как минимум столько же девушек.
- Все пятеро юношей знают всех 5 девушек (≥5) ✓
Условие Холла выполняется! Значит, всех можно женить.
Граф задачи и одно из возможных паросочетаний:
Пример паросочетания: Ю1→Д1, Ю2→Д2, Ю3→Д3, Ю4→Д4, Ю5→Д5
Другой вариант: Ю1→Д2, Ю2→Д3, Ю3→Д4, Ю4→Д5, Ю5→Д1
Зеленые линии показывают одно из возможных распределений.
Этот граф представляет собой «цикл», что гарантирует существование совершенного паросочетания.
Как решать задачи?
Шаг 1: Постройте двудольный граф
Шаг 2: Проверьте условие Холла для всех возможных групп левой доли
Шаг 3: Если условие выполняется — паросочетание существует
Шаг 4: Если условие нарушается — паросочетания не существует
Советы для решения
- Начинайте проверку с маленьких групп
- Особое внимание уделяйте группам, которые знают мало общих вершин
- Ищите «узкие места» в графе
- Попробуйте найти контрпример, если считаете, что паросочетания нет
Дополнительная задача
Придумайте свой пример с 4 юношами и 4 девушками, где:
- Условие Холла выполняется
- Условие Холла нарушается
Нарисуйте графы и проверьте свои примеры.
Где применяется теорема Холла?
Теорема Холла — не просто абстрактная математическая идея. Она имеет множество практических применений!
Применение в реальной жизни
- Распределение студентов по практикам: Каждый студент имеет список предпочтительных мест практики. Теорема Холла помогает определить, можно ли всех студентов распределить согласно их предпочтениям.
- Назначение работников на задачи: Каждый работник имеет набор навыков. Теорема помогает определить, можно ли назначить каждого работника на задачу, соответствующую его навыкам.
- Совершенные паросочетания в графах: В информатике теорема Холла используется в алгоритмах поиска максимального паросочетания.
Теорема Холла также является основой для более сложных теорем в теории графов и комбинаторике.
Интересные факты
- Теорема Холла была доказана в 1935 году Филипа Холла
- Иногда её называют «теоремой о свадьбах» из-за популярной формулировки
- Теорема обобщается на бесконечные множества (теорема Холла о бракосочетаниях)
- Существует алгоритм на основе теоремы Холла, который находит максимальное паросочетание в двудольном графе
Теорема Холла в науке
Комбинаторика: Подсчет комбинаторных конструкций
Теория графов: Изучение двудольных графов
Информатика: Алгоритмы сопоставления
Экономика: Теория matching markets
Биология: Сопоставление доноров и реципиентов
Теорема о свадьбах
Теорема Холла иногда называется «теоремом о свадьбах», потому что её можно сформулировать так:
«Если каждый из множества юношей знаком с некоторыми девушками, то можно всех женить на знакомых девушках тогда и только тогда, когда любая группа из k юношей знает в совокупности не менее k девушек.»
Теорема Холла: Ученики и проекты
Ситуация: В классе есть ученики и учебные проекты. Каждый ученик может работать только над теми проектами, в которых он разбирается.
Вопрос: Можно ли распределить всех учеников так, чтобы:
- Каждый ученик работал ровно над одним проектом
- Над каждым проектом работал ровно один ученик
- Ученик работал только над проектом, в котором он разбирается
|S| — количество учеников в группе
|N(S)| — количество проектов, которые знают ученики из группы S
Условие: Для ЛЮБОЙ группы учеников количество доступных проектов должно быть не меньше количества учеников.
Сценарий 1: Условие выполнено
4 ученика и 4 проекта. Каждый ученик знает 2 проекта.
Проверка: Любая группа учеников знает не меньше проектов, чем учеников в группе.
Можно распределить! Каждый получит свой проект.
Сценарий 2: Условие нарушено
3 ученика и 3 проекта, но у Бориса и Виктора оба интересуются ТОЛЬКО Физикой.
Проблема: Группа {Борис, Виктор} знает только 1 проект (Физику).
2 ученика → 1 проект — распределить невозможно!
Сценарий 3: Пограничный случай
3 ученика и 3 проекта. У каждого разные интересы.
Проверка: Даже у групп из 2-х учеников всегда есть хотя бы 2 разных проекта.
Можно распределить! Но нужно быть внимательным при выборе.
Возможное распределение
Как найти решение?
1. Начните с ученика, у которого меньше всего вариантов
2. Назначьте ему один из доступных проектов
3. Удалите этого ученика и проект
4. Повторяйте для оставшихся
Если условие Холла выполнено, решение всегда найдётся!
Дополнительно
Источник: https://www.mathnet.ru/links/17373bb19c8372e842c49fc9f6838d9e/kvant794.pdf
Источник: https://www.mathnet.ru/links/991f3132f0bc4066c07539dd14c0adc6/mo416.pdf
Источник: https://www.mathnet.ru/links/4de9aba1c996d4fff2189dc840ab805a/mo422.pdf