Bài toán cặp ghép trong pascal

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ố Cij. 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 xi thuộc X và nối T với các đỉnh yj 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: