будет от вершин
будет от вершин из X к вершинам из Y;
• пропускная способность всех дуг C[i,j]=1.
Найдем максимальный поток из s в t для построенной сети. Он существует[11]. Насыщенные дуги потока (они выделены “жирными” линиями на рисунке соответствуют ребрам наибольшего паросочетания исходного графа.
Примечание. Найденное наибольшее паросочетание не единственное. Проверьте, это ли паросочетание получается при помощи алгоритма нахождения максимального потока. Найдите другие паросочетания.
Рассмотрим другой метод построения наибольшего паросочетания в двудольном графе. Введем понятие чередующейся цепи из X в Y относительно данного паросочетания M. Произвольное множество дуг P?E вида:
P={(x0,y1), (y1,x1), (x1,y2), ..., (yk,xk), (xk,yk+1)},
где k>0, все вершины различны, x0 - свободная вершина в X, yk+1 - свободная вершина в Y, и каждая вторая дуга принадлежит M, то есть
P?M={(y1,x1), (y2,x2), ..., (yk,xk)}.
Теорема[3]. Паросочетание M в двудольном графе G наибольшее тогда и только тогда,
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
