Теория графов и комбинаторика

" Я •ce'f J / Г Е Ш ИЕ«- У -NET. И. — — V 6) Рйо.8.2 Пользуясь теоремой Кеяига, легко проверить, что граф, иао- йражвшшй на р;5с.8.1,а, является двудольным. Приведенное дока- ня гильство достаточности теореш Кенига являетоя конструктивным и дает iiBiOR лоотроения долей, если граф ^ двудольный. Из теореми Кенига, в частности, следует, что двудольный граф ие может содержать треугольников. ^8.2. Язпосочетйния я двудолытах гпагТах. Теореиз Хо. т.та fij-CTi. G =CVi,Vi.,X) _ двудольный граф, V \ € Vjt, и V] ом . Тогда взаимко-одисзначпое соотватствко «е» 1Гд, называегоя паросочетанкемэ л е м е н т о в . Еоли S с \/j-подмно­ жество первой додк, то вза15мко-одкозначяое осответстзиа S:S- »V^, такое, что ^1'"е Я V") яазываетог паросочач-Н'лвм из S Пуоть ^ S - т - паросочетагае из S в Тогда можно по­ ставить ему в соответствие иодглкоквстео X jCS) f V j J, у д лотпоргшщеа условиям: (SI и 2) (ЗCЛ^j•~ Отсвда следует, что парооочетание из S в Vg, мовщо опредедци, как множество/7сX попарно несмежных ребер, икцидент- ifflx нершпкам S число которых равно /S / . Ларосочетание кз Vj называетоя полным или совершенным п а - рооочвтанием в двудольной графе ^ ( ^1, *^2,; X ) . Н а рйо.8.3,а показан ярикор совершэнного паросочетания из V, B V^^ (жирше"ребра). Лда двудольного графа на рис.8.3,6 оовершанно^'о парооочетания и з V( в Vj, не оущеотвует. йсслвзден вопроо оущеотаования парооочетаняй. Введем мнсжеот- й-а M(V)= {ШЧ^с- М(3)=^^^М(ТГ), где Sc V , . '"}лк I S i > IM(S)I , то на сущеотвует парооочетания из S в М( S ) . а следовательно, и в V;j, . Дефицитом подмиожества SС Ц называетоя чиоло 61^3), равнее; 48