Bàn luận thêm về Cặp ghép
Nguyễn Tuấn Dũng
'Ghép cặp' các đốitượng theo một quan hệ nào đó là một bài toán mang tính hết sức tự
nhiên và cónhiều ý nghĩa trong ứng dụng thực tiễn. Chẳng hạn, các sinh viên ngành sư
phạmdo được nhà nước đào tạo miễn phí nên khi ra trường họ được phân công về dạyhọc
ở các trường miền núi. Nhưng những sinh viên đó được đưa ra danh sách nhữngtrường mà
mình muốn công tác với độ ưu tiên khác nhau. Một bài toán đặt ra làphải bố trí các sinh
viên này sao cho phù hợp nhất (có thể được) với sở thíchcủa mỗi người, tuy nhiên ở đây,
sinh viên nào có kết quả học tập tốt hơn sẽđược ưu tiên hơn. Hay ta có thể gặp vấn đề ghép
cặp trong các bài toán quenthuộc khác như: bài toán phân công công việc, bài toán hôn
nhân bền vững, bàitoán xếp thời khoá biểu...
Trong số 26(11/2001), tác giả Lê Văn Chương đã giới thiệu với chúng ta thuật toánKuhn-
Munkres giải bài toán tìm cặp ghép có tổng trọng số lớn nhất. ở đây, không đi vào thuật
toán tìm cặpghép có tổng trọng số lớn nhất nữa vì điều đó khá rõ ràng trong số báo
trước.Tuy nhiên, chúng ta sẽ xem xét thêm một chút để giúp các bạn phần nào tiếp cậngần
bài toán hơn và đỡ nhầm lẫn trong lúc cài đặt chương trình. Để tiện theodõi, ta tóm tắt lại
bài toán:
Cho G = (X U Y,E) là đồ thị hai phía đầy đủ, trong đó: X, Y là hai tập hữu hạn gồm n
phần tử, E là tập các cạnh của đồ thịvà với mỗi cạnh được gán với một trọng số C
ij
. Cần
tìm tập cặp ghépđầy đủ M có tổng trọng số lớn nhất.
Đối với bài toánnày có thể sử dụng bài toán luồng cực đại để giải bằng cách thêm vào G
hai đỉnhgiả S và T, nối với các đỉnh x
i
thuộc X và nối T với các đỉnh y
j
thuộc Ybằng các
cạnh có trọng số là 0. Tuy nhiên, bài toán cặp ghép cực đại là trườnghợp riêng của bài toán
luồng nên nó có những đặc điểm riêng và do đó dẫn đếnviệc giải quyết nó thì cũng có
những thuật toán đặc thù, mà tiêu biểu là thuậttoán gán nhãn, trong đó ta có thể đi theo hai

hướng chính:
Hướng thứnhất, xuất phát từ một cặp ghép M đầy đủ bất kỳ của G, ta xây dựng một nhãnF
tương ứng với M, nếu F chấp nhận được thì M là nghiệm cần tìm, ngược lại nhãnF là
không chấp nhận được thì ta tiếp tục điều chỉnh.
Hướng thứ hai,xây dựng một nhãn F chấp nhận được, sau đó tìm M tương ứng với F bằng
cách:khởi tạo M là tập rỗng, chừng nào mà M chưa đầy đủ thì ta còn tiếp tục điềuchỉnh
(tăng cặp ghép).
Thuật toánKunh-Munkres trình bày trên số báo 26 là cách giải thứ hai, được trình bày
khárõ ràng. Tuy nhiên có điểm cần chú ý trong bước 5 (sửa nhãn), lượng sửa nhãnkhông
phải:
d:=min {F(x
i
)+ F (y
j
) - C
ij
, x
i
thuộc S, y
j
thuộc T} (cóthể do lỗi khi in ấn) mà là:
d:=min {F(x
i
)+ F(y
j
) - C
ij
, x
i
thuộc S, y

j
thuộc T } (*)
Bởi vì, trongbước 3 khi không tìm được đường tăng cặp ghép ta mới phải sửa nhãn sao
cho:
- Nhãn F
mới
vẫn chấp nhận được.
- F
mới
vẫn tương ứng với M đang có, để cho số cạnh của G (F, M) không bị giảm đi.
- Tăng thêm sốcạnh trong đồ thị cân bằng tương ứng G (F, M)
Muốn tăng sốcạnh trong G(F, M) thì ta phải có thêm cặp x
i
', y
j
' khác,cụ thể (x
i
', y
j
') thuộc
G(F, M), sao cho: F(x
i
')+ F(y
j
') = C'
ij
. Đồng thời để cho sau khi thêm cạnh vàoG(F, M) ta
có thể tìm đường tăng cặp ghép thì cạnh cần thêm đó được chọn làcạnh nối giữa một đỉnh
x
i

đã được đi đến trong quá trình tìm đường ởbước 3 với một đỉnh y
j
' chưa được đi đến
trong quá trình đó.
Nếu lượng sửanhãn là d:=min{F(x
i
)+ F (y
j
) - C
ij
, x
i
thuộc S, y
j
thuộc T} thìsẽ dẫn đến
những sai sót khiến chương trình không cho ra kết quả. Thật vậy, tacho ra công thức sửa
nhãn:
F(x
i
) := F(x
i
)- d với x
i
thuộcS
F(y
j
) := F(y
j
)+ d với y
j

thuộcT
Xét một ví dụđơn giản, sau khi sửa nhãn với lượng sửa nhãn d như trên, đối với những
đỉnh x
i
thuộc S vày
j
thuộc T,ta có:
F(x
i
)
mới
:=F(x
i
)
cũ
- d
F(y
j
)
mới
:=F(y
j
)
cũ
Suy ra:
A = F(x
i
)
mới
+F(y

j
)
mới
- C
ij
= F(x
i
)
cũ
+ F(y
j
)
cũ
- C
ij
- d
Nhận thấy A cóthể dương, bằng không, hay âm tuỳ thuộc vào các x
i
, y
j
gán nhãn F
cũ
vì d chỉ
là min {F(x
i
)
cũ
+F(y
j
)

cũ
- C
ij
} đối với những đỉnh x
i
thuộc S, y
j
thuộc T.Do đó có thể xảy ra
F(x
i
)
mới
+ F(y
j
)
mới
< C
ij
với một vài cặp cạnh (x
i
,y
j
) nào đómà x
i
thuộc S,y
j
thuộc T.Nói cách
khác, nhãn F
mới
sẽ là không chấp nhận được, ít nhất là đốivới những đỉnh y

j
thuộc T.
Trong khi đó,theo như dưới đây ta sẽ thấy việc gán nhãn công thức (*) là hoàn toàn đúng
đắn.Thật vậy:
Ta có công thứcsửa nhãn:
F(x
i
) := F(x
i
)- d với x
i
thuộc S
F(y
j
) := F(y
j
)+ d với y
j
thuộc T
Nhận thấy, dotính chất đặc biệt của G(F, M), chỉ có thể đi từ y
j
sang x
i
khi và chỉ khi (x
i
, y
j
)
thuộc M nên tập S (tập các đỉnh đếnđược trong bước 3 tìm đường tăng cặp ghép) sẽ là tập
các đỉnh của X đã đượcghép cặp (trừ x

0
). Đồng thời, khi không có đường tăng cặp ghép
nghĩalà trong khi tìm đường đi, ta chỉ đến được các y
j
đã bị ghép cặp. Dođó tập T cũng là
tập các đỉnh của Y đã ghép cặp (với các đỉnh thuộc S)
Bây giờ ta sẽxem xét các trường hợp:
1. Đối vớinhững x
i
thuộcS: F(x
i
)
mới
:= F(x
i
)
cũ
- D
- Xét các đỉnh y
j
thuộc T: F(y
j
)
mới
:= F(y
j
)
cũ
Suy ra: F(x
i

)
mới
+ F(y
j
)
mới
- C
ij
= F(x
i
)
cũ
+ F(y
j
)
cũ
- C
ij
- D >= 0
(vì D = min {F(x
i
)
cũ
+ F (y
j
)
cũ
- C
ij
} với x

i
thuộc S, y
j
thuộc T)
do đó: F(x
i
)
mới
+ F(y
j
)
mới
>= C
ij
, x
i
thuộc S, y
j
thuộc T (1)
Vậy nhãn F vẫnchấp nhận được đối với những x
i
thuộc S và y
j
thuộc T.
Ngoài ra ta còncó thêm đẳng thức F(x
i
) + F(y
j
) = C
ij

trong đóx
i
thuộc S,y
j
thuộc Ttương ứng
với việc xảy ra dấu '=' trong bất đẳng thức lượng sửa nhãn (luôn luônxảy ra). Do đó dẫn tới
việc làm tăng thêm số cạnh của G(F, M).
- Xét y
j
thuộc T:F(y
j
)
mới
:= F(y
j
)
cũ
+ D
Do đó: F(x
i
)
mới
+ F(y
j
)
mới
= F(x
i
)
cũ

- D + F(y
j
)
cũ
+ D = F(x
i
)
cũ
+F(y
j
)
cũ
= C
ij
(2)
bởi vì với x
i
thuộc S vày
j
thuộcT trong bước 3 thì (x
i
, y
j
) là một cạnh của đồ thị cânbằng
tương ứng G(F, M
cũ
)
Như vậy, nhãn F
mới
vẫn tương ứng tập cặp ghép M

cũ
ngay cả với những đỉnh bị sửa
nhãn.Đối với những đỉnh còn lại của M
cũ
không bị sửa nhãn thì cũng vẫntương ứng với F
mới
vì F
mới
là giữ nguyên giá trị của F
cũ
đối với những đỉnh này.
2. Đối với x
i
thuộc S:F(x
i
)
mới
= F(x
i
)
cũ
mà: F(y
j
)
mới
= F(y
j
)
cũ
với y

j
thuộc T
F(y
j
)
mới
= F(y
j
)
cũ
+ D với y
j
thuộc T
thì: F(x
i
)
mới
+ F(y
j
)
mới
>= F(x
i
)
cũ
+ F(y
j
)
cũ
>= C

ij
(3)
(vì nhãn F
cũ
là chấp nhận được)
Tóm lại, từ (1)(2) (3) ta kết luận sau khi sửa nhãn, nhãn F
mới
vẫn chấp nhận đượcvà tương
ứng với M
cũ
đang có, đồng thời thêm được cạnh trong G(F,M). Do đó, quay lại bước 3 ta
vẫn có thể tìm được đường tăng cặp ghép và tiếptục các bước tiếp theo của thuật toán.
Trên đây đã bànluận một số chi tiết trong các bước thực hiện thuật toán Kuhn-Munkres.
Tiếptheo, vấn đề đặt ra là đối với bài toán tìm cặp ghép đầy đủ có tổng trọng sốnhỏ nhất
thì sao?
Cặp ghép đầy đủ cótổng trọng số nhỏ nhất
Nếu bạn xem xétkỹ lưỡng một chút về thuật toán Kuhn-Munkres thì có thể thấy ngay bài
toán nàyhoàn toàn tương tự với bài toán tìm cặp ghép có tổng trọng số lớn nhất. Chỉ
cầnsửa lại một chút như sau:
+ Thứ nhất,nhãn F được gọi là chấp nhận được nếu F(x
i
) + F(y
j
) <=C
ij
Như vậy, có thểkhởi tạo: F(x
i
) := 0
F(y
j

):= min {C
ij
, x
i
thuộcX }, y
j
thuộcY
+ Thứ hai,lượng sửa nhãn: d:= max{F(x
i
)+ F(y
j
) - C
ij
, x
i
thuộc S, y
j
thuộc T}
với nhận xét: d<= 0
Hoặc: d:=min {C
ij
- F(x
i
)- F(y
j
), x
i
thuộcS, y
j
thuộc T}

thì d >= 0 vàkhi đó, công thức sửa nhãn sẽ là: F(x
i
):= F(x
i
) + d
F(y
j
):= F(y
j
) - d
Cách khác, đơngiản hơn, chúng ta có thể thấy để tìm M có tổng trọng số nhỏ nhất, chỉ cần
đổidấu các phần tử của ma trận trọng số rồi tìm cặp ghép có tổng trọng số lớn nhấtvới ma
trận trọng số mới này. Cặp ghép đó sẽ chính là cặp ghép có tổng trọng sốnhỏ nhất cần tìm
đối với ma trận trọng số ban đầu.
Như chúng ta đãbiết bài toán cặp ghép được xem xét theo hai khía cạnh. Trường hợp thứ
nhất,người ta quan tâm đến việc ghép cặp đầy đủ và thoả mãn tính tối ưu như bài
toánKuhn-Munkres ở trên. Nhưng trong trường hợp khác, người ta lại không quan tâmđến
việc ghép cặp đầy đủ với tổng trọng số lớn nhất mà cần tìm một tập cặp ghépcó số lượng
cặp ghép là cực đại (không quan tâm đến trọng số trên các cạnh củacặp ghép). Khi đó
chúng ta sẽ có một bài toán khác dưới đây:
Cặp ghép cực đại
Để minh hoạ, taxét một bài toán cụ thể, bài toán Phân công thợ-việc: Có N người thợvà M
công việc, mỗi công việc, mỗi một người thợ chỉ biết làm một số công việcnhất định. Cần
phân công mỗi thợ chỉ làm một việc và mỗi việc chỉ được làm bởimột thợ sao cho có nhiều
công việc được làm nhất. Khả năng làm việc của các thợđược cho trong ma trận C
ij
với C
ij
= 1 thì thợ i biết làmviệc j, C
ij

=0 thì thợ i không biết làm việc j.
Ta nhận thấyhoàn toàn có thể giải bài toán này bằng thuật toán Kunh-Munkres. Tuy nhiên,
vấnđề ở đây là bài toán của chúng ta đơn giản hơn nhiều và tất nhiên, có thể giảiquyết nó
bằng một cách riêng khá dễ dàng.
Bàn luận thêm về cặp ghép
Nguyễn Tuấn Dũng
(Tiếp theo số trước)
Nhắc lại bài toán phân công Thợ - Việc: Có N người thợ và M công việc, mỗi côngviệc,
mỗi một người thợ chỉ biết làm một số công việc nhất định. Cần phân côngmỗi thợ chỉ làm
một việc và mỗi việc chỉ được làm bởi một thợ sao cho có nhiềucông việc được làm nhất.
Khả năng làm việc của các thợ được cho trong ma trận C
ij
với C
ij
= 1 thì thợ i biết làm việc
j, C
ij
=0 thì thợ ikhông biết làm việc j.
Ta nhận thấy hoàn toàn có thể giải bài toán nàybằng thuật toán Kunh-Munkres. Tuy nhiên,
vấn đề ở đây là bài toán của chúng tađơn giản hơn nhiều và tất nhiên, có thể giải quyết nó
bằng một cách riêng khádễ dàng.
Với các khái niệm và định nghĩa như trong bàitoán Kunh-Munkres (tuy nhiên, đồ thị hai
phía G ở đây không nhất thiết đầy đủ),ta sử dụng định lý sau để có được thuật toán: