Теоретический материал
| Сайт: | Информатикс |
| Курс: | Алгоритмы на графах |
| Книга: | Теоретический материал |
| Напечатано:: | Гость |
| Дата: | Пятница, 18 Июль 2025, 21:35 |
Поиск максимального паросочетания в двудольном графе
Граф называют двудольным, если множество его вершин можно разбить на 2 непересекающихся множества (каждая вершина должна обязательно войти в одно из этих множеств), причем каждое ребро графа начинается в первом из этих множеств, а заканчивается в другом. Максимальное паросочетание — это максимально возможное количество ребер, не имеющих общих концов.
В основной программе каждой вершине одного из множеств мы пытаемся найти допустимую пару (очевидно, что если каждой вершине пара будет найдена, то максимальное паросочетание построено). Делается это с помощью функции dfs. Если для вершины j свободной пары в противоположном множестве нет, то делается попытка построить чередующуюся цепочку, начинающуюся с j-й вершины.
const max=…{размер большего из двух множеств}
var new: array[1..max] of boolean;{смысл противоположен названию!!!}
res: array[1..max] of integer;
n, m, i, j, cnt: integer;
function dfs(j: integer): boolean;
{пытается найти вершине j пару}
var i: integer;
begin
if new[j] then {j в текущем паросочетании уже просмотрена}
begin dfs:= false; exit end;
new[j]:= true;
for i:= 1 to n do
if a(i, j) {ребро между i и j существует} and
((res[i] = 0) {у i еще нет пары}
or{пару i можно пристроить к другой вершине} dfs(res[i])) then
begin
dfs:=true; res[i]:=j; exit
end;
dfs:=false
end;
begin {
…{здесь вводим описание графа}
fillchar(res,sizeof(res),0);
cnt:=0;{счетчик ребер в паросочетании}
for j:= 1 to m do
{каждой вершине одного из множеств пытаемся найти пару}
begin
fillchar(new,sizeof(new),false);
if dfs(j) then inc(cnt)
end;
writeln(cnt);
for i:= 1 to n do
if res[i] <> 0 then write(i,' ',res[i])
end.
Решение задачи о назначениях (Венгерский алгоритм)
В данной задаче требуется найти в двудольном графе полное паросочетание минимального веса. Не снижая общности мы можем считать, что такое паросочетание всегда существует (двудольный граф можно дополнить до полного ребрами с весом, превышающим сумму остальных весов ребер данного графа и при необходимости удалить подобные ребра из ответа).
Лемма 1. Если веса всех ребер графа, инцидентных какой-либо вершине, увеличить (уменьшить) на одно и то же число, то искомое паросочетание является искомым и в новом графе.
Одно из следствий – мы можем считать, что веса всех ребер у нас неотрицательные.
Лемма 2. Если веса всех ребер неотрицательные, и некоторое паросочетание состоит из ребер нулевого веса, то оно искомое.
Схема решения
for i:= 1 to n do begin
{каждой вершине одного из множеств находим назначение}
for j:=1 to n do min[j]:=maxint;
repeat
fillchar(new,sizeof(new),false);
f := dfs(i);{пару ищем только по ребрам нулевого веса}
if not f then begin
1) {ищем минимальный элемент в помеченных dfs строках new[i]=true
среди элементов столбцов не вошедших в текущую цепочку
(res[j] = 0) or (not new[res[j]])
обозначим найденный элемент del}
2) {перестраиваем матрицу так:
из всех помеченных dfs строк вычитаем del
ко всем вошедшим в текущую цепочку столбцам прибавляем del
end;
until f;
end;
for j:= 1 to n do
writeln(j,' ',res[j])
|
1 |
3 |
2 |
3 |
|
2 |
1 |
3 |
6 |
|
4 |
2 |
6 |
8 |
|
4 |
5 |
2 |
7 |
|
0 |
2 |
1 |
2 |
|
2 |
1 |
3 |
6 |
|
4 |
2 |
6 |
8 |
|
4 |
5 |
2 |
7 |
|
0 |
2 |
1 |
2 |
|
1 |
0 |
2 |
5 |
|
4 |
2 |
6 |
8 |
|
4 |
5 |
2 |
7 |
|
0 |
2 |
1 |
2 |
|
1 |
0 |
2 |
5 |
|
2 |
0 |
4 |
6 |
|
4 |
5 |
2 |
7 |
|
0 |
3 |
1 |
2 |
|
0 |
0 |
1 |
4 |
|
1 |
0 |
3 |
5 |
|
4 |
6 |
2 |
7 |
|
0 |
3 |
0 |
1 |
|
0 |
0 |
0 |
3 |
|
1 |
0 |
2 |
4 |
|
4 |
7 |
2 |
7 |
и т.д.
Понятная программа решения с быстрым пересчетом
const max=100;{размер большего из двух множеств}
var new: array[0..max] of boolean;
res, min, u, v: array[0..max] of integer;
n, i, j,
f: boolean;
function a(i,j:integer):integer;
begin
a:=c[j,i];{транспонированная матрица исходных данных}
end;
function dfs(i: integer): boolean;
{пытается найти вершине j пару}
var j: integer;
begin
if new[i] then {j в текущем паросочетании уже просмотрена}
begin dfs:= false; exit end;
new[i]:= true;
for j:= 1 to n do
if a(i, j)-u[i]-v[j]=0 then
if (res[j] = 0) or dfs(res[j]) then
begin
dfs:=true; res[j]:=i; exit
end
else
else
if ((res[j] = 0) or (not new[res[j]])) and
(a(i, j)-u[i]-v[j] < min[j]) then begin
min[j]:=a(i, j)-u[i]-v[j];
if
end;
dfs:=false;
end;
begin {
fillchar(res,sizeof(res),0);
fillchar(u,sizeof(v),0);
fillchar(v,sizeof(v),0);
n :=100;
for i:= 1 to n do begin
{каждой вершине одного из множеств находим назначение}
for j:=1 to n do min[j]:=maxint;
repeat
fillchar(new,sizeof(new),false);
f := dfs(i);{в эффективной программе заменяется на перестройку цепочки}
if not f then begin
for j:=1 to n do
if (res[j]>0)and new[res[j]] then begin
v[j]:=v[j]-del;
u[res[j]]:=u[res[j]]+del
end;
u[i]:=u[i]+
end;
until f;
end;
for j:= 1 to n do
writeln(j,' ',res[j])
end.
Программа решения за N^3
begin {
fillchar(res,sizeof(res),0);
fillchar(u,sizeof(v),0);
fillchar(v,sizeof(v),0);
…{задание исходных данных}
for i:= 1 to n do
{каждой вершине одного из множеств находим назначение}
begin
for j:=1 to n do min[j]:=maxint;{минимальные значения столбцов}
fillchar(new,sizeof(new),false);
j0 := 0;
res[0] := i;
repeat
new[j0] := true;{в данной версии мы метим столбцы!!!}
i0 := res[j0];
for j := 1 to n do
if not new[j] then begin
if a(i0,j)-u[i0]-v[j] < min[j] then begin
min[j] := a(i0,j)-u[i0]-v[j];
way[j] := j0
end;
if min[j] <
j1 := j
end
end;{нашли новое значение
for j := 0 to n do
if new[j] then begin
u[res[j]] := u[res[j]] +
v[j]:=v[j]-
end
else min[j] := min[j] -
j0 := j1; {}
until res[j0]=0; {свободный ноль позволит увеличить паросочетание}
repeat {перестраиваем цепочку с учетом выбранного нуля}
j1 := way[j0];
res[j0] := res[j1];
j0 := j1
until j0 = 0;
end;
writeln(-v[0]); {здесь мы получили сумму всех назначений}
for j:= 1 to n do
writeln(a(res[j],j));
end.