Доведення. 1. Необхідність. Покажемо спочатку, що умова

1. Необхідність. Покажемо спочатку, що умова

(11.1)

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

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

6. Число називають дефіцитом графа .

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

8. Крок 1. Побудувати довільне повне паросполучення .

Крок 2. Якщо відображає всю множину в , то воно максимально, алгоритм кінчений. Якщо ні, то перейти до кроку 3.

Крок 3. Знайти в графі із установленим у ньому паросполученням довільний ланцюг, що чергується, . Якщо такого ланцюга немає, то максимально, алгоритм закінчено. Якщо такий ланцюг є, то побудувати паросполучення - паросполучення містить всі жирні дуги паросочетания , що не входять у ланцюг і всі тонкі дуги ланцюга (див мал. 11.3 й 11.4). Перейти до кроку 2, поклавши .

9. Вершину графа назвемо насиченої, якщо вона інцидентна жирній дузі, у противному випадку - ненасиченої.

10. Паросполучення назвемо повним, якщо кожна тонка дуга інцидентна хоча б одній насиченій вершині.

11. Теорема 6. Наступні 4 умови еквівалентні:

1) у простому графі паросполучення максимальне;

2) у простому графі не існує ланцюгів, що чергуються;

3) у графі не існує шляху, що йде із вершин множини в вершину

множини ;

4) у графі кожну вершину можна позначити знаком «+» або «-» так, щоб всі вершини множини одержали знак «+», а всі вершини множини - знак «-» і щоб ніяка дуга не йшла з «+» в «-».

12. Множина вершин простого графа тоді й тільки тоді є його опорою, коли множина внутрішньо стійка.

Для числа внутрішньої стійкості з Т. 7 слідує

.

13. Для побудови найбільшої внутрішньо стійкої множини простого графа в силу Т.7 можна скористатися одним з наведених алгоритмів побудови найбільшого паросполучення в графі .

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