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

б) Рис.8.3 ^ ^ C S ) - | S | - | M C S ) 1 . ( b . i ) ' Дефицит &'(б') графа cnpeflejiflaTO-i так: I^CG)- W I A X S ^ C S ) . (,,?.} SCV'I Из оярадолсний (8.1) и (В.2) оледует, ч'о О , т . к . ^ ( 0 ) = 0 . Если 6^ ( 6=) ^ О , то VScVi( J 5(4(M(S)|), Если <^(&) > О . п) Л S c \ / i 1 IS I > 1М CS) 1. • Очевидно, что при ^CG) > О не оущеотвуат совершаняого иа- рооочатания и з S i, V^^pflsi некоторого яод .„..ожеотБа S . Тоотзема 8 . 2 (Холл), Совершенное паросочатапив из Vi в в двудольном графа G = С V( ,V},,X ) существует тогда и только " о г - д а , когда V / l c V ' i ( | Д | ^ |М(А)/л т . е . когда ГС<?) ^ 0 . Наойходимоот', •' ) . Если f \/г, - соворюснноо паросочвгание, то V A c V t | Д ( - ( i ' ( A ) | . Ввиду того, что JCA) С МС/4) . т о 1 К Л ) | й ; 1М(Л)1 . Таким Образом, 1/\ I ^ ^ | М С А ) | . Доотаточнооть ( ) . Сущеотвоваж10 совершапного парооо- •19тания докажем индукцией по числу вершин в первой дола V i , 1 . Проверка. Если IVfis-f , то по условию теорош •с.ь. даш ед''чо 'Сйенной вершиш множества V( имеется хотя би одна смежная ей вершина Тогда соответстпие V] 1Г^ явля. о я совершенн/л паросочетанием из в . 2. Индуктивное предположение. Допустим, что достаточность справедлива для любого двудольного графа при 1 ( <w . 3 . Индзгктнвный шаг. Докажем доотаточпость для случая |\/((=W, Итак, имрем двудо; ный граф ^ - С X ) . в котором ) V , ( =м и V/A ' А ! 1М(А)| . Рассмотрим даа случая выпслнения условия т е о р вш. 49