Matchings construction procedure.pdf В [1, с. 165] приведены следующие достаточные условия существования в двудоль-ном графе G = (X, Y, E) полного паросочетания множества X с множеством Y:min dGx ^ max dGy. (1)жехНеобходимые и достаточные условия сформулированы в известной теореме Хол-ла [1, с. 164].Теорема 1. Для существования в двудольном графе G = (X, Y, E) полного паро-сочетания множества X с множеством Y достаточно выполнение условийV(x,y) Е E (dGx ^ dGy) ,которые в дальнейшем будем называть «условиями доминирования».Определение 1. Пусть граф G = (X, Y, E) удовлетворяет условиям доминиро-вания. Если после удаления из E некоторого паросочетания условия доминированиявыполняются, то данное удаление назовём сохраняющим.Определение 2. Разбиение множества рёбер E графа G = (X, Y, E) на после-довательность A, B, C , . . . из А паросочетаний называется непрерывным, если любоеребро, инцидентное вершине x Е X, включено в одно из первых dGx паросочетанийданной последовательности.Теорема 2. Пусть граф G1 = (X1,Y1,E1 ) удовлетворяет условиям доминирова-ния; Gj = (X1,Yj,Ei ) -граф, полученный удалением из графа Gi - 1 = (X1, Yi - 1 , E i - 1 )минимального паросочетания Mi - 1 , насыщающего все вершины наибольшей степенив Gi - 1 , i = 2 , . . . , А. Тогда1) каждое из этих удалений является сохраняющим;2) Мд = EA является полным паросочетанием множества X1 с множеством Y1в Gi;3) последовательность М д , . . . , М 1 представляет непрерывное разбиение множе-ства Ei на А паросочетаний.

Скачать электронную версию публикации