В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 23
Текст из файла (страница 23)
Например, в графе, изображенном на рис. 29.2, множество из пяти ребер Н1, 9), (2, 8), (3, 7), (4, 5), (5, 6П является реберным покрытием, а поскольку 91(6) ) 4,5, то оно наименьшее. Паросочетание называется совершенным (или 1-фактором), если опо одновременно является реберным покрытием.
Иногда сам граф называют пароеочетаяием — тогда, когда все ребра графа составляют одно паросочетанне. Так, граф тКа является совершенным паросочетанием. В графе, изображенном на рис. 29.1, (е1, еа, ~ г з еа, ег) — совершенное паросочетание. Очевидно, что если в графе есть совершенное паросочетание, то оно является наименьшим ре- У Е 2 берным покрытием. Б Читатель помнит, что число Рис.
29.2 вершин в наибольшем независимом множестве и число вершин в наименыпем покрытии графа 6 порядка и связаны соотношением аа(С) + ра(6) = п. Аналогичное верно и для соответствующих реберных параметроз, т. е. справедлива следузощая Теорема 29.1 (Т. Галлаи, 1959 г.). Для любого графа С порядка и без изолированных вершин верно равенство а~ (6)+ р1(6) = и. с' Положим а~ = а|(6), 91= 91(6) и докажем два неравенства а1 + 91 < и, (1) а1+ 91~ и, (2) объединение которых и означает гарантируемое теоремой равенство. Пусть М вЂ” наиболыпее паросочетан~е в графе 6.
Рассмотрим подмножество У всех вершин этого графа, не покрываемых ребрами из М. Очевидно, что либо Ъ' — независимое множество веригин, либо ес=О, иначе паросочетание М не было бы наибольшим. Кроме того, ~ РЧ = =-п — 2ап При Р Ф 8 для каждой веригины вы 'е" выберем в графе 6 ребро, ей ннцидентное. Множество выбранных ребер обозначим через Е'. При Р' = 8 пололгпм Е = ю. Поскольку в графе С нет изолированных 123 вершин и множество Г независимо, то ~Е'~ = ) г') = = и — 2аь Очевидно, что множество Е' 0 М является реберпым покрытием, следовательно, ~~ ~!Е'0 М! = )Е'1+ )М! =(и — 2я~)+а~ = п — а~', неравенство (1) доказано.
Перейдем к доказательству неравенства (2). Пусть Р— наименьшее реберное покрытие графа С. Рассмотрим подграф С' = С (Р), порожденпьш .ребрами покрытии Р. Поскольку Р является наименьшим покрытием, то в графе С' всякое ребро пнцндентно вершине степени 1, т. е. каждая связная компонепта графа 6 является звездой. Пусть à — число этих звезд и я, — число ребер в 1-й компоненте, 1 = 1, й Выбрав в каждой компоненте по одному ребру, получим некоторое паросочетание Р' мощности й Следовательно, тассо Поскольку в графе С нет изолированных вершин, то с ю и Х (й + 1) Х )В + 8 ! Р! + г ) + Г( р + сс Неравенство (2) доказано. 0 5 30. Паросочетания в двудольном графе При изучении паросочетаннй основное внимание будет уделяться дзудольным графам. Для пояска паросочетаний в произвольном графе используются те же идеи, что и в случае двудольных, только реализация их усложняется.
Самые разные задачи связаны с построением паросочетаний в двудольных графах. Приведем только два примера. Первый пз пнх — задача о свадьбах, упоминавшаяся в з 22 в связи с теорией трапсверсалей. Существовавание решения этой задачи равносильно существованию в специально построенном двудольном графе (Х, У, Е) паросочетания, покрывазощего Х.
В этом графе вершины из Х соответствуют зовошам, из У вЂ” девушкам, а ребро соединяет вершины, соответствующие знакомым юноше п девушке. На рнс. 30.1 изображен граф для задачи о свадьбах, заданной таблицей 22.1. )Инрнымн линиями выделены ребра паросочетапия, решающего задачу. Второй пример — задача о назначениях. Имеется конечное множество исполнителей (гь хм ..., х,), каждый пз которых мозкег выполнять некоторые из ра- 124 бог (ун ум ..., у„).
Стоимость выполненияработу; исполнителем х1 равна юц. Нужно распределить исполнителей по работам, т. е. назначить по одному исполнителю на каждую работу, так, чтобы, во-первых, выполнить все работы и, во-вторых, минимизировать общие затраты. Как и в случае задачи о свадьбах, строится дзудольньш граф, каждому ребру которого приписывается вес, равньш стоимости выполнения исполнителем соответствующей работы.
Возможность выполнения всех работ равносильна существовашио в графе совершенного паросочетания, а назначение, минимизирующее все затраты, соответствует наибольшему паросочетанию с мн- зсо пнмальпым суммарным весом. Рассмотрим условия существовання паросочетаний. Для произ-,тг вольного подмножества А в )т6 Уг положим у Дго(А) = Дс(Л) = Ц )У(о)'чЛ. Назовем )тв (А) окружением под- 1'вс. ЗОА множества Л в графе С. Очевидно, что если длн графа 6 =(Х, У, Е) существует паросочетапие, покрывающее Х, то для любого подмножества А в Х число вершин, смежных с злемептами из А, не меньше, чем число вершин в А, т.
е. !)У(А) ! ~ !А!. Оказывается, что зто условие является и достаточным для существования такого паросочетания. Т е о р е м а 30.1. Для существования в двудольном графе С=(Х, У, Е) паросочвтания, покрывающего Х, необходимо и достаточно, чтобы любое подмногхество А мнолсгства Х удовлетворяло условию !А! (!М(А) !. Ппясе показано, что эта теорема является переформулярованной теоремой Холла о траясверсалях и потому не нуждается в дополнительном доказательстве. Однако для того, чтобы сделать эту главу независимой от предыдущей, приведем прямое доказательство теоремы о паросочетаннях. > Доказательство теоремы 30.1.
Необходимость утверждения теоремы очевидна. 125 Достаточность докажем индукцпей. Пусть С =(Х, У, Е) — двудольный граф с !Х! = т) О, удовлетворяющий условию теоремы. При т = 1 единственяая вершина из Х инцидентяа хотя бы одному ребру, которое и являетсл нужным паросочетанием. Пусть т ) 1 и теорема верна для графов, у которых !Х! ( т, Отдельно рассмотрим два возмохоных случая. 1. Для каждого собственного подмножества А в Х верно строгое неравенство !А! ( )Л',(А) !.
Выберем в С произвольное ребро ху. Коли С' = С вЂ” х — у, Х' = Х~х, У' = У~у, Е' =ЕЧ[хи, иу: и и У, а ~ Х), то (Х', У',Е')— дзудольлый граф, )Х'! = и — 1. Пусть А' — произвольное подмножество множества Х'. Так как !А'! ( ()го(А') !, а из У удалена только одла вершина, то )А'! -!Л"о (.4')!. По илдуктивному предположению в графе С существует паросочетание М, покрывающее Х'. Добавив к ЛХ ребро ху, получим нужное паросочеталие графа С. 2. В мяожестве Х существует такое собственное подмяожество Ао, что веряо равенство !Ао! = !)Уо(Ао) !.
(1) Пусть С п С" — подграфы графа С, порожденяые множествами вершил Ао 0 Л о(Ао) и УС~ (Ао 0 )гв (Ао) ) соответственно. Рассмотрим подграф С'. Для любого подмножества А Ао имеем Л'а(А) = Лго (А), н, следовательно, ! А ! ((! Л'о (А) !. По индуктивному предполоягепи1о в С существует паросочетание, покрывающее Ао. Обратимся к подграфу С". Для любого подмножества А — Х~Ао выполняются соотяошения ! 1о!+ !А! = ! 1о 0 А!<~!Лго(Ао О 1)! = = ! Л~а (Ао) ! + ! Л о" (А) ! и верно равенство (1). Следовательно, )А!~()Л"о (А)! и по индуктивному предпотожению в графе С' существует паросочеталие, покрывающее Х~Ао. Объединяя это паросочетание с построеняым выше, получим паросочетание в графе С, покрывающее Х.
<~ С л е д с т в и е 30.2. В тобом регулярном непуегам двудальнам графе существует совершенное пароеачетанпе. ~> Пусть С = (Х, У, Е) — регулярный двудольный граф, дев С = и ) О, А ы Х. Тогда число ребер, инцидентлых вершинам из А, равно и!А!. Степени концов этих ребер все равны т, поэтому !Л'(А) ! ) т!А !/т = !А!. 126 Согласно теореме 30.1 существует паросочетапие, покрывающее Х.
Поскольку для регулярного двудольного графа 6 = (Х, У, Е) всегда !Х! = ! У!, то в нем всякое паросочетание, покрывающее Х, является совершенным. < Следствие 30.3. Регулярный двудольный граф ненулевой степени является реберно непересекающимся объединением 1-факторов, з Пусть 6 — регулярный двудольпый граф степени пг > О. При пз 1 он является 1-фактором. Пусть зп > 1.
Согласно предыдущему следствию в С существует совершенное паросочетание М. 6 — М вЂ” регулярный двудольный граф степени 7п — 1. Проведя эту процедуру несколько раз, придем к объединению 1-факторов. < Заметим, что утверждение следствия 30.3 перестает быть верным, если пе требовать двудольпости графа.
В частности, граф Петерсена (рис. 1.7) был впервые введен в качестве примера кубического графа, не являющегося объединением 1-факторов. Следствие ЗОА. Пусть 6 =(Х, У, Е) — двудольный зраф, 1 — натуральное число, г ( !Х!. Для существования в графе С паросочетания мощности 1 необходимо и достаточно, чтобы любое подмнозкество А ез Х удовлетворяло условию !Хо(А)! ~~ (А!+1 — )Х!.
(2) > Построим новый двудольный граф 6' = (Х, У', Е'), добавив !Х! — г новых вершин к доле У и соединив ребром кангдую из них с каждой вершиной из Х. Очевидно, что существование в графе 6 паросочетания мощности г равносильно существованию в графе 6 паросочетання, покрывающего Х, для ~чего должно выполняться условие .4 (~ ! Л'о (А) !. Последнее равносильно условию (2), поскольку ! Л'о (А) ! = ! Л'о(А) ! + ! Х ! — й 7 Для полноты картины отметим без доказательства следующую теорему.
Теорема 30.5. В произвольном графе С совершенное паросочетание существует тогда и только тогда, когда для любого подмножества Я': — УС верно неравенство !Я! > ро(Я), где ро(Я) — число компонент нечетного порядка графа 6 — Я. Возвратимся к двудольпым графам. Пусть 6 = (Х, У, Е) — двудольный граф с непустыми долямп. Для любого подмнонгества А ш Х полотким )(А! — !7У(А)!, если А~ и, б( )=(О, если А = 8.
127 Величину 6„= 6, (Х, У, Е) = шах 6 (А) назовем дефиуитом графа 6 (Х, У, Е)'. Очевидно, что 0 < 6» ~ 1Х). Теорема 30.6. Для произволы»ого двудольного графа 6 =(Х, У, Е) с непустыми дол ми верно равенство с»,(6) = ~Х! — бе. с Перепишем неравенство (2) в виде 6(А) ~А! — ~1Ч(Л) ! ~ (Х~ — й (3) Согласно следствию 30.4 для существования паросочетания мощности » необходимо и достаточно, чтобы для каждого Л '= Х выполнялось условие (3). Прн г )Х! — 6» имеем 6(А) ( 1Х! — » 6», п, следовательно, неравенство (3) верно. Позтому граф С имеет паросочетаппе мощности ~Х! — 6». Если же ~ =!Х! — 6»+ 1, то неравенство (3) принимает вид 6(А)~ 1Х! — ~ бо — 1 и нарушается для тех подмножеств Лв, для которых 6 (Ао) бе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
