3. Системи різних представників

Нехай  скінчена множина;  скінчене сімейство його непустих (не обов'язково різних) підмножин. Порушимо питання: при яких умовах з кожної множини можна виділити по елементу  представникові множини так, щоб всі представники були попарно різні між собою. Таку систему різних представників часто називають трансверсаллю сімейства .

Визначення. Трансверсаль сімейства , де , називається частковою трансверсаллю сімейства .

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

Теорема 2. Нехай  непуста скінчена множина й сімейство непустих його підмножин, має трансверсаль (систему різних представників) тоді й тільки тоді, коли об'єднання будь-яких підмножин містить не менш елементів.

4. Дефіцит простого графа

Нехай  простий граф. На множині всіх підмножин визначимо функціонал .

Визначення. Число називають дефіцитом графа . Тому що , то завжди , при цьому тоді й тільки тоді, коли для всіх . Це дозволяє дати ще одне формулювання теореми Кенига  Холу.

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

Теорема 3. Якщо в простого графа дефіцит , то в будь-якому його паросполученні число дуг .

Доведення.

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

Позначимо через множину всіх таких підмножин , для яких . Для посилення теореми нам знадобляться наступні властивості функціонала й множини .

Твердження:

1.

.

2. Якщо , то й .

3. Нехай . Якщо , то й .

Доведення.

1. Властивість 1 одержимо, віднімаючи зі співвідношення

співвідношення

.

2. Якщо , то властивості 1.

Далі,

і , ,

отже,

і

3. Припустимо .

1) Тому що  скінчено (адже скінчено  скінчено), то по властивості 2 (перетинання кінцевого числа множин) ;

2) припустимо, , з іншого боку , прийшли до протиріччя, отже, .

Теорема 4. (Кенига  Оре). У простому графі найбільше число дуг паросполучення дорівнює .

Доведення. Якщо , то теорема зводиться до теореми Кенига  Холу. Допустимо, і розглянемо перетинання , перетинання тих множин , для яких . По властивості 3, . Якщо видалити із графа довільну вершину , то будуть зруйновані всі ті множини , для яких . Тому новий граф буде мати дефіцит . Покажемо, що . Для множини маємо , тобто . Але в силу справедливо , отже, . Звідси .

У силу нерівності маємо .

Видаляючи із множини графа вершин, одержимо граф , дефіцит якого дорівнює 0. Він допускає паросполучення , що відображає множину в множину , тобто . Відповідно паросполучення графа має те ж число дуг. Тому що, по теоремі 3 , то, і теорема 4 доведена.

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

Визначення. Опора, що містить найменше число вершин, називається найменшою.

Якщо  найменша опора і є елемент опори, то . Звідси слідує, що найменша опора представима у вигляді , де .

Теорема 5. (Кенига). У простому графі число вершин найменшої опори дорівнює числу дуг найбільшого паросполучення.

Доведення.

Дійсно,

.