4.5: Відповідність у двосторонніх графіках

Last updated
Save as PDF

Page ID: 64466

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Template:MathJaxLevin

Досліджуйте!

Враховуючи двочастковий граф, відповідність є підмножиною ребер, для якої кожна вершина належить рівно одному з ребер. Наша мета в цій діяльності полягає в тому, щоб виявити певний критерій того, коли двосторонній граф має відповідність.

Чи містить графік нижче відповідність? Якщо так, знайдіть його.

$image-145.svg$

Не всі двосторонні графіки мають збіги. Намалюйте якомога більше принципово різних прикладів двосторонніх графіків, які НЕ мають збігів. Ваша мета полягає в тому, щоб знайти всі можливі перешкоди на графіку, що має ідеальне відповідність. Запишіть необхідні умови, щоб граф мав відповідність (тобто заповніть порожній: Якщо граф має відповідність, то). Тоді запитайте себе, чи достатньо цих умов (чи правда, що якщо, то графік має відповідність?).

Ми завершуємо ще одним прикладом задачі теорії графів, яка ілюструє різноманітність і простори предмета.

Припустимо, у вас є двосторонній граф$G\text{.}$ Це буде складатися з двох множин вершин$A$ і$B$ з деякими ребрами, що з'єднують деякі вершини з деякими вершинами в$B$ (але, звичайно, немає ребер між двома вершинами як в,$A$ так і в обох$B$).$A$ Відповідність$A$ - це підмножина ребер, для якої кожна вершина$A$ належить рівно одному краю підмножини, і жодна вершина не$B$ належить більш ніж одному ребру в підмножині. На практиці ми будемо вважати, що$|A| = |B|$ (два множини мають однакову кількість вершин), тому це говорить про те, що кожна вершина у графі належить рівно одному ребру у відповідності. ⁵ Примітка: те, що ми називаємо відповідністю, іноді називають ідеальним відповідністю або повним відповідністю. Це тому, що в ньому цікаво дивитися і на неідеальні відповідності. Ми назвемо ці часткові збіги.

Деякий контекст може полегшити це розуміння. Подумайте про вершини в$A$ як представляють учнів у класі, а вершини в$B$ як представляють теми презентації. Ми ставимо ребро від вершини$a \in A$ до вершини,$b \in B$ якщо студент$a$ хотів би представити на тему$b\text{.}$ Звичайно, деякі студенти хотіли б представити на більш ніж одну тему, тому їх вершина буде мати ступінь більше 1. Як викладач, ви хочете призначити кожному учню свою унікальну тему. Таким чином, ви хочете знайти відповідність$A\text{:}$ ви вибираєте деяку підмножину країв так, щоб кожен студент збігався з точно однією темою, і жодна тема не збігається з двома студентами. ⁶ Стандартним прикладом для збігів раніше була проблема шлюбу, в якій$A$ consisted of the men in the town, $B$ the women, and an edge represented a marriage that was agreeable to both parties. A matching then represented a way for the town elders to marry off everyone in the town, no polygamy allowed. We have chosen a more progressive context for the sake of political correctness.

Питання: коли двосторонній граф містить відповідність$A\text{?}$ Щоб почати відповідати на це питання, подумайте, що може перешкодити графу містити відповідність. Це не обов'язково скаже нам умову, коли графік має відповідність, але принаймні це початок.

Один із способів не$G$ може мати відповідність, якщо є вершина в$A$ не сусідній з будь-якою вершиною в$B$ (так що має ступінь 0). Що ще? Що робити, якщо двом студентам обом подобається одна і та ж одна тема, а іншим немає? Потім після присвоєння цієї теми першому студенту нічого не залишається для другого студента, щоб сподобатися, так що це дуже багато, ніби другий студент має ступінь 0. Або що робити, якщо трьом студентам подобаються лише дві теми між ними. Знову ж таки, після присвоєння одному студенту тему, ми зменшуємо це до попереднього випадку двох студентів, які люблять лише одну тему. Ми можемо продовжувати цей шлях з дедалі більшою кількістю студентів.

На цьому етапі повинно бути зрозуміло, що якщо є кожна група$n$ студентів, які як група люблять$n-1$ або менше тем, то відповідність неможлива. Це справедливо для будь-якої цінності$n\text{,}$ і будь-якої групи$n$ учнів.

Щоб зробити це більш теоретичним графами, скажімо, у вас є$S \subseteq A$ набір вершин. Визначити,$N(S)$ щоб бути множиною всіх сусідів вершин в$S\text{.}$ Тобто,$N(S)$ містить всі вершини (в$B$) які примикають принаймні до однієї з вершин в$S\text{.}$ (У студенті/теми граф,$N(S)$ це набір тем, які сподобалися студентам $S\text{.}$) Наше обговорення вище можна узагальнити наступним чином:

Відповідна умова

Якщо двосторонній граф$G = \{A, B\}$ має відповідність$A\text{,}$ тоді

\ почати {рівняння*} |N (S) |\ ge |S|\ кінець {рівняння*}

для всіх$S \subseteq A\text{.}$

Чи вірно зворотне? Припустимо,$G$ задовольняє умову відповідності$|N(S)| \ge |S|$ для всіх$S \subseteq A$ (кожна множина вершин має принаймні стільки сусідів, ніж вершин у множині). Чи означає це, що існує відповідність? Дивно, так. Очевидного необхідної умови також достатньо. ⁷ Це часто трапляється в теорії графів. Якщо вам вдасться уникнути явних зустрічнихприкладів, то часто отримуєте бажане. Це теорема, вперше доведена Філіпом Холом в 1935 році. ⁸ Існує також нескінченна версія теореми, яка була доведена маршалом Холл-молодшим. Назва є збігом обставин, хоча, оскільки два зали не пов'язані між собою.

Теорема 4.5.1 Теорема Холла про шлюб

$G$Дозволяти бути двосторонній граф з$A$ множинами, а$B\text{.}$ потім$G$ має відповідність$A$ якщо і тільки якщо

\ почати {рівняння*} |N (S) |\ ge |S|\ кінець {рівняння*}

для всіх$S \subseteq A\text{.}$

Існує досить багато різних доказів цієї теореми - швидкий пошук в Інтернеті допоможе вам почати роботу.

Окрім застосування до тем презентації шлюбу та студентських презентацій, матчі мають програми повсюдно. Завершимо одним з таких прикладів.

Приклад$\PageIndex{1}$

Припустимо, ви роздаєте 52 звичайних гральних карт на 13 стопок по 4 карти кожна. Доведіть, що ви завжди можете вибрати одну карту з кожної купи, щоб отримати один з кожного з 13 значень карт туз, 2, 3,..., 10, валет, дама, і король.

Рішення

Зробити це безпосередньо було б важко, але ми можемо використовувати відповідну умову, щоб допомогти. Побудувати граф$G$ with 13 vertices in the set $A\text{,}$ each representing one of the 13 card values, and 13 vertices in the set $B\text{,}$ each representing one of the 13 piles. Draw an edge between a vertex $a \in A$ to a vertex $b \in B$ if a card with value $a$ is in the pile $b\text{.}$ Notice that we are just looking for a matching of $A\text{;}$ each value needs to be found in the piles exactly once.

У нас буде відповідність, якщо відповідна умова тримає. З огляду на будь-який набір значень карти (набір$S \subseteq A$) we must show that $|N(S)| \ge |S|\text{.}$ That is, the number of piles that contain those values is at least the number of different values. But what if it wasn't? Say $|S| = k\text{.}$ If $|N(S)| < k\text{,}$ then we would have fewer than $4k$ different cards in those piles (since each pile contains 4 cards). But there are $4k$ cards with the $k$ different values, so at least one of these cards must be in another pile, a contradiction. Thus the matching condition holds, so there is a matching, as required.