Паросочетания

Опр1: подмнож. М мн-ва Е наз. паросочетанием, если никакие 2 ребра из М не имеют общей вершины, т.е. никакие 2 вершины не явл. инцинд., если ребро в паросочетании, то наз. паросочетанным, само ребро паросочетающим. Опр2: паросочетание М на двудольном графе наз. max. если никакое другое паросочетание на не сод. больше ребер чем М. Опр3: Паросочетание М на двудольном , где , наз. полным, если . Опр4: Для подмнож. мн-ва , рассм. мн-во , - мн-во значений . Теорема Менгера: Наименьшее число вершин, разделяющих две несмежные вершины s и t, равно наибольшему числу непересекающихся простых (s − t) цепей. Теорема Холла: если в двудольном графе любые k элементов одной из долей связаны по крайней мере с k элементами другой, то граф разбивается на пары. Док-во: Пусть мощность первой доли — n. Сделаем из данного графа сеть. Для этого на каждом ребре введем пропускную способность по 1 в направлении от вершины первой доли к вершине второй. При этом создадим две дополнительные вершины — s и t, от первой проведем все стрелки в вершины первой доли, а из каждой вершины второй проведем стрелки во вторую добавленную вершину. Заметим, что получившаяся сеть — целочисленная, то есть в ней существует максимальный целочисленный поток, и что если мы сможем доказать, что пропускная способность минимального разреза равна , то по теореме Форда-Фалкерсона (величина максимального потока равна величине минимального разреза) величина максимального потока равна пропускной способности минимального разреза, то есть тоже равна . Очевидно, что если в бинарной транспортной сети величина максимального потока равна , то существует непересекающихся по вершинам путей из истока в сток. Это следует из алгоритма для нахождения максимального целочисленного потока в целочисленном графе, а из каждого такого пути можно выбрать смежную пару вершин из разных долей исходного графа.

То, что мощность минимального разреза не превышает , очевидно — достаточно рассмотреть разрез, в котором множество S содержит одну вершину .

Теперь рассмотрим произвольный разрез (S,T). Пусть в S попали ровно вершин из первой доли и из второй. Тогда если , то есть , то пропускная способность разреза, уже хотя бы , из-за ребер, ведущих из S в и ребер, ведущих из в T. Иначе, если , то из условия, что любые вершины первой доли связаны хотя бы с вершинами второй, следует, что эти также связаны с вершинами второй доли, а так как , то они связаны хотя бы с вершинами во второй доле, попавшими во множество T. Тогда пропускная способность разреза не меньше , то есть снова не меньше . Теорема доказана. Алгоритм поиска max паросочетания: Найдём строку, в которой нет поставим # и отметим эту 1 в последней строке , двигаемся вверх по отмеч. столбцу до , пишем в строке. На столбца сод. 1 без в строке отметим в столбцах . Теперь ищем строки сод. указываем столбцы. В строке ищем 1 без записываем . . Проходя по этим маршрутам заменим . Новые сочетания . Венгерский алгоритм: Задача: Имеется m заданий и столько же исполнителей. Каждый исполнитель способен выполнить каждое задание, но за каждое задание он возьмет с Вас определенную сумму денег. Вы торопитесь, поэтому хотите назначить каждому исполнителю по задаче (разные исполнители получают разные задачи), и заставить их всех работать одновременно. Ваша задача - сделать это так, чтобы минимизировать затраты.

Идея алгоритма: Начиная с этого момента будем предполагать, что значения всех элементов матрицы w[i][j] неотрицательны. Задача легко сводится к этому случаю, если ко всем элементам матрицы прибавить достаточно большое положительное число. Для матрицы w с неотрицательными элементами справедливо следующее очевидное утверждение:

Искомый минимальный вес z независимого набора равен нулю тогда и только тогда, когда в матрице существует полный независимый набор, состоящий из нулевых элементов.

Идея алгоритма состоит в том, чтобы при помощи некоторых операций модифицировать матрицу w так. чтобы в ней появился такой независимый набор из нулей. При этом операции, производимые над матрицей, будут сводить задачу к эквивалентной, то есть модификации матрицы будут сохранять свойство минимальности веса для каждого полного независимого набора. Эти операции состоят в следующем: 1)Модификация строки. Операция состоит в добавлении заданного числа a ко всем элементам одной строки матрицы w. 2)Модификация столбца (аналогично).