Теорема холу про весіллях - студопедія

Можливе рішення задачі таке: (1,4), (2,1), (3,3), (4,2).

Розглянуту задачу можна представити графічно за допомогою двудольного графа. Для того, щоб точно сформулювати завдання про весіллях в термінах теорії графів, введемо таке поняття.

Паросочетание (або незалежним безліччю ребер) називається безліч ребер, в якому ніякі два не суміжні. Паросочетание називається максимальним, якщо ніяке його надмножество не є незалежним. Зроблене паросполучення з V1 у V2 в дводольному графі G (V1 ÇV2. Е) називається взаємно однозначне відповідність між вершинами з V1 і підмножиною вершин з V2. володіє тим властивістю, що вершини з'єднані ребром. - Еквівалентно: паросочетание, що покриває вершини V1.

Тепер завдання про весіллях можна сформулювати наступним чином: якщо G (V1 ÇV2. Е) - двочастковий граф, то за яких умов в G існує ідеальне паросочетание?

Використовуючи «матримоніальну» термінологію, можна сформулювати наступне необхідна умова для існування рішення в задачі про весіллях: будь-які k юнаків повинні бути знайомі (в сукупності) щонайменше з k дівчатами, де 1 £ k £ m. - Якщо умова не виконується, то неможливо одружити вже цих k юнаків, не кажучи вже про решту.

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

Теорема Холла про весіллях. Нехай А (| A | = m) - безліч юнаків і В (| B | = n) - безліч дівчат, причому кожен з юнаків знайомий з кількома дівчатами. Завдання про весіллях має рішення тоді і тільки тоді, коли будь-які k юнаків повинні бути знайомі (в сукупності) щонайменше з k дівчатами, де 1 £ k £ m.

Нехай - двочастковий граф. Зроблене паросполучення існує тоді і тільки тоді коли "AÍV1 | A | £ | Г (А) |.

Нехай S = 1. .... Sm> - сімейство підмножин кінцевого безлічі Е. Підмножини Sk не обов'язково різні і можуть перетинатися. Системою різних представників (або трансверсалями) називається підмножина C = 1. .... cm> з m елементів множини Е, таких що ck ÎSk. У яких випадках існує трансверсалями?

Зауваження. З - підмножина - отже, все ck різні.