Cặp ghép và luồng cực đại trên đồ thị hai phía
Nguyễn Thanh Tùng
Trong một số bài viết trước tôi có đề cập đến thuật toán 'cặp ghép' và 'luồng'. Sau khi bài
viết được đăng, có bạn đọc phản hồi để nghị trình bày kĩ hơn về các thuật toán đó. Trong
bài viết này tôi sẽ trình bày về thuật toán tìm cặp ghép cực đại và tìm luồng cực đại trên
đồ thị hai phía.
1. Cặp ghép cực đại của đồ thị hai phía
1. Các định nghĩa
G được gọi là đồ thị hai phía nếu G=(X hợp Y,E); trong đó tập đỉnh V là hợp của 2 tập
đỉnh con X,Y rời nhau và tập cạnh E chỉ chứa các cạnh có một đỉnh thuộc X và đỉnh còn
lại thuộc Y. Như thế, về mặt trực quan đồ thị 2 phía có dạng:
Đồ thị hai phía có thể dùng biểu diễn nhiều mối quan hệ, thường là giữa 2 tập đối tượng
khác nhau: chẳng hạn giữa công nhân và công việc hay vị trí trên dây truyền sản xuất, giáo
viên và môn học,…
Thông thường đồ thị hai phía thường được biểu diễn bởi một ma trận quan hệ A (n,m). Khi
đó:
- Tập X có n đỉnh, đánh số từ 1 đến n.
- Tập Y có m đỉnh, đánh số từ 1 đến m.
- Với 'i thuộc X, j thuộc Y nếu có cạnh (i,j) thì đặt A[i,j]=1; ngược lại thì A[i,j]=1.
Cặp ghép M là một tập con của E sao cho không có đỉnh nào của X hay Y thuộc nhiều hơn
1 phần tử của M (M chứa các cạnh đôi một không có đỉnh chung). Nói cách khác mỗi đỉnh
thuộc X hay thuộc Y đều chỉ được tương ứng ('ghép') với nhiều nhất là một đỉnh khác
thuộc tập kia, tất nhiên giữa cặp đỉnh đó phải có cạnh nối. Cặp ghép M được gọi là cặp
ghép cực đại nếu nó có chứa nhiều cặp đỉnh nhất.
Khi X và Y có số phần tử bằng nhau và bằng N, ta có khái niệm cặp ghép đầy đủ là cặp
ghép có đúng N phần tử. Nói một cách nôm na đồ thị có cặp ghép đầy đủ nếu mọi đỉnh i
thuộc X đều được tương ứng với duy nhất một đỉnh j thuộc Y và ngược lại (tất nhiên giữa i
và j phải có cạnh nối).
2. Ví dụ
Ví dụ một bài toán về tìm cặp ghép cực đại: Có N chàng trai và M cô gái. Mỗi chàng trai
mến một hoặc có thể nhiều cô gái. Hãy tổ chức nhiều nhất các cặp nhảy, trong đó mỗi

chàng trai sẽ nhảy với một cô gái mà mình mến.
Đồ thị 2 phía ở đây có tập đỉnh X là N chàng trai, tập đỉnh Y là M cô gái. Nếu chàng trai i
mến cô gái j thì có cạnh (i,j). Việc tổ chức các cặp nhảy chính là tìm cặp ghép cực đại trên
đồ thị.
Nếu N=M và yêu cầu của bài là tìm cách ghép để ai cũng có bạn nhảy thì bài toán trở thành
việc tìm cặp ghép đầy đủ.
3. Thuật toán và cài đặt
Với cặp ghép M, các đỉnh thuộc các cạnh trong M gọi là đỉnh đã ghép, các đỉnh còn lại gọi
là đỉnh tự do.
Phương pháp xây dựng cặp ghép cực đại của đồ thị như sau:
- Khởi tạo M là rỗng.
- Với mỗi đỉnh x thuộc X, tìm cho nó một đường tăng cặp ghép. Nếu có thì tăng cặp ghép.
Cho đến khi không tăng được nữa thì ta có cặp ghép cực đại.
Đường tăng cặp ghép xuất phát từ đỉnh x là một đường đi trên G có dạng như sau:
x , y
1
, x
1
, y
2
, x
2
, …, y
k
, x
k
, y.
Trong đó y là đỉnh tự do thuộc Y, các cạnh (x
i
,y

i
) thuộc M, i=1..k (k có thể bằng 0), tức là
(x
i
,y
i
) là cặp đỉnh đã được ghép.
Với đường tăng cặp ghép trên ta tăng cặp ghép bằng cách: loại tất cả các cạnh (x
i
,y
i
) khỏi
M và thay vào đó là các cạnh (x,y
1
), (x
1
,y
2
) … (x
k
,y). Dễ thấy nhờ đó M tăng thêm một
phần tử.
Cài đặt:
Thuật toán tìm đường tăng cặp ghép cho đỉnh x dùng phương pháp BFS. Ta sử dụng một
số cấu trúc dữ liệu sau:
queue: hàng đợi với các thao tác: put để thêm một phần tử vào queue, get để lấy ra một
phần tử và hàm empty báo queue đã rỗng hay chưa.
m
x
, m

y
là 2 mảng ghi nhận cặp ghép: mx[i], my[j] tương ứng là đỉnh ghép của i hay j. Bằng
0 tức là còn tự do, chưa được ghép với đỉnh nào.
tr là mảng lần vết, mô tả đỉnh trước của một đỉnh trên đường đi. tr[j]=0 tức là đỉnh j chưa
thăm.
procedure find(x);
begin
queue := ∅ tr[j] := 0 với mọi j ;
put(x);
repeat
get(i);
for j := 1 to n do
if (tr[j] = 0) and (i,j) thuộc E then
tr[j] := i;
if my[j]=0 then begin
trace (j);
exit;
end
else put(my[j]);
until empty(queue);
end;
Thủ tục trace thực hiện việc lần vết để xây dựng đường tăng cặp ghép đồng thời tăng cặp
ghép.
procedure trace(j);
begin
repeat
i := tr[j];
t := mx[i];
mx[i] := j;
my[j] := i;

j := t;
until j=0;
end;
Và thuật toán tìm cặp ghép cực đại tiến hành như sau:
procedure match;
begin
for x := 1 to n do find(x);
end;
Đó là thuật toán kiểm tra tìm cặp ghép cực đại. Ta cũng có thể dùng nó để kiểm tra đồ thị
có cặp ghép đầy đủ không (Nếu đỉnh nào cũng được ghép thì đồ thị có cặp ghép đầy đủ).
Bạn đọc có thể tự lập trình giải bài toán ghép cặp nhảy ở trên.
Thuật toán cặp ghép áp dụng với kĩ thuật tìm kiếm nhị phân cho kết quả rất ấn tượng với
nhiều bài toán. Các bạn có thể xem lại bài viết về Kĩ thuật tìm kiếm nhị phân của tôi trên
số báo trước. Ngoài ra với cách nhìn nhận thích hợp ta có thể đưa một bài toán khó về một
bài toán cặp ghép.
Tuy nhiên đôi khi trên đồ thị 2 phía nếu nhìn nhận bài toán theo kiểu cặp ghép thì độ phức
tạp tính toán rất cao. Chẳng hạn ở bài xe bus, nếu số hành khách cỡ hàng ngàn và số chỗ
trên xe cũng cỡ hàng trăm (điều đó đúng với thực tế hơn) thì giải bằng cặp ghép không tốt
bằng giải bằng 'luồng'. Sau đây tôi sẽ trình bày về thuật toán luồng trên đồ thị hai phía.
II. Luồng cực đại của đồ thị hai phía
1. Các định nghĩa
Đồ thị hai phía G trong bài toán luồng vẫn có cấu trúc như đối với bài toán cặp ghép,
nhưng có thêm trọng số đối với cả đỉnh và cạnh: mỗi đỉnh i thuộc X, j thuộc Y và cạnh (i,j)
thuộc E đều có một trọng số kèm theo gọi là 'khả năng thông quá, được kí hiệu tương ứng
là Cx(i), Cy(j) và C(i,j).
'Luồng' trên G bao gồm các giá trị kèm theo mỗi đỉnh i thuộc X, j thuộc Y và cạnh (i,j)
thuộc E được kí hiệu tương ứng là Lx(i), Ly(j) và L(i,j) thoả mãn các điều kiện.
1. Điều kiện thông qua: '0 ≤ luồng ≤ khả năng thông quá.
2. Điều kiện cân bằng luồng: 'tổng luồng ra qua mỗi đỉnh bằng tổng luồng vàó.
Các điều kiện trên có thể mô tả qua kí hiệu như sau:

0 ≤ Lx(i) ≤ Cx(i); 0 ≤ Ly(i) ≤ Cy(i); 0 ≤ L(i,j) ≤ C(i,j) với mọi i,j.
Ta sẽ hiểu rõ hơn những kí hiêu đó khi phân tích ví dụ sau: bài toán xe bus.
2. Ví dụ
Có K khách cần đến N khách sạn. Có M xe bus và xe bus thứ i có q[i] chỗ ngồi. Mỗi xe
bus trên hành trình sẽ dừng trả khách tại một số khách sạn, và mỗi xe chạy một tuyến nên
có thể đỗ tại các khách sạn không giống nhau. Hãy sắp xếp hành khách lên xe sao cho:
1. Số hành khách lên mỗi xe ≤ số ghế ngồi trên xe.
2. Mỗi hành khách đều ngồi lên xe có dừng tại khách sạn mình cần đến.
Phân tích:
Đồ thị hai phía được mô tả bởi:
- Tập X là tập N khách sạn. 'Khả năng thông quá của khách sạn i là: Cx(i) = số khách cần
đến khách sạn i.
- Tập Y là tập M xe bus. 'Khả năng thông quá của xe bus j là số khách tối đa mà xe j có thể
chở: Cy(j) = q[j].
- Nếu xe bus j dừng tại khách sạn i thì có cạnh (i,j), 'khả năng thông quá của cạnh này là
C(i,j)=min(Cx(i),Cy(j)). Ngược lại ta đặt C(i,j)=0.
- Luồng trên cạnh (i,j): L(i,j) sẽ là số hành khách cần về khách sạn i được xếp lên xe j.
Luồng ở đỉnh i thuộc X: Lx(i) là số hành khách được chở đến khách sạn i; luồng ở đỉnh j
thuộc Y: Ly(j) là số khách được xếp lên xe j. Luồng có thể bằng 0.
Dễ dàng kiểm tra các điều kiện của luồng. (Ví dụ: số hành khách mà xe j chở = tổng số
hành khách xe j chở đến từng khách sạn mà nó đi qua, tức là ).
Nếu luồng cực đại ở mỗi đỉnh bằng khả năng thông qua thì ta có cách sắp xếp khách thoả
mãn 2 điều kiện đã cho. Chú ý là thứ tự khách không quan trọng (xếp lên xe nào cũng
được, miễn là đi đến nơi cần đến). Chẳng hạn nếu L(1,1) = 3 thì chọn 3 khách chưa được
xếp, cần về khách sạn 1 cho lên xe 1. Nếu còn 3 người nữa và có L(1,2) = 1 và L(1,3) = 2
thì xếp 1 người lên xe 2 và 2 người lên xe 3, người nào lên xe nào cũng được. Chú ý là
nên luôn có đủ chỗ trên các xe, và ai cũng được lên xe.
Vậy, chỉ còn vấn đề tìm được luồng cực đại thôi. Thuật toán như sau:
3. Thuật toán
Phương pháp xây dựng cặp ghép cực đại của đồ thị như sau:

1. Khởi tạo luồng bằng 0.
2. Tìm cho nó một đường tăng luồng. Nếu có thì tăng. Nếu không tìm được một đường
tăng luồng nào nữa thì ta được luồng cực đại.
Đường tăng luồng là một đường đi trên đồ thị hai phía có hướng Gx, có tập đỉnh là X hợp
Y, tập cạnh được xây dựng như sau:
- Nếu L(i,j)
- Nếu L(i,j)>0 thì có cung (j,i) từ Y sang X, được gọi là cung ngược.
Đường tăng luồng tìm bằng thuật toán BFS trên Gx, xuất phát từ một đỉnh x thuộc X mà
Lx(x)<Cy(y).
Giả sử các đỉnh trên đường đi đó như sau:
x j
1
i
1
y
2
i
2
… y
k
x
k
y.
Thế thì ta thấy:
Lx(x)
Để đảm bảo điều kiện cân bằng luồng tại x, ta phải tăng luồng trên cạnh (x,j
1
) lên một
lượng d (chú ý đó là một cung xuôi của Gx). Để làm được điều đó thì d≤C(x,j
1

)-L(x,j
1
).
Do ta không được thay đổi luồng tại đỉnh j
1
nên để đảm bảo điều kiện kiện cân bằng luồng
tại j
1
thì ta phải giảm luồng trên cạnh (i
1
,j
1
) là d, và như vậy d≤L(i
1
,j
1
). Chú ý (j
1
,i
1
) là cung
ngược.
Suy luận tương tự ta thấy:
- Luồng trên cạnh chứa cung xuôi được tăng một lượng d.
- Luồng trên cạnh chứa cung ngược bị giảm một lượng d.
- Luồng tại x và y tăng một lượng d, tại các đỉnh khác thì không đổi.
Ta có d là giá trị lớn nhất có thể chọn mà vẫn đảm bảo điều kiện thông qua thì:
d = min(Cx(x)-Lx(x), Cy(y)-Ly(y),
C(i,j)-L(i,j) với (i,j) là cung xuôi,
L(i,j) với (j,i) là cung ngược).

Như vậy mỗi lần tìm được một đường tăng luồng thì tổng luồng trên toàn bộ đồ thị được
tăng thêm một lượng d. Khi không tìm được đường tăng luồng nữa thì ta có luồng cực đại.
Sau đây là chương trình cài đặt thuật toán tìm luồng cực đại trên đồ thị hai phía. Các bạn
hãy tập đọc để tìm hiểu cách cài đặt và rèn luyện kĩ năng đọc hiểu chương trình của người
khác..
program bflow;
const
inp = 'bflow.inp';
out = 'bflow.out';
max = 100;
type
mang1 = array[1..2*max] of integer;
mang2 = array[1..max,1..max] of integer;
var
N,M,d:integer;
L,C:mang2;
Lx, Ly, Cx, Cy, Tx, Ty, Dt:mang1;
found:boolean;
(*********************)
procedure nhap;
var
i,j:integer;
f:text;
begin
assign(f, inp);
reset(f);
readln(f, N, M);
for i:=1 to N do read(f,Cx[i]);
readln(f);
for j:=1 to M do read(f,Cy[j]);

readln(f);
for i:=1 to N do begin
for j:=1 to M do
read(f,C[i,j]);
readln(f);
end;
close(f);
end;
(*********************)
function min(x,y:integer): integer;
begin
if x end;
procedure trace(j:integer);