Математика · объяснение и практика

Теорема Холла: почему общего числа мест недостаточно

Проверяем объединения допустимых выборов для каждой группы и доказываем критерий разных представителей; отличаем нехватку внутри группы от общего числа мест.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Пусть A₁,…,Aₙ — конечные множества допустимых вариантов. Выбрать различные xᵢ∈Aᵢ можно тогда и только тогда, когда для любой группы индексов J объединение её множеств содержит не меньше |J| элементов. Это условие Холла проверяет каждую группу, а не только все множества вместе.

Общий запас может скрывать местную нехватку

Представим распределение разных заданий между учениками, по одному на человека. Множество Aᵢ содержит только подходящие i-му ученику задания. Один вариант нельзя назначить дважды, даже если он подходит многим. Если троим доступны только два задания, посторонние свободные задания положения не исправят: этим троим всё равно не хватит различных представителей.

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

Проверка только одиночек или всего семейства слабее. Например, три первых списка могут равняться {1,2}, а четвёртый — {3,4}. Всего есть четыре разных варианта для четырёх участников, каждый список непуст, но подгруппа первых троих имеет лишь два возможных места.

Почему условия достаточно: разделяем тесную группу

Достаточность докажем индукцией по числу списков. Один непустой список очевиден. Если есть непустая собственная группа J, для которой размер объединения ровно |J|, по индукции распределяем эти варианты внутри группы. В остальных списках удаляем всё это объединение: назначенные элементы больше использовать нельзя.

Для любой оставшейся группы K прежнее условие, применённое к J∪K, даёт не меньше |J|+|K| вариантов. После удаления ровно |J| занятых элементов остаётся хотя бы |K|. Значит, сокращённые списки снова удовлетворяют условию Холла. Индукция распределяет остаток, и два распределения используют непересекающиеся запасы.

Пример

Для А доступны {x,y}, для Б — {y,z}, для В — {x,z}. Постройте разных представителей и проверьте не только полный запас.

Можно назначить А→x, Б→y, В→z. Каждый одиночный список имеет два варианта, объединение любой пары равно {x,y,z} и имеет три элемента, объединение всех троих тоже имеет три. Таким образом, условия выполнены для всех семи непустых групп, а записанное назначение непосредственно подтверждает существование.

Если тесной собственной группы нет

Остаётся случай, когда всякая непустая собственная группа имеет хотя бы на один вариант больше своего размера. Выберем произвольный элемент последнего списка, назначим его последнему участнику и удалим этот элемент из остальных списков. Любая группа оставшихся участников теряет не больше одного варианта, поэтому её запас всё ещё не меньше её размера. Снова применяем индукцию.

Оба случая вместе доказывают существование, но не единственность назначения. Условия не выбирают самый дешёвый или самый желанный вариант: в модели есть только допустимость и требование различности. Алгоритм увеличивающих путей способен находить назначение, а теорема объясняет, какая именно группа служит свидетельством невозможности.

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

От чтения к действию

А теперь — вы

У первых четырёх участников один и тот же список {1,2,3}, у пятого — {4,5}. Все пары и весь запас выглядят достаточными. Возможен ли общий выбор?

Частые вопросы

Достаточно ли проверить только пары списков?

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

Теорема требует занять все имеющиеся места?

Нет. Требуется дать по одному разному представителю каждому списку. Избыточные варианты могут остаться свободными.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться