Доведення. Якби деяка паросполучення мала б дуг, то вона не відображала б у менш чим

Доведення.

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

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

Твердження:

1.

.

2. Якщо , то й .

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

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

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

.

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

Далі,

і , ,

отже,

і

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-11-09