теорема холу

Різні постановки задач про паросочетание

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

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

Всі елементи безлічі З різні, звідки і походить назва «система різних представника».

Приклади завдання СРП. В університеті працює безліч професорів, які люблять створювати комітети. Після того, як професора сформували безліч комітетів, вони вирішують утворити комітет комітетів (КК). КК складається з представників, які головують у звичайних комітетах. Діють такі правила:

а) від кожного комітету є в точності один представник в КК;

б) ніхто в КК не може бути представником більше одного комітету.

Питання полягає в наступному - чи можна в кожному комітеті обрати голову так, щоб ніякий професор ні головою більше одного комітету.

3. Досконале паросочетание паросочетание (або незалежним безліччю ребер) називається безліч ребер, в якому ніякі два ребра не суміжні.

Нехай G (V1. V2. Е) - двочастковий граф. Зроблене паросполучення з V1 у V2 називається паросочетание, що покриває вершини V1. В якому випадку існує зроблене паросполучення з V1 у V2?

Взагалі кажучи, завдання 1, 2 і 3 - це одна і та ж завдання. Дійсно, завдання 1 зводиться до задачі 3 наступним чином. V1 - безліч юнаків, V2 - безліч дівчат, ребра - знайомства юнаків з дівчатами. В такому випадку зроблене паросполучення - шуканий набір весіль. Завдання 2 зводиться до задачі 3 наступним чином. Покладемо V1. = S, V2. = Е, ребро (Sk, ei) існує, якщо. В такому випадку зроблене паросполучення - шукана трансверсалями. Таким чином, завдання 1. 2 і 3 мають загальний відповідь: в тому і тільки тому випадку, коли

що встановлюється наступною теоремою.

Нехай G (V. Е) - граф, A - підмножина вершин V, тобто , Тоді нехай позначимо через - безліч всіх вершин, суміжних з вершинами з A.

Теорема (Холла). Нехай G (V1. V2. Е) - двочастковий граф. Зроблене паросполучення з V1 у V2 існує тоді і тільки тоді, коли ().

Доведення. Нехай існує зроблене паросполучення з V1 у V2. Тоді в входить | А | вершин з V2. парних до вершин з множини А, і, можливо, ще щось. Таким чином, | А | .

Додамо в G дві нові вершини і та v. так що вершина і суміжно з усіма вершинами з V1. а вершина v суміжно з усіма вершинами з V2. Зроблене паросполучення з V1 у V2 існує тоді і тільки тоді, коли існують | V1 | вершинно-непересічних простих (і, v) -ланцюгів (рис. 37). Ясно, що | Р (u. V) | (Так як V1 розділяє вершини і та v).

По теоремі Менгера max | P (і, v) | = Min | R (і, v) | = | R |, де R - найменший мно-дружність, що розділяє вершини і та v. Маємо. Покажемо, що. Нехай,,. Тоді. Дійсно, якби, то існував би «обхідний» шлях (і, v1, v2, v) (див. Рис. 37) і S не було б розділяє безліччю для і і v. Маємо:. Отже,.

Мал. 37. До доведенню теореми Холла