Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 126
Текст из файла (страница 126)
Причину обьясним позже. Заметим, т.к. поток в каждую вершину а, не может превысить 1, поток через каждое ребро Ьз из а, в Ь должен быть 1 или 0 независимо от пропускной способности с(й, ). Для ребра !с, из а; в Ь определим поток ~(!сз ) равным 1, если имеется паросочетаюшее ребро между а, и Ь, и равным 0 в противном случае.
Величина потока, иа!!!), в таком случае равна количеству ребер в паросочетании между А и В. Максимальный поток имеет место, когда имеется максимальное паросочетание. Таким образом, задача нахождения максимального паросочетания сведена к задаче построения максимального потока. Воспользуемся алгоритмом нахождения максимального потока, описанным в предыдущем разделе. Начнем с ребра е,, ведушего в вершину а,, которое не РАЗМЕЛ 1Б.2. Паросочетание 709 является паросочетающим, в противном случае Дег) = с(ег) = 1.
Затем движемся по ориентированному ребру 1гг к вершине Ь, множества В. Если вершина Ь, не паросочетается, создаем паросочетающее ребро между сч и Ь, увеличивая поток. Если вершина 6, паросочетается, нужно вернуться по неправильно ориентированому ребру. Поэтому его поток должен быть равен 1, и мы продолжаем цепь назад во множество А по паросочетающему ребру. Снова, возвращаясь в В, выбираем ребро, которое не является паросочетающим.
Продолжаем цепь, пока не достигнем вершины во множестве В, которая не паросочетается. В цепи необходимо добавить 1 к потоку правильно ориентированных ребер из А в В и вычесть 1 из потоков неправильно ориентированных ребер из В в А. В результате паросочетающими ребрами станут те, которые ими не были, а прежние паросочетающие ребра будут удалены. Это добавит одно паросочетающее ребро двудольному графу, и мощность паросочетания увеличится на 1. Таким образом, алгоритм нахождения максимального потока позволяет найти максимальное паросочетание. Начать можно с пустого паросочетания, как того требует алгоритм нахождения максимального потока.
В этом случае используем алгоритм построения паросочетающих ребер, а затем увеличим их число, чтобы найти максимальное паросочетание. В следующих примерах мы предполагаем, что изначально имеется некоторое паросочетание, которое будем увеличивать до максимального. Мы видим, что при использовании этого метода нет необходимости заботиться о вершинах а и з. Мы просто начинаем с вершины из множества А, которая не паросочетается, и продолжаем движение назад и вперед, пока оно не закончится в вершине множества В, у которой нет паросочетающего ребра.
ПРИМЕР 16.20. Для графа, изображенного на рис. 16.32, найти максимальное паросочетание. а( Ьг аг аз Ь Рис, !б.32 Начинаем в вершине аю поскольку она не имеет паросочетающего ребра. По ориентированному ребру попадаем в вершину Ьа, т.к. ребро (аг,Ьз) не принадлежит начальному паросочетанию. Продолжаем цепь назад в аз, поскольку ребро (аз, 64) принадлежит текущему паросочетанию.
Из аз цепь продолжаем в Ьы поскольку (аз,бг) — не паросочетающее ребро. Из Ьг цепь продолжаем в аз, поскольку (аз,Ь!) — паросочетающее ребро. Из аз цепь продолжаем в вершину Ьз, т.к. (аз, Ьз) не принадлежит паросочетанию. Из Ьз цепь продолжаем назад в аы поскольку (аг,бз) — паросочетающее ребро. Из аг цепь продолжаем в Ьз, поскольку (ам ба) не принадлежит паросочетанию. Из Ьз не выходит ни одно паросочетающее ребро, поэтому цепь построена и имеет вид: а„- 64 — аз — Ьг — аз — Ьз — а, — Ьз.
После этого удаляем из исходного 710 ГЛг»ВА 16. Сети паросочетания ребра, имеюшиеся в цепи, и добавляем ребра из цепи, которые в нем отсутствуют. Получаем граф, изображенный на рис. 16.33. а, еЬ, а2 ° Ьз аз еЬ, а4 4 Рис. /б.33 Построенное паросочетание является максимальным и, к тому же, полным паросочетанием, потому что количество ребер в паросочетании равно количеству вершин в А. П ПРИМЕР 16.21. Для графа, изображенного на рис. 16.34, найти максимальное паросочетание. а» а, а а2 Е Ь2 аз 5 аз з Ь4 а4 а ° Ь а5 ° ь5 Рис. !б.34 Рис.
!б.3б Начинаем в вершине аз, поскольку у нее нет просочетаюшего ребра. По ориентированному ребру попадаем в вершину 65, т.к. (аз, 65) — не паросочетаюшее ребро. Затем продолжаем цепь назад в аз, потому что (аз, Ьз) — паросочетаюшее ребро. Из аз продолжаем цепь в Ь4, поскольку (аз, Ь4) — не паросочетаюшее ребро. Далее продолжаем цепь назад в аг, т.к, (амЬ4) — паросочетаюшее ребро. Из а, продолжаем цепь в Ьз, потому что (амЬз) — не паросочетаюшее ребро. После этого возвращаем цепь в аз, поскольку (аз,ьз) — паросочетаюшее ребро.
Из аз продолжаем цепь в 62, (аз, Ьз) — не паросочетаюшее ребро. Из 62 не выходит ни одно паросочетаюшее ребро, поэтому цепь построена и имеет вид: »25 «65' из «64' и1 +Ьз» из «62 ° Удаляем из исходного паросочетания ребра, имеюшиеся в цепи, и добавляем ребра из цепи, которые в нем отсутствуют. Получаем граф, изображенный на рис. 16.35. Поскольку количество ребер в паросочетании равно количеству вершин в А, имеем максимальное паросочетание, которое является полным.
П РАЗДЕЛ 1б.2. Паросочетание 711 ОПРЕДЕЛЕНИЕ 16.22.Для подмножества Х множества А введем множество В(Х) = (Ь: Ь Е В и Ь смежная с вершиной из Х). В(Х) называется множеством значений Х. Это определение согласовано с определением множества значений, которое представлено в главе 2 при изучении отношений. Теперь можно сформулировать необходимые и достаточные условия полноты паросочетания. ТЕОРЕМА 16.23. (Теорема Холла) Двудольный граф С(Е, и'), в котором )г = А О В, имеет полное паросочетание тогда и только тогда, когда для каждого подмножества Х С А выполняется )Х) < (В(Х) ~.
ДОКАЗАТЕЛЬСТВО. Очевидно, что если граф С(Е, Ъ') — полный, тогда необходимо (Х! < ~В(Х)! для каждого подмножества Х множества А, т.к. в противном случае не для всех элементов из Х и, следовательно, не для всех элементов из А существует паросочетаюшее ребро. В частности, каждый элемент из А смежен с элементом из В и )А) < )В). Обратно, предположим, что )Х) < (В(Х)! для каждого подмножества Х множества А. Согласно теореме 16.16 существует разрез (Я,Т) такой, что оа1(1) = С(Я,Т). Известно, что оа1(У) равно количеству вершин в максимальном паросочетании, поэтому С(Я,Т) тоже равно количеству вершин в макисимальном паросочетании.
Пусть )А( = и. Тогда С(Я,Т) < и, поскольку количество элементов в максимальном паросочетании не может превысить количество вершин в А. Вспомним, что С(Я,Т) равно сумме пропускных способностей всех ребер между 5 и Т. Известно также, что этот разрез не может содержать ребро Ьу между вершиной а, из А и вершиной Ь, из В, т.к. с(/с, ) = и+ 1. Поэтому, если а, Е Я, то В((а)) С Я. Отсюда следует, что В(А П 5) С Я. Между каждой вершиной из В(А П 5) и г существует ребро. Кроме того, каждое из этих ребер принадлежит разрезу (Я,Т), поскольку г Е Т и вносит 1 в С(Я,Т).
Множество А — несвязное объединение множеств АП Я и А ПТ. Следовательно, и = )А! = )А П 5(+ ~АПТ). Между элементом а и каждым элементом множества А и Т существует ребро. Поскольку а е Я, каждое из этих ребер принадлежит разрезу (Я, Т) и вносит 1 в С(Я,Т). Поскольку по предположению (А П 5) < )В(А П 5)(, отсюда следует, что С(Я,Т) > (В(А О 5)(+ (Аг1 Т~ > )Ап 5(+ (А пТ~ = (А( = и. Вспомним, однако, что С(5, Т) равно количеству ребер в максимальном паросочетании. Поэтому С(Я,Т) < и, откуда следует, что С(Я,Т) = и, т.е. максимальное паросочетание является полным.
Теперь представим другой алгоритм нахождения максимального паросочетания. На этот раз используем матрицы. Начнем с модифицированной матрицы инцидентности. Поскольку имеются ребра только из А в В, то необходима та часть матрицы А, в которой строка соответствует элементу из А, а столбец соответствует элементу из В. Строки именуем вершинами из А, столбцы — вершинами из В. Как и раньше, помещаем 1 в г-ую строку ~-ого столбца, если существует ребро из а, в Ь . Начнем с расстановки скобок вокруг каждой 1 в г-ой строке и 1-ом столбце, если существует паросочетающее ребро из а, в Ь,.
Проиллюстрируем этот процесс для паросочетания из примера 16.20. Помешаем символ 4~ в 712 ГПАВА 1б. Сети конец строки, соответствующей а4, чтобы отметить, что в строке нет ]Ц и, следовательно, для а4 нет паросочетаюшего ребра. Считаем строку, содержащую такой символ в конце, помеченной. Точно так же считаем помеченным каждый столбец, содержащий в конце указанный символ.
На этом этапе матрица имеет следующий вид; Поскольку строка, содержащая а4, помечена, то везде, где имеется 1 без скобок, помешаем а4 под каждым столбцом, содержащим 1. Числа внизу и справа помогут найти обратный путь. Переход по 1 в столбце Ь4 равносилен переходу из а4 в 64 по непаросочетаюшему ребру. В столбце, соответствуюшем Ь4, выберем строку, содержащую [Ц, которая встречается в аз, и поместим 64 в правый столбец этой строки, что эквивалентно построению паросочетаюшего ребра из 64 в аз. На этом этапе имеем следующую матрицу: Теперь ишем вхождение единиц в строке аа и помешаем аз внизу каждого столбца.
В данном случае единицы имеются в столбцах 6| и Ьз. Имеем, таким образом, две возможности для непаросочетаюшего ребра. В столбцах, соответствуюших Ь, и Ьз, находим строки, содержашие ]Ц. Ими являются строки, соответствуюшие аз н аы Помещаем 6| в правый столбец строки аз и Ьз — в правый столбец строки аы Получаем матрицу вида В строке аг отыскиваем 1 в одном из столбцов. Таким столбцом является Ьз. Под ним помещаем аы В строке аз отыскиваем 1 в столбцах. Ими являются столбцы 6з и Ь4, но они уже помечены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
