Теорема холла о браке - Halls marriage theorem - Wikipedia

В математика, Теорема холла о браке, доказано Филип Холл  (1935 ), это теорема с двумя эквивалентными формулировками:

• В комбинаторный формулировка имеет дело с набором конечный наборы. Это дает необходимое и достаточное условие для возможности выбора отдельного элемента из каждого набора.
• В теоретический график формулировка касается двудольный граф. Он дает необходимое и достаточное условие для нахождения соответствие покрывающий хотя бы одну сторону графика.

Комбинаторная формулировка

Позволять ${\displaystyle S}$ быть (возможно, бесконечным) семья конечных подмножества из ${\displaystyle X}$, где члены ${\displaystyle S}$ находятся считаться с множеством (То есть, ${\displaystyle S}$ может содержать один и тот же набор несколько раз).^[1]

А поперечный за ${\displaystyle S}$ это изображение из инъективная функция ${\displaystyle f}$ из ${\displaystyle S}$ к ${\displaystyle X}$ такой, что ${\displaystyle f(s)}$ является элементом множества ${\displaystyle s}$ для каждого ${\displaystyle s}$ в семье ${\displaystyle S}$. Другими словами, ${\displaystyle f}$ выбирает по одному представителю из каждого набора в ${\displaystyle S}$ таким образом, что нет двух из этих представителей равных. Альтернативный термин для поперечный является система различных представителей.

Коллекция S удовлетворяет состояние брака когда для каждого подсемейства ${\displaystyle W\subseteq S}$,

${\displaystyle |W|\leq {\Bigl |}\bigcup _{A\in W}A{\Bigr |}.}$

Другими словами, условие брака утверждает, что каждое подсемейство ${\displaystyle S}$ содержит по крайней мере столько различных членов, сколько наборов в подсемействе.

Если условие брака не выполняется, то не может быть поперечного ${\displaystyle f}$ из ${\displaystyle S}$.

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

Предположим, что условие брака не выполняется, т. Е. Что для некоторой подгруппы ${\displaystyle W_{0}}$ из ${\displaystyle S}$, ${\displaystyle \textstyle |W_{0}|>|\bigcup _{A\in W_{0}}A|.}$ Предположим от противного, что трансверсаль ${\displaystyle f(S)}$ из ${\displaystyle S}$ тоже существует. Ограничение ${\displaystyle f}$ к оскорбительной субколлекции ${\displaystyle W_{0}}$ будет инъективной функцией от ${\displaystyle W_{0}}$ в ${\displaystyle \textstyle \bigcup _{A\in W_{0}}}$. Это невозможно принцип голубятни поскольку ${\displaystyle \textstyle |W_{0}|>|\bigcup _{A\in W_{0}}A|}$. Следовательно, если условие брака не выполняется, трансверсали не может существовать.

Теорема Холла утверждает, что верно и обратное:

Теорема Холла о браке — Семья S конечных множеств имеет трансверсаль тогда и только тогда, когда S удовлетворяет условию брака.

Примеры

пример 1, условие брака выполнено

Пример 1: рассмотрим S = {А₁, А₂, А₃} с

А₁ = {1, 2, 3}

А₂ = {1, 4, 5}

А₃ = {3, 5}.

Допустимая трансверсаль будет (1, 4, 5). (Обратите внимание, что это не уникально: например, (2, 1, 3) работает одинаково хорошо.)

пример 2, условие брака нарушено

Пример 2: рассмотрим S = {А₁, А₂, А₃, А₄} с

А₁ = {2, 3, 4, 5}

А₂ = {4, 5}

А₃ = {5}

А₄ = {4}.

Не существует допустимого трансверсального перехода; условие брака нарушено, как показывает подсемейство W = {А₂, А₃, А₄}. Здесь количество наборов в подсемействе |W| = 3, а объединение трех множеств А₂ U А₃ U А₄ содержит всего 2 элемента Икс.

Пример 3: рассмотрим S = {А₁, А₂, А₃, А₄} с

А₁ = {а, б, c}

А₂ = {б, d}

А₃ = {а, б, d}

А₄ = {б, d}.

Единственные допустимые трансверсалии (c, б, а, d) и (c, d, а, б).

Заявление о браке

Стандартный пример применения теоремы о браке - представить две группы; один из п мужчины, и один из п женщины. Для каждой женщины есть подмножество мужчин, за любого из которых она с радостью выйдет замуж; и любой мужчина был бы счастлив жениться на женщине, которая хочет жениться на нем. Подумайте, возможно ли объединиться в пары (в брак ) мужчин и женщин, чтобы каждый был счастлив.

Если мы позволим А_я быть набором мужчин, которые я-я женщина была бы счастлива выйти замуж, тогда теорема о браке утверждает, что каждая женщина может счастливо выйти замуж за мужчину тогда и только тогда, когда совокупность множеств {А_я} соответствует условию брака.

Обратите внимание, что условием брака является то, что для любого подмножества ${\displaystyle I}$ женщин, количество мужчин, на которых хотя бы одна из женщин была бы счастлива выйти замуж, ${\displaystyle |\bigcup _{i\in I}A_{i}|}$, быть не меньше, чем количество женщин в этой подгруппе, ${\displaystyle |I|}$. Очевидно, что это условие необходимо, как будто это не выдерживает, не хватает мужчин, чтобы разделить между ${\displaystyle I}$ женщины. Что интересно, это еще и достаточный условие.

Теоретико-графическая формулировка

синие края представляют собой соответствие

Позволять грамм быть конечным двудольный граф с двудольными множествами Икс и Y (т.е. грамм := (Икс + Y, E)). An X-идеальное соответствие (также называемый: X-насыщающее соответствие) это соответствие покрывающий каждую вершину в Икс.

Для подмножества W из Икс, позволять N_грамм(W) обозначают район из W в грамм, т.е. множество всех вершин в Y соседний к какому-то элементу W. Теорема о браке в этой формулировке утверждает, что существует Икс-идеальное соответствие если и только если для каждого подмножества W из Икс:

${\displaystyle |W|\leq |N_{G}(W)|.}$

Другими словами: каждое подмножество W из Икс имеет достаточно много смежных вершин в Y.

Доказательство теоретико-графовой версии

Легкое направление: мы предполагаем, что некоторое соответствие M насыщает каждую вершину Икс, и доказать, что условие Холла выполняется для всех W ⊆ Икс. Позволять M(W) обозначим множество всех вершин в Y соответствует M к данному W. По определению соответствия, |M(W)| = |W |, Но M(W) ⊆ N_грамм(W), поскольку все элементы M(W) являются соседями W. Итак, | N_грамм(W)| ≥ |M(W) | а значит, | N_грамм(W)| ≥ |W|.

Жесткое направление: мы предполагаем, что нет Икс-точное соответствие и доказать, что условие Холла нарушается хотя бы для одного W ⊆ Икс. Позволять M быть максимальным соответствием, и ты вершина не насыщена M. Рассмотреть все чередующиеся пути (т.е. пути в грамм попеременно используя края снаружи и внутри M) начиная с ты. Пусть множество всех точек в Y подключен к ты этими чередующимися путями быть Z, а множество всех точек в Икс подключен к ты этими чередующимися путями (включая ты сам) быть W. Никакой максимальный чередующийся путь не может заканчиваться вершиной в Y, иначе это будет расширение пути, чтобы мы могли увеличить M к строго большему соответствию путем переключения статуса (принадлежит M или нет) всех краев пути. Таким образом, каждая вершина в Z совпадает M с вершиной в W \ {ты}. И наоборот, каждая вершина v в W \ {ты} соответствует M к вершине в Z (а именно, вершина, предшествующая v на переменном пути, заканчивающемся в v). Таким образом, M обеспечивает взаимное соответствие W \ {ты} и Z, что означает |W| = |Z| + 1. С другой стороны, N_грамм(W) ⊆ Z: позволять v в Y быть соединенным с вершиной ш в W. Край (ш,v) должен быть в M, иначе ты достигает ш через альтернативный путь, не содержащий v, и мы могли бы пойти по альтернативному пути, оканчивающемуся на ш и расширить его с помощью v, получая дополнительный путь (что снова противоречило бы максимальности M). Следовательно v должен быть в Z, поэтому | N_грамм(W)| ≤ |Z| = |W| − 1 < |W|.

Конструктивное доказательство жесткого направления

Определить Нарушитель зала как подмножество W X, для которого | N_грамм(W)| < |W|, Если W является нарушителем Холла, то не существует паросочетания, насыщающего все вершины W. Следовательно, также нет соответствия, которое насыщает Икс. Теорема Холла о браке гласит, что граф содержит Икс-идеальное соответствие тогда и только тогда, когда оно не содержит нарушителей Холла. Следующий алгоритм доказывает жесткую направленность теоремы: он находит либо Икс-идеальное соответствие или нарушитель Холла. В качестве подпрограммы он использует алгоритм, который при совпадении M и непревзойденная вершина Икс₀, либо находит M- фрагментирующий путь или нарушитель Холла, содержащий Икс₀.

Оно использует

1. Инициализировать M знак равно // Пустое соответствие.
2. Утверждать: M соответствует в грамм.
3. Если M насыщает все вершины ИКС, тогда вернуть Икс-идеальное соответствие M.
4. Позволять Икс₀ - несопоставленная вершина (вершина в Икс V (M)).
5. С использованием Нарушитель зала алгоритма, найдите либо нарушителя Холла, либо M-аугментация пути.
6. В первом случае вернуть нарушителя зала.
7. Во втором случае используйте M-аугментация пути для увеличения размера M (по одному краю), и вернуться к шагу 2.

На каждой итерации M растет одним краем. Следовательно, этот алгоритм должен завершиться не позднее, чем через |E| итераций. Каждая итерация занимает не более |Икс| время. Общая сложность выполнения аналогична методу Форда-Фулкерсона для поиска максимальное соответствие количества элементов.

Эквивалентность комбинаторной формулировки и теоретико-графической формулировки

Позволять S = (А₁, А₂, ..., А_п) где А_я - конечные множества, которые не обязательно должны быть различными. Пусть набор Икс = {А₁, А₂, ..., А_п} (то есть набор имён элементов S) и множество Y быть объединением всех элементов во всех А_я.

Мы формируем конечный двудольный граф грамм := (Икс + Y, E) с двудольными множествами Икс и Y присоединив любой элемент в Y для каждого А_я членом которого он является. Пересечение S является Икс-идеально соответствие (соответствие, которое покрывает каждую вершину в Икс) двудольного графа грамм. Таким образом, проблема комбинаторной формулировки может быть легко преобразована в задачу теоретико-графовой формулировки.

Топологическое доказательство

Теорема Холла может быть доказана (неконструктивно) на основе Лемма Спернера.^{[2]:Thm.4.1,4.2}

Приложения

У теоремы есть много других интересных «внебрачных» приложений. Например, возьмите стандартная колода карт и разложите их на 13 стопок по 4 карты в каждой. Затем, используя теорему о браке, мы можем показать, что всегда можно выбрать ровно 1 карту из каждой стопки, так что 13 выбранных карт содержат ровно одну карту каждого ранга (Туз, 2, 3, ..., Дама, Король).

Говоря более абстрактно, пусть грамм быть группа, и ЧАС быть конечным подгруппа из грамм. Тогда теорему о браке можно использовать, чтобы показать, что существует множество Т такой, что Т является трансверсалью как для множества левых смежные классы и правые смежные классы ЧАС в грамм.

Теорема о браке используется в обычных доказательствах того факта, что (р × п) Латинский прямоугольник всегда можно расширить до ((р +1) × п) Латинский прямоугольник при р < п, и так, в конечном итоге Латинский квадрат.

Логические эквивалентности

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

• В Теорема Кенига – Эгервари. (1931) (Денес Кёниг, Jen Egerváry )
• Теорема Кенига^[3]
• Теорема Менгера (1927)
• В теорема о максимальном потоке и минимальном отсечении (Алгоритм Форда – Фулкерсона)
• В Теорема Биркгофа – фон Неймана. (1946)
• Теорема Дилворта.

Особенно,^[4][5] есть простые доказательства импликаций теоремы Дилворта ⇔ теоремы Холла ⇔ теоремы Кёнига – Эгервари ⇔ теоремы Кенига.

Бесконечные семьи

Маршалл Холл младший вариант

Изучая Филип Холл оригинальное доказательство тщательно, Маршалл Холл младший (не имеющий отношения к Филиппу Холлу) смог настроить результат таким образом, чтобы доказательство работало для бесконечного S.^[6] Этот вариант уточняет теорему о браке и дает нижнюю оценку количества трансверсалей, которые S можно иметь. Этот вариант:^[7]

Предположим, что (А₁, А₂, ..., А_п), где А_я конечные множества, которые не обязательно должны быть различными, это семейство множеств, удовлетворяющих условию брака, и предположим, что |А_я| ≥ р за я = 1, ..., п. Тогда количество различных трансверсалей для семейства не менее р! если р ≤ п и р(р − 1) ... (р − п + 1) если р > п.

Напомним, трансверсаль для семьи S является упорядоченной последовательностью, поэтому две разные трансверсали могут иметь одинаковые элементы. Например, семья А₁ = {1, 2, 3}, А₂ = {1, 2, 5} имеет и (1, 2), и (2, 1) как различные трансверсали.

Условие брака не распространяется

Следующий пример, принадлежащий Маршаллу Холлу-младшему, показывает, что условие брака не гарантирует существование трансверсали в бесконечной семье, в которой разрешены бесконечные множества.

Позволять S быть семьей, А₀ = {1, 2, 3, ...}, А₁ = {1}, А₂ = {2}, ..., А_я = {я }, ...

Условие брака выполняется для этой бесконечной семьи, но трансверсаль не может быть построена.^[8]

Более общая проблема выбора (не обязательно отдельного) элемента из каждого набора непустой наборы (без ограничений в отношении количества наборов или размера наборов) разрешены в целом, только если аксиома выбора принято.

Теорема о браке распространяется на бесконечный случай, если ее правильно сформулировать. Для двудольного графа со сторонами А и B, мы говорим, что подмножество C из B меньше или равен размеру подмножества D из А в графике если в графе существует инъекция (а именно, с использованием только ребер графа) из C к D, и что он будет строго меньше в графе, если, кроме того, в графе нет инъекции в другом направлении. Обратите внимание, что опуская в графике дает обычное понятие сравнения мощностей. Теорема о бесконечном браке утверждает, что существует инъекция из А к B в графе тогда и только тогда, когда нет подмножества C из А такой, что N(C) строго меньше, чем C в графике.^[9]

Вариант дробного соответствия

А дробное соответствие в графе - это присвоение неотрицательных весов каждому ребру, так что сумма весов, смежных с каждой вершиной, не превышает 1. Дробное сопоставление Икс-совершенно, если сумма весов, смежных с каждой вершиной, равна 1. Следующие утверждения эквивалентны для двудольного графа грамм = (X + Y, E):^[10]

• грамм допускает X-совершенное соответствие.
• грамм допускает X-совершенное дробное соответствие. Вывод очевиден, поскольку Икс-совершенное соответствие - частный случай Икс-совершенное дробное сопоставление, в котором каждый вес равен либо 1 (если край находится в сопоставлении), либо 0 (если это не так).
• грамм удовлетворяет условиям брака Холла. Значение имеет место, потому что для каждого подмножества W из Икс, сумма весов около вершин W есть |W|, поэтому смежные с ними ребра обязательно примыкают не менее чем к | W | вершины Y.

Количественный вариант

Когда условие Холла не выполняется, исходная теорема говорит нам только о том, что идеального совпадения не существует, но не сообщает нам наибольшее совпадение, которое существует. Чтобы узнать эту информацию, нам понадобится понятие недостаток графика. Учитывая двудольный граф грамм = (X + Y, E), дефицит G w.r.t. Икс является максимумом по всем подмножествам W из Икс, из разницы | W| - | N_грамм(W) |, Чем больше недостаток, тем дальше график не удовлетворяет условию Холла.

Используя теорему Холла о браке, можно доказать, что если дефект двудольного графа грамм является d, тогда грамм допускает соответствие размера не менее |Икс| -d. Видеть Дефицит (теория графов) для доказательства.

Обобщения

• Обобщение теоремы Холла на общие графы (которые не обязательно являются двудольными) обеспечивается Теорема Тутте.
• Обобщение теоремы Холла на двудольные гиперграфы обеспечивается различными Теоремы холловского типа для гиперграфов.

Примечания

1. Холл мл. 1986, стр. 51. Также возможно иметь бесконечное множество наборов в семье, но количество наборов в семье должно быть конечным, считая с кратностью. Только ситуация с бесконечным числом наборов при разрешении бесконечного набора недопустима.
2. Хакселл, П. (2011). «Об образовании комитетов». Американский математический ежемесячник. 118 (9): 777–788. Дои:10.4169 / amer.math.monthly.118.09.777. ISSN  0002-9890.
3. Название этой теоремы противоречиво в литературе. Есть результат, касающийся паросочетаний в двудольных графах и его интерпретации как покрытия (0,1) -матриц. Холл-младший (1986) и ван Линт и Уилсон (1992) называют матричную форму теоремой Кёнига, а Робертс и Тесман (2009) назовем эту версию теоремой Кёнига-Эгервари. Версия с двудольным графом называется теоремой Кёнига по формуле Кэмерон (1994) и Робертс и Тесман (2009).
4. Эквивалентность семи основных теорем комбинаторики
5. Райхмайдер 1984
6. Холл мл. 1986, стр. 51
7. Кэмерон 1994, стр.90
8. Холл мл. 1986, стр. 51
9. Ахарони, Рон (февраль 1984). "Теорема двойственности Кенига для бесконечных двудольных графов". Журнал Лондонского математического общества. s2-29 (1): 1–12. Дои:10.1112 / jlms / s2-29.1.1. ISSN  0024-6107.
10. «co.combinatorics - версия теоремы Холла о браке с дробным соответствием». MathOverflow. Получено 2020-06-29.

Рекомендации

• Бруальди, Ричард А. (2010), Вводная комбинаторика, Верхняя Седл-Ривер, Нью-Джерси: Прентис-Холл / Пирсон, ISBN  978-0-13-602040-0
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы, Кембридж: Издательство Кембриджского университета, ISBN  978-0-521-45761-3
• Дунчен, Цзян; Нипков, Тобиас (2010), "Теорема Холла о браке", Архив формальных доказательств, ISSN  2150-914X. Проверено компьютером.
• Холл-младший, Маршалл (1986), Комбинаторная теория (2-е изд.), Нью-Йорк: John Wiley & Sons, ISBN  978-0-471-09138-7
• Холл, Филипп (1935), «О представителях подмножеств», J. London Math. Soc., 10 (1): 26–30, Дои:10.1112 / jlms / s1-10.37.26
• Халмос, Пол Р.; Воан, Герберт Э. (1950), «Проблема брака», Американский журнал математики, 72 (1): 214–215, Дои:10.2307/2372148, JSTOR  2372148, МИСТЕР  0033330
• Райхмайдер, П.Ф. (1984), Эквивалентность некоторых комбинаторных теорем о согласовании, Полигональное Издательство, ISBN  978-0-936428-09-3
• Робертс, Фред С .; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), Бока-Ратон: CRC Press, ISBN  978-1-4200-9982-9
• van Lint, J. H .; Уилсон, Р. (1992), Курс комбинаторики, Кембридж: Издательство Кембриджского университета, ISBN  978-0-521-42260-4

внешняя ссылка

• Теорема о браке в завязать узел
• Теорема и алгоритм брака в завязать узел
• Теорема Холла о браке объясняется интуитивно в заметках Лаки.

Эта статья включает в себя материал из доказательства теоремы Холла о браке на PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.