Cáp ghép và lượng cực đại hai phía

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ị.