Теорема Холла о браке - Hall's marriage theorem
В математике , Теорема Холла , доказанная Philip Hall ( 1935 ), является теоремой с двумя эквивалентными формулировками:
- Комбинаторной формулировка имеет дело с набором конечных множеств . Это дает необходимое и достаточное условие для возможности выбора отдельного элемента из каждого набора.
- На графике теоретическая формулировки имеет дело с двудольным графом . Он дает необходимое и достаточное условие для поиска соответствия, которое покрывает хотя бы одну сторону графа.
Комбинаторная формулировка
Пусть будет (возможно , бесконечное) семейство конечных подмножеств из , где члены будут с учетом кратности (То есть, могут содержать один и тот же набор несколько раз).
Трансверсальна для этого изображения из инъективного функции от к таким образом, что является элементом множества для каждого в семье . Другими словами, выбирает одного представителя из каждой группы таким образом, чтобы никакие два из этих представителей не были равными. Альтернативный термин для трансверсальности - система различных представителей .
В коллекции S удовлетворяет условие брака , когда для каждого подсемейства ,
Другими словами, условие брака утверждает, что каждое подсемейство содержит, по крайней мере, столько различных членов, сколько наборов в подсемействе.
Если условие брак терпит неудачу , то не может быть трансверсально из .
Доказательство
|
---|
Предположим , что условие брак терпит неудачу, то есть, что для некоторых поднабор из , Пусть, от противного, что поперечная из тоже существует. Ограничение ошибочной подколлекции было бы инъективной функцией from into . Это невозможно по принципу Дирихле , так как . Следовательно, если условие брака не выполняется, трансверсали не может существовать. |
Теорема Холла утверждает, что верно и обратное:
Хола Брак теорема - семейство S конечных множеств имеет трансверсалъ тогда и только тогда , когда S удовлетворяет условие брака.
Примеры
Пример 1. Рассмотрим S = { A 1 , A 2 , A 3 } с
- A 1 = {1, 2, 3}
- A 2 = {1, 4, 5}
- A 3 = {3, 5}.
Допустимая трансверсаль будет (1, 4, 5). (Обратите внимание, что это не уникально: например, (2, 1, 3) работает одинаково хорошо.)
Пример 2: Рассмотрим S = { A 1 , A 2 , A 3 , A 4 } с
- A 1 = {2, 3, 4, 5}
- A 2 = {4, 5}
- A 3 = {5}
- A 4 = {4}.
Не существует допустимого трансверсального перехода; условие брака нарушается, как показывает подсемейство W = { A 2 , A 3 , A 4 }. Здесь количество наборов в подсемействе | W | = 3, в то время как объединение трех множеств 2 U 3 U 4 содержит только 2 элементы X .
Пример 3. Рассмотрим S = { A 1 , A 2 , A 3 , A 4 } с
- A 1 = { a , b , c }
- A 2 = { b , d }
- A 3 = { a , b , d }
- A 4 = { b , d }.
Единственные допустимые трансверсали - это ( c , b , a , d ) и ( c , d , a , b ).
Заявление о браке
Стандартный пример применения теоремы о браке - представить две группы; один из n мужчин и одна из n женщин. Для каждой женщины есть подмножество мужчин, за любого из которых она с радостью выйдет замуж; и любой мужчина был бы счастлив жениться на женщине, которая хочет жениться на нем. Подумайте, можно ли объединить (в браке ) мужчин и женщин, чтобы все были счастливы.
Если мы допустим, что A i будет набором мужчин, за которых i -я женщина была бы счастлива выйти замуж, тогда теорема о браке утверждает, что каждая женщина может счастливо выйти замуж за уникального мужчину тогда и только тогда, когда для любого подмножества женщин количество люди , которых по крайней мере одна из этих женщин была бы счастлива выйти замуж, , по крайней мере , столь же большой , как число женщин в этой подгруппе .
Это условие необходимо , так как если оно не выполняется, не хватает мужчин, чтобы разделить их между женщинами. Что интересно, это тоже достаточное условие.
Теоретико-графическая формулировка
Пусть G - конечный двудольный граф с двудольными множествами X и Y (т.е. G : = ( X + Y , E )). Х-идеальное соответствие (также называется: X-насыщающее соответствие ) представляет собой соответствие , которое покрывает каждую вершину в X .
Для подмножества W из X , пусть N G ( W ) обозначает окрестность из W в G , то есть множество всех вершин в Y смежных к некоторому элементу из W . Теорема о браке в этой формулировке утверждает, что существует X -совершенное соответствие тогда и только тогда, когда для каждого подмножества W из X :
Другими словами: каждое подмножество W из X имеет достаточно много смежных вершин в Y .
Доказательство теоретико-графовой версии
Легко направление : мы предполагаем , что некоторые сопоставления M насыщается каждая вершина X , и доказать , что условие Холла выполняется для всех W ⊆ X . Пусть M ( W ) обозначим множество всех вершин в Y совпавших по М к данному W . По определению соответствия, | M ( W ) | = | W |, Но М ( W ) ⊆ N G ( W ), так как все элементы M ( W ) являются соседями W . Итак, | N G ( W ) | ≥ | M ( W ) | а значит, | N G ( W ) | ≥ | W |,
Жесткое направление : мы предполагаем , что нет X Совершенного Совпадения и доказать , что условие Холла нарушается по крайней мере один W ⊆ X . Пусть М будет максимум соответствия, и пусть у вершина из X не насыщается М . Рассмотрим все чередующиеся пути (т. Е. Пути в G, попеременно использующие ребра снаружи и внутри M ), начинающиеся с u . Пусть множество всех точек в Y подключено к U этих чередующихся путями быть Z , а также множество всех точек в X соединено с U этих чередующихся путями ( в том числе и у самого) будет Вт . Никакой максимальный чередующийся путь не может заканчиваться вершиной в Y , иначе это будет дополняющий путь , так что мы могли бы увеличить M до строго большего соответствия, переключая статус (принадлежит M или нет) всех ребер пути. Таким образом, каждая вершина в Z сопоставляется M с вершиной в W \ { u }. И наоборот, каждая вершина v в W \ { u } сопоставляется посредством M с вершиной в Z (а именно, с вершиной, предшествующей v на альтернативном пути, заканчивающемся в v ). Таким образом, M обеспечивает биекцию W \ { u } и Z , что влечет | W | = | Z | + 1. С другой стороны, N G ( W ) ⊆ Z . Действительно, пусть v в N G ( Вт ) быть подключен к вершине ш в W . Если ребро ( w , v ) находится в M , то v предшествует w в любом альтернативном пути, идущем от u к w . Если ребро ( w , v ) не входит в M , то с его помощью можно продолжить любой альтернативный путь, идущий от u к w . В любом случае v посещается некоторым альтернативным путем, исходящим от u . Следовательно, N G ( W ) ⊆ Z и, значит, | N G ( W ) | ≤ | Z | = | W | - 1 <| W |,
Конструктивное доказательство твердого направления
Определим нарушитель Холла как подмножество W в X, для которого | N G ( W ) | <| W |, Если W является нарушителем зала, то нет соответствия , что насыщает все вершины W . Таким образом, существует также не соответствие, насыщающий X . Теорема Холла о браке гласит, что граф содержит X -совершенное соответствие тогда и только тогда, когда он не содержит нарушителей Холла. Следующий алгоритм доказывает жесткое направление теоремы: он находит либо X -совершенное паросочетание, либо нарушитель Холла. В качестве подпрограммы он использует алгоритм, который при условии соответствия M и несовпадающей вершины x 0 либо находит M- фрагментирующий путь, либо нарушитель Холла, содержащий x 0 .
Оно использует
- Инициализировать M : = {}. // Пустое соответствие.
- Утверждай: М является соответствие в G .
- Если M насыщает все вершины X, затем возвращает X соответствующий Совершенный M .
- Пусть x 0 - несовпадающая вершина (вершина в X \ V ( M )).
- Используя алгоритм нарушителя Холла , найдите либо нарушитель Холла, либо M- фрагментирующий путь.
- В первом случае верните нарушителя Холла .
- Во втором случае используйте M -элементный путь, чтобы увеличить размер M (на одно ребро), и вернитесь к шагу 2 .
На каждой итерации M увеличивается на одно ребро. Следовательно, этот алгоритм должен завершиться не позднее, чем через | E | итераций. Каждая итерация занимает не более | X | время. Общая сложность выполнения аналогична методу Форда-Фулкерсона для поиска соответствия максимальной мощности .
Эквивалентность комбинаторной формулировки и теоретико-графической формулировки
Пусть S = ( A 1 , A 2 , ..., A n ), где A i - конечные множества, которые не обязательно должны быть различными. Пусть множество X = { A 1 , A 2 , ..., A n } (то есть множество имен элементов S ) и множество Y является объединением всех элементов во всех A i .
Мы формируем конечный двудольный граф G : = ( X + Y , E ) с двудольными множествами X и Y , присоединяя любой элемент в Y к каждому A i, членом которого он является. Трансверсаль S представляет собой Х Улучшите соответствия (согласующий который охватывает каждую вершину в X ) из двудольного графа G . Таким образом, проблема комбинаторной формулировки может быть легко преобразована в задачу теоретико-графовой формулировки.
Топологическое доказательство
Теорема Холла может быть доказана (неконструктивно) на основе леммы Спернера .
Приложения
У теоремы есть много других интересных «внебрачных» приложений. Например, возьмите стандартную колоду карт и разложите ее на 13 стопок по 4 карты в каждой. Затем, используя теорему о браке, мы можем показать, что всегда можно выбрать ровно 1 карту из каждой стопки, так что 13 выбранных карт содержат ровно одну карту каждого ранга (Туз, 2, 3, ..., Дама, Король).
Более абстрактно, пусть G является группой , а Н конечная подгруппа из G . Тогда брак теорема может быть использован , чтобы показать , что существует множество T таких , что Т является трансверсально как для множества левых смежных классов и правых смежных классов группы H в G .
Брак теорема используется в обычных доказательствах того факта , что ( г × л ) латинский прямоугольник всегда может быть продолжено до (( г + 1) × п ) латинский прямоугольник при г < п , и так, в конечном счете , к латыни квадрат .
Логические эквивалентности
Эта теорема является частью набора замечательно мощных теорем комбинаторики, все из которых связаны друг с другом в неформальном смысле в том смысле, что доказать одну из этих теорем на основе другой из них проще, чем на основе первых принципов. Это включает:
- Теорема Кёнига – Эгервари (1931) ( Денес Кёниг , Ену Эгервари )
- Теорема Кенига
- Теорема Менгера (1927)
- Теорема о максимальном потоке и минимальном разрезе (алгоритм Форда – Фулкерсона)
- Теорема Биркгофа – фон Неймана (1946 г.)
- Теорема Дилворта .
В частности, есть простые доказательства импликаций теоремы Дилворта, теоремы Холла, теоремы Кенига – Эгервари, теоремы Кенига.
Бесконечные семьи
Вариант Маршалла Холла младшего
Исследуя Philip Hall оригинальное доказательство «s тщательно, Маршалл Холл-младший (не имеет никакого отношения к Philip Hall) был в состоянии настроить результат таким образом , что это разрешено доказательство к работе для бесконечного S . Этот вариант уточняет теорему о браке и дает нижнюю границу количества трансверсалей, которые может иметь данный S. Этот вариант:
Предположим, что ( A 1 , A 2 , ..., A n ), где A i - конечные множества, которые не обязательно должны быть различными, представляет собой семейство множеств, удовлетворяющих условию брака, и предположим, что | A i | ≥ r для i = 1, ..., n . Тогда количество различных трансверсалей для семейства не меньше r ! если r ≤ n и r ( r - 1) ... ( r - n + 1), если r > n .
Напомним, что трансверсаль для семейства S - это упорядоченная последовательность, поэтому две разные трансверсали могут иметь точно такие же элементы. Например, семейство A 1 = {1, 2, 3}, A 2 = {1, 2, 5} имеет как (1, 2), так и (2, 1) как разные трансверсали.
Условие брака не продлевается
Следующий пример, принадлежащий Маршаллу Холлу младшему, показывает, что условие брака не гарантирует существование трансверсали в бесконечной семье, в которой разрешены бесконечные множества.
Пусть S - семейство, A 0 = {1, 2, 3, ...}, A 1 = {1}, A 2 = {2}, ..., A i = { i }, ...
Условие брака выполняется для этой бесконечной семьи, но трансверсаль не может быть построена.
Более общая проблема выбора (не обязательно различные) элемент из каждого из совокупности непустых множеств (без ограничений в отношении числа наборов или размера наборов) допускается в общем случае только тогда , когда аксиома выбора является принято.
Теорема о браке распространяется на бесконечный случай, если ее правильно сформулировать. Принимая во внимание двудольный граф со сторонами A и B , мы говорим , что подмножество С из B меньше или равны по размеру подмножества D из A в графе , если существует инъекция в графе (а именно, с использованием только краев график) от C к D , и что он будет строго меньше в графе, если, кроме того, в графе нет инъекции в другом направлении. Обратите внимание, что пропуск в графе дает обычное понятие сравнения мощностей. Теорема о бесконечном браке утверждает, что существует инъекция из A в B в графе тогда и только тогда, когда нет такого подмножества C в A , что N ( C ) строго меньше, чем C в графе.
Вариант дробного соответствия
Дробно соответствия в графе является присвоением неотрицательных весов к каждому краю, таким образом, что сумма весов примыкают к каждой вершине не более 1. дробного соответствия является Й Улучшите , если сумма весов примыкают к каждой вершине ровно 1. Следующие утверждения эквивалентны для двудольного графа G = ( X + Y, E ):
- G допускает X-совершенное соответствие.
- G допускает X-совершенное дробное соответствие. Импликация следует непосредственно из того факта, что X- идеальное сопоставление является частным случаем X -совершенного дробного сопоставления, в котором каждый вес равен либо 1 (если ребро находится в сопоставлении), либо 0 (если это не так).
- G удовлетворяет условию брака Холла. Импликация верна, потому что для каждого подмножества W в X сумма весов около вершин W равна | W |, поэтому смежные с ними ребра обязательно смежны не менее чем с | W | вершины Y .
Количественный вариант
Когда условие Холла не выполняется, исходная теорема говорит нам только о том, что идеального совпадения не существует, но не говорит, какое совпадение является наибольшим из существующих. Чтобы узнать эту информацию, нам понадобится понятие дефектности графа . Учитывая двудольный граф G = ( X + Y , E ), то дефицит G WRT Х является максимальным, более всех подмножеств W из X , разности | W | - | N G ( W ) |. Чем больше дефект, тем дальше график не удовлетворяет условию Холла.
Используя теорему Холла о браке, можно доказать, что если дефект двудольного графа G равен d , то G допускает паросочетание размера не менее | Х | - d .
Обобщения
- Обобщение теоремы Холла на общие графы (которые не обязательно являются двудольными) обеспечивается теоремой Тутте .
- Обобщение теоремы Холла на двудольные гиперграфы обеспечивается различными теоремами типа Холла для гиперграфов .
Примечания
- Перейти ↑ Hall, Jr. 1986 , pg. 51. Также возможно иметь бесконечное множество наборов в семье, но количество наборов в семье должно быть конечным, считая с кратностью. Только ситуация с бесконечным количеством наборов при разрешении бесконечных наборов недопустима.
- ^ Haxell, P. (2011). «Об образовании комитетов» . Американский математический ежемесячник . 118 (9): 777–788. DOI : 10,4169 / amer.math.monthly.118.09.777 . ISSN 0002-9890 .
- ^ Обозначение этой теоремы противоречиво в литературе. Имеется результат о паросочетаниях в двудольных графах и его интерпретация как покрытие (0,1) -матриц. Холл-младший (1986) и ван Линт и Уилсон (1992) называют матричную форму теоремой Кёнига, а Робертс и Тесман (2009) называют эту версию теоремой Кёнига-Эгервари. Версия с двудольным графом называется теоремой Кенига Кэмероном (1994) и Робертсом и Тесманом (2009) .
- ^ Эквивалентность семи основных теорем комбинаторики
- ^ Reichmeider 1984
- Перейти ↑ Hall, Jr. 1986 , pg. 51
- ^ Cameron 1994 , pg.90
- Перейти ↑ Hall, Jr. 1986 , pg. 51
- ^ Aharoni, Рон (февраль 1984). "Теорема двойственности Кенига для бесконечных двудольных графов". Журнал Лондонского математического общества . s2-29 (1): 1–12. DOI : 10.1112 / jlms / s2-29.1.1 . ISSN 0024-6107 .
- ^ «co.combinatorics - версия теоремы Холла о браке с дробным соответствием» . MathOverflow . Проверено 29 июня 2020 .
использованная литература
- Бруальди, Ричард А. (2010), Введение в комбинаторику , Верхняя река Сэдл, Нью-Джерси: Прентис-Холл / Пирсон, ISBN 978-0-13-602040-0
- Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы , Кембридж: Cambridge University Press, ISBN 978-0-521-45761-3
- Дунчен, Цзян; Нипков, Тобиас (2010), «Теорема Холла о браке» , Архив формальных доказательств , ISSN 2150-914X . Проверено компьютером.CS1 maint: postscript ( ссылка )
- Холл-младший, Маршалл (1986), комбинаторная теория (2-е изд.), Нью-Йорк: John Wiley & Sons, ISBN 978-0-471-09138-7
- Холл, Филип (1935), «О представителях подмножеств», J. London Math. Soc. , 10 (1): 26-30, DOI : 10.1112 / jlms / s1-10.37.26
- Halmos, Paul R .; Vaughan, Герберт Е. (1950), "Проблема брака", Американский журнал математики , 72 (1): 214-215, DOI : 10,2307 / 2372148 , JSTOR 2372148 , МР 0033330
- Райхмайдер, П. Ф. (1984), Эквивалентность некоторых комбинаторных теорем о согласовании , Polygonal Publishing House, ISBN 978-0-936428-09-3
- Робертс, Фред С .; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), Бока-Ратон: CRC Press, ISBN 978-1-4200-9982-9
- ван Линт, JH; Уилсон, Р.М. (1992), Курс комбинаторики , Кембридж: Издательство Кембриджского университета, ISBN 978-0-521-42260-4
внешние ссылки
- Теорема о браке в разорванном узле
- Теорема и алгоритм брака при разрубании узла
- Теорема Холла о браке интуитивно объяснена в заметках Лаки.
Эта статья включает в себя материал из доказательства теоремы Холла о браке на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .