Теорема Холла — не просто абстрактная математика. Это практический инструмент, который помогает организовать работу, составить расписание, распределить задачи. Научившись ей пользоваться, вы сможете решать реальные проблемы — от организации школьного праздника до планирования сложных проектов.
Введение: О чём пойдёт речь?
Представьте, что вы организатор школьного мероприятия. Есть задачи (оформить зал, написать сценарий, сделать музыку) и есть ученики, которые умеют делать только некоторые из этих задач. Можно ли всем найти работу по силам, чтобы все задачи были выполнены разными людьми?
Именно на этот вопрос отвечает теорема Холла — математический инструмент, который появился в 1935 году и с тех пор помогает решать тысячи практических задач.
Основные понятия — что нужно знать?
1. Двудольный граф (самое важное!)
Что это? Граф, вершины которого можно разбить на две группы так, что все связи идут только между вершинами из разных групп.
Простой пример:
- Левая группа: ученики {Аня, Боря, Вова}
- Правая группа: задачи {№1, №2, №3}
- Рёбра: Аня умеет задачи №1 и №2, Боря — №2 и №3, Вова — №1 и №3
Зачем это нужно? Любую задачу на распределение можно представить как двудольный граф!
2. Паросочетание (что мы ищем)
Что это? Набор пар (ученик → задача), где каждый ученик и каждая задача встречаются не больше одного раза.
Идеальное паросочетание: Когда ВСЕ ученики получили задачи и ВСЕ задачи распределены.
3. Степень вершины (сколько у кого вариантов)
Что это? Количество рёбер, выходящих из вершины.
Пример: Если у Ани 3 варианта задач, то её степень = 3.
Теорема Холла: формулировка
Формально: В двудольном графе существует паросочетание, покрывающее все вершины левой доли, тогда и только тогда, когда для любого подмножества A левой доли выполняется: |N(A)| ≥ |A|.
Иначе: Можно подобрать каждому человеку уникальную работу тогда и только тогда, когда для любой группы из k человек найдётся хотя бы k доступных для них вариантов.
10 типов задач и приёмы их решения
Тип 1: Простые задачи на распределение
Пример: «4 друга решили по 3 задачи из 6, каждую задачу решили ровно двое. Можно ли выбрать по одной задаче от каждого так, чтобы все задачи были разными?»
Шаг 1: Подсчитаем общее число решений задач
- Каждый из 4 друзей решил по 3 задачи → всего «решений»: 4⋅3=12.
- Каждую из 6 задач решили ровно двое → также 6⋅2=12.
Числа совпадают — условие согласовано.
Шаг 2: Применим теорему Холла
Во всех случаях условие Холла выполняется → существует требуемый выбор.
Шаг 3. Построим конкретный пример распределения:
| Друг | Задачи |
|---|---|
| A | T1, T2, T3 |
| B | T1, T4, T5 |
| C | T2, T4, T6 |
| D | T3, T5, T6 |
Проверим, каждую ли задачу решили ровно двое:
- T1: A, B ✅
- T2: A, C ✅
- T3: A, D ✅
- T4: B, C ✅
- T5: B, D ✅
- T6: C, D ✅
Отлично.
Теперь выберем:
- От A — T1
- От B — T4
- От C — T6
- От D — T3
Все разные → успех.
Ответ: Да, всегда можно выбрать по одной задаче от каждого из четырёх друзей так, чтобы все выбранные задачи были различны.
Тип 2: Циклические графы
Пример: «4 девушки и 4 парня стоят в кругу и знакомы только со своими соседями: слева и справа. Можно ли составить 4 пары «девушка–парень», чтобы каждый был в паре ровно один раз?«
Особенность: Граф образует чётный цикл.
Приём: В таком «круге» с чётным числом участников (8 человек) и чередованием полов всегда можно выбрать пары, просто брать каждую вторую связь (ребро) в круге.
✅ Как это сделать? Два простых способа:
Способ 1 — берём пары по «часовой стрелке»:
- Д₁ – П₁
- Д₂ – П₂
- Д₃ – П₃
- Д₄ – П₄
Способ 2 — берём «сдвигом»:
- Д₁ – П₄
- Д₂ – П₁
- Д₃ – П₂
- Д₄ – П₃
В обоих случаях:
Все пары — из реально существующих знакомств (соседи в круге) ✅
Все пары — «девушка + парень» ✅
Каждый человек — ровно в одной паре ✅
Ответ: Да, можно. В таком круге из 4 девушек и 4 парней всегда найдётся способ составить 4 хорошие пары, и даже двумя разными способами.
Тип 3: Регулярные графы ⭐ ОСОБЫЙ СЛУЧАЙ
Определение: Граф, где все вершины имеют одинаковую степень (одинаковое количество связей), называется регулярным.
Пример: «5 студентов, каждый выбрал 2 темы, каждая тема понравилась 2 студентам. Можно ли дать всем разные темы?»
✅ Ответ: Да, можно!
Важнейшее правило: В k-регулярном двудольном графе с равными долями совершенное паросочетание существует ВСЕГДА!
Запомните: Видите «все степени одинаковы» + «групп поровну» → сразу ответ «ДА»!
Тип 4: Системы различных представителей — СРП
Есть несколько групп (например, комитетов), и в каждой — список кандидатов.
Нужно выбрать по одному кандидату от каждой группы, чтобы все выбранные были разными людьми.
Проще говоря: «Можно ли назначить по одному человеку в каждый комитет так, чтобы никто не работал в двух местах сразу?»
Пример: «4 комитета, кандидаты: К1: {Маша, Петя}, К2: {Петя, Саша}, К3: {Саша, Даша}, К4: {Даша, Маша}. Можно ли выбрать 4 разных представителя?»
Любые m комитетов вместе должны предлагать хотя бы m разных кандидатов.
Если это верно для всех групп комитетов — от 1 до всех — то СРП существует.
Если хоть где-то нарушено — невозможно.
Приём решения: Проверяем ВСЕ возможные комбинации комитетов:
1 комитет: у каждого минимум 2 кандидата → ≥1 → ✅
2 комитета:
К1+К2 = {Маша, Петя, Саша} → 3 ≥ 2 → ✅
К2+К3 = {Петя, Саша, Даша} → 3 ≥ 2 → ✅
К1+К4 = {Маша, Петя, Даша} → 3 ≥ 2 → ✅
— и так далее → все пары в порядке.
3 комитета:
К1+К2+К3 = {Маша, Петя, Саша, Даша} → 4 ≥ 3 → ✅
Любая тройка — всё равно все 4 имени → ✅
Все 4 комитета: кандидаты = {Маша, Петя, Саша, Даша} → 4 = 4 → ✅
Вывод: условие выполнено → можно!
Например:
- К1 → Маша
- К2 → Петя
- К3 → Саша
- К4 → Даша
Не нужно перебирать все комбинации (это долго!).
Достаточно проверить все подмножества групп на выполнение правила «кандидатов ≥ групп» — это и есть условие Холла.
Тип 5: Контрпримеры — учимся на ошибках
Иногда задача кажется решаемой, но на самом деле невозможна.
Чтобы не тратить время на поиски решения, которое не существует, сначала проверь самое простое условие..
Пример: «3 кружка, преподаватели: К1: {Анна, Борис}, К2: {Анна}, К3: {Борис}. Вопрос: можно ли назначить по одному разному преподавателю в каждый кружок?
Прием: Если всех возможных кандидатов вместе меньше, чем нужно заполнить позиций — сразу отвечаем: «Нет!»
В нашем случае:
- Всего кандидатов: Анна и Борис → 2 человека
- Кружков: 3
- 2 < 3 → невозможно назначить 3 разных преподавателей!
Тип 6: Полные двудольные графы
Определение: Граф, где каждая вершина левой доли соединена с каждой вершиной правой доли называется полным двудольным графом..
Обозначение: Kₙ,ₙ (например, K₃,₃ — 3 на 3)
Пример: «3 старшие команды и 3 младшие. Все старшие готовы играть с любой младшей. Можно ли составить 3 пары «старшая — младшая», чтобы каждая команда участвовала ровно в одной паре?
Ответ: Да — и даже многими способами!
Приём: В полном двудольном графе Kₙ,ₙ решение существует ВСЕГДА!
Тип 7: Граничные случаи
Иногда система всё ещё позволяет назначить разные пары, но только потому, что всё идеально сбалансировано. Если чуть-чуть что-то изменить — например, убрать одного кандидата или добавить ещё одну позицию — всё развалится. Такие ситуации называют «граничными» или «узкими местами».
Пример: «Стенды: ‘Наука’ → {Аня, Боря}, ‘Искусство’ → {Аня, Боря}, ‘Спорт’ → {Витя, Галя}, ‘Техника’ → {Витя, Галя}»
✅ Да! Например:
- Наука → Аня
- Искусство → Боря
- Спорт → Витя
- Техника → Галя
Всё отлично — но только потому, что:
- Первые 2 стенда делят ровно 2 кандидата → 2 = 2
- Последние 2 стенда делят ровно 2 других кандидата → 2 = 2
❗ Нигде нет «запаса»: кандидатов ровно столько, сколько нужно.
Особенность: Решение существует, но система «на грани» нарушения.
Приём: Ищите подмножества, где |N(A)| = |A| (ровно столько кандидатов, сколько нужно).
Алгоритм решения — пошагово
Шаг 1: Определите структуру задачи
- Левая доля: Кому назначаем? (ученики, девушки, комитеты)
- Правая доля: Что назначаем? (задачи, парни, представители)
- Связи: Кто что может делать?
Шаг 2: Проверьте частные случаи (это сэкономит время!)
- Все степени одинаковы и групп поровну? → ДА, решение есть! (регулярный граф)
- Это полный граф Kₙ,ₙ? → ДА, решение есть!
- Это чётный цикл? → ДА, решение есть!
- Кандидатов меньше, чем позиций? → НЕТ, решения нет!
Шаг 3: Если не попали в частные случаи — проверяйте условие Холла
- Для каждой возможной группы A левой доли:
- Найдите N(A) — всех соседей этой группы
- Сравните: |N(A)| ≥ |A|?
- Секрет экономии времени: Проверяйте не все группы, а:
- Самые большие группы
- Группы, которые кажутся «проблемными»
- Группы с общими соседями
Шаг 4: Интерпретируйте результат
- Если для ВСЕХ групп |N(A)| ≥ |A| → решение СУЩЕСТВУЕТ
- Если нашлась хотя бы одна группа, где |N(A)| < |A| → решения НЕТ
Частые ошибки и как их избежать
Ошибка 1: «У каждого есть вариант → значит, можно всем найти работу»
Неправильно! Даже если у каждого ученика есть варианты, может случиться так, что у двух учеников одинаковые единственные варианты.
Правильно: Проверяйте группы! Важно, чтобы у каждой ГРУППЫ было достаточно вариантов.
Ошибка 2: Проверять только отдельных людей
Неправильно: Проверили, что у каждого ученика есть хотя бы одна задача → решили, что всё хорошо.
Правильно: Нужно проверять ВСЕ возможные группы учеников (хотя на практике часто достаточно проверить «опасные» группы).
Ошибка 3: Путать, кто кому назначается
Неправильно: Смешивать, кто выбирает, а кого выбирают.
Правильно: Чётко определите: левая доля = кто выбирает, правая доля = кого выбирают.
Ошибка 4: Забывать про регулярные графы
Неправильно: Долго проверять все группы в регулярном графе.
Правильно: Запомнить правило: в k-регулярном двудольном графе с равными долями решение есть всегда!
Интересные факты и применение
Где используется теорема Холла?
- Расписания: Составление школьных расписаний, расписаний врачей
- Трудоустройство: Распределение выпускников по местам работы
- Спортивные турниры: Составление пар для игр
- Компьютерные сети: Распределение каналов связи
- Генетика: Анализ совместимости доноров и реципиентов
Почему это важно?
Теорема Холла не просто говорит «можно или нельзя» — она показывает, КАК искать решение. Алгоритмы, основанные на этой теореме, работают в тысячах компьютерных программ по всему миру.
Заключение: Главное — запомнить
- Теорема Холла отвечает на вопрос: можно ли всем найти уникальную работу?
- Условие: Для любой группы людей должно быть достаточно вариантов
- Регулярные графы — решение есть всегда!
- Рисуйте графы — это помогает думать
- Проверяйте группы, а не отдельных людей
Теорема Холла: 10 практических задач
Интерактивные графы с пошаговыми решениями. Кликните на кнопку "Решение", чтобы увидеть подробный разбор каждой задачи.
Раздел 1: Распределение задач
Базовые задачи на распределение работ между людьми
4 ученика решили по 3 задачи из 6. Каждую задачу решили ровно 2 ученика. Можно ли выбрать по одной задаче от каждого, чтобы все задачи были разными?
• 4 ученика × 3 задачи = 12 решённых задач
• Каждую задачу решили 2 раза ⇒ всего 12 / 2 = 6 задач
Левая доля: ученики {Аня, Боря, Вова, Галя}
Правая доля: задачи {№1, №2, №3, №4, №5, №6}
Берём любую группу из k учеников:
Каждая задача принимает максимум: 2 ребра
⇒ Задач-соседей ≥ (3k) / 2 ≥ k (при k ≥ 1)
Любые 2 ученика имеют минимум 3 уникальные задачи (6 рёбер / 2 = 3)
Пример распределения: Аня→№1, Боря→№2, Вова→№3, Галя→№4
4 девушки и 4 парня образуют круг знакомств. Аня знает Петю и Васю, Бетти — Васю и Колю, Вика — Колю и Димой, Галя — Димой и Петю. Можно ли составить 4 пары?
Граф образует чётный цикл длины 8: Аня→Петя→Галя→Дима→Вика→Коля→Бетти→Вася→Аня
В любом чётном цикле всегда можно выбрать совершенное паросочетание, взяв каждое второе ребро.
• Любые 2 девушки: минимум 3 парня ≥ 2 ✓
• Любые 3 девушки: все 4 парня ≥ 3 ✓
Идём по циклу и выбираем каждое второе ребро
Пример: Аня→Петя, Бетти→Вася, Вика→Коля, Галя→Дима
5 студентов выбрали по 2 темы курсовых. Каждая тема понравилась ровно 2 студентам. Можно ли дать всем разные темы?
• 5 студентов × 2 темы = 10 выборов
• Каждая тема выбрана 2 раза ⇒ всего тем: 10 / 2 = 5
Граф является 2-регулярным двудольным с равными долями!
• Исходит 2k рёбер
• Каждая тема принимает ≤ 2 рёбер
⇒ Соседних тем ≥ 2k/2 = k ≥ k
В k-регулярном двудольном графе с равными долями совершенное паросочетание существует всегда!
Пример: С1→Т1, С2→Т2, С3→Т3, С4→Т4, С5→Т5
Раздел 2: Системы представителей
Задачи на выбор уникальных представителей для множеств
4 комитета: К1: {Маша, Петя}, К2: {Петя, Саша}, К3: {Саша, Даша}, К4: {Даша, Маша}. Можно ли выбрать 4 разных представителя?
Нужно найти Систему Различных Представителей (СРП) для множеств:
A₁={М,П}, A₂={П,С}, A₃={С,Д}, A₄={Д,М}
• 2 комитета (К1+К2): {М,П,С} — 3 человека ≥ 2 ✓
• 3 комитета (К1+К2+К3): {М,П,С,Д} — 4 ≥ 3 ✓
• 4 комитета: {М,П,С,Д} — 4 ≥ 4 ✓
Для любого подмножества комитетов |N(A)| ≥ |A|
Можно выбрать: К1→Маша, К2→Петя, К3→Саша, К4→Даша
Все комитеты получат уникальных представителей
3 кружка, преподаватели: К1: {Анна, Борис}, К2: {Анна}, К3: {Борис}. Можно ли найти 3 разных преподавателя?
Всего кандидатов: 2 человека (Анна, Борис)
Кружков: 3
Уже видим проблему: 2 < 3
Рассмотрим множество всех трёх кружков A = {К1, К2, К3}
|N(A)| = 2
|A| = 3
2 < 3 ⇒ НАРУШЕНИЕ УСЛОВИЯ ХОЛЛА!
Три кружка "претендуют" на двух преподавателей. Кто-то должен вести два кружка.
Нужно либо найти третьего преподавателя, либо объединить кружки.
Классический контрпример нарушения теоремы Холла
3 старшие и 3 младшие команды. Каждая старшая готова играть со всеми младшими, каждая младшая — со всеми старшими. Можно ли составить 3 пары?
Это полный двудольный граф K₃,₃
Каждая старшая команда соединена с каждой младшей
Для любой группы из k старших команд:
|N(A)| = 3 ≥ k для любого k = 1, 2, 3
Условие выполняется автоматически, так как соседи всегда все 3 младшие команды
В полном двудольном графе Kₙ,ₙ всегда существует совершенное паросочетание!
Пример: С1→М1, С2→М2, С3→М3 (любые пары подойдут)
Раздел 3: Специальные случаи
Регулярные графы и граничные ситуации
4 учителя, 4 дня. Каждый учитель свободен в 2 дня, каждый день свободны 2 учителя. Можно ли составить расписание?
• Каждый учитель: степень 2 (свободен в 2 дня)
• Каждый день: степень 2 (свободны 2 учителя)
⇒ Граф 2-регулярный двудольный
2-регулярный двудольный граф всегда является объединением чётных циклов.
В каждом чётном цикле можно выбрать совершенное паросочетание, взяв каждое второе ребро.
• Исходит 2k рёбер
• Каждый день принимает ≤ 2 рёбер
⇒ Дней-соседей ≥ 2k/2 = k ≥ k
Пример: Анна→Пн, Борис→Ср, Виктор→Вт, Галина→Чт
В флешмобе поровну мужчин и женщин. Каждый сделал репост от 3 человек противоположного пола, каждый получил 3 запроса. Можно ли разбить на пары?
• n мужчин и n женщин
• Каждая вершина имеет степень 3
⇒ Граф 3-регулярный двудольный с равными долями
• От них исходит 3m запросов
• Каждая женщина принимает ≤ 3 запросов
• Если бы женщин-соседей было < m
• Они получили бы < 3m запросов
• Но запросов ровно 3m — противоречие!
⇒ Женщин-соседей ≥ m
В ЛЮБОМ k-регулярном двудольном графе с равными долями совершенное паросочетание существует всегда!
Для любых k и n пары всегда можно составить
5 юношей и 5 девушек. Каждый указал 3 желаемых соперника противоположного пола, каждый получил 3 запроса. Можно ли составить 5 пар?
• 5 юношей и 5 девушек
• Каждая вершина имеет степень 3
⇒ Граф 3-регулярный двудольный с равными долями
• Исходит 3k рёбер
• Каждая девушка принимает ≤ 3 рёбер
⇒ Девушек-соседей ≥ 3k/3 = k ≥ k
Допустим, есть k юношей с менее чем k девушками-соседями.
Тогда эти девушки получили бы менее 3k рёбер, но юноши отправили ровно 3k рёбер — противоречие!
Всегда можно составить пары в 3-регулярном графе
4 стенда: "Наука" → {Аня, Боря}, "Искусство" → {Аня, Боря}, "Спорт" → {Витя, Галя}, "Техника" → {Витя, Галя}. Можно ли найти 4 разных ответственных?
Задача состоит из двух независимых блоков:
• Блок 1: {"Наука", "Искусство"} → {Аня, Боря}
• Блок 2: {"Спорт", "Техника"} → {Витя, Галя}
Рассмотрим подмножество {"Наука", "Искусство"}:
|N(A)| = 2
|A| = 2
2 = 2 — условие выполняется впритык!
• Решение существует, но система неустойчива
• Добавь один гуманитарный стенд — решение исчезнет
• Убери одного кандидата — решение исчезнет
Всегда проверяйте подмножества, где |N(A)| = |A| — это "узкие места" системы!
Пример: Наука→Аня, Искусство→Боря, Спорт→Витя, Техника→Галя
Дополнительно
Источник: https://www.mathnet.ru/links/17373bb19c8372e842c49fc9f6838d9e/kvant794.pdf
Источник: https://www.mathnet.ru/links/991f3132f0bc4066c07539dd14c0adc6/mo416.pdf
Источник: https://www.mathnet.ru/links/4de9aba1c996d4fff2189dc840ab805a/mo422.pdf