Trong bài này chúng ta tìm hiểu một số ứng dụng của bài toán cặp ghép cực đại trong đồ thị hai phía. Một số ứng dụng khá hiên nhiên như: lập lich trên các máy song song, ghép đôi nam-nữ, mình sẽ không nhắc đến ở đây. Đối tượng của bài viết này là các bài toán không tầm thường mà chúng ta có quy được về bài toán cặp ghép. Một bài toán điển hình là domino tiling mà mình đã có dịp trình bày trong bài quy dẫn trước đây. Bài này, chúng ta sẽ tìm hiểu ứng dụng của cặp ghép trong ba bài toán khác: phủ chu trình (cycle cover) trong đồ thị có hướng, phủ đỉnh (vertex cover) trong đồ thị hai phía và phủ các phần tử 0 trong ma trận bằng hàng/cột. (Nói chung các bài toán phủ.)

Phủ chu trình

 
Xem minh họa trong Figure 1(a).

Figure 1: (a) Một đồ thị có hướng và một phủ chu trình (các cung màu xanh) của đồ thị. (b) Đồ thị hai phía thu được sau phép quy tương ứng với đồ thị đầu vào ở hình (a).

Bài toán đặt ra là: cho một đồ thị có hướng $\vec{G}(V,\vec{E})$, tìm một phủ chu trình (nếu có) của $\vec{G}$. Bài toán này có thể giải bằng cách quy về bài toán cặp ghép cực đại trên đồ thị hai phía như sau:

Ta xây dựng một đồ thị hai phía $G(A\cup B, E)$ trong đó $A = V$ và $B$ là một bản sao của $V$. Với mỗi đỉnh $u \in A$, ta kí hiệu bản sao của nó trong $B$ là $u'$. Với mỗi cung $u\rightarrow v \in \vec{E}$, ta thêm một cạnh $uv'$ nối $u \in A$ và bản sao $v'$ của $v$ trong $B$. Xem hình minh họa trong Figure 1(b).

 
Chứng minh: Ta phải chứng minh hai chiều của Theorem 1.

Chiều thuận: $\vec{G}$ có phủ chu trình thì $G$ có một cặp ghép hoàn hảo. Thật vậy, gọi $\mathcal{C}$ là một phủ chu trình của $\vec{G}$, và $C$ là một chu trình (có hướng) trong $\mathcal{C}$. Với mỗi cung $ u \rightarrow v \in C$, ta thêm cạnh $uv'$ vào tập cạnh $M$. Không khó để thấy rằng $M$ là một cặp ghép; chi tiết coi như bài tập cho bạn đọc (bài tập 1 dưới đây). Do $\mathcal{C}$ phủ toàn bộ tập đỉnh của đồ thị, $M$
ghép tất cả các đỉnh trong $G$, do đó, nó là một cặp ghép hoàn hảo. Xem hình minh họa trong Figure 1(b). Các cạnh màu xanh là cặp ghép hoàn hảo tương ứng với phủ chu trình trong Figure 1(a) tìm được theo thủ tục này.

Chiều ngược: $G$ có một cặp ghép hoàn hảo thì $\vec{G}$ có phủ chu trình. Gọi $M$ là một cặp ghép hoàn hảo của $G$. Ta xây dựng phủ chu trình của $G$ như sau. Ban đầu $\mathcal{C} \leftarrow \emptyset$. Gọi $u_0 \in A$ là một đỉnh chưa được phủ bởi $\mathcal{C}$. Gọi $u_0u'_1, u_1u'_2,$ $\ldots,u_{k-1}u'_k, u_ku'_0$ là một dãy các cạnh của cặp ghép $M$, bắt đầu từ $u_0$ và kết thúc tại $u'_0$ (bản copy của $u_0$ trong $B$). Xem ví dụ minh họa một dãy cạnh như vậy trong Figure 2(b). Không khó để thấy rằng dãy này xác định duy nhất vì mỗi đỉnh được ghép với duy nhất một đỉnh khác trong $M$.

Gọi $C = \{u_0,u_1,\ldots, u_k\}$ là một dãy các đỉnh thuộc $A$ theo thứ tự xuất hiện trong dãy cạnh trên. Ta có:

Nhận xét: $C$ xác định một chu trình duy nhất trong $\vec{G}$.

Xem minh họa trong Figure 2(c). Thêm $C$ vào $\mathcal{C}$ và lặp lại cho đến khi mọi đỉnh của $A$ đều được phủ bởi $\mathcal{C}$. Chứng minh $\mathcal{C}$ thu được sau quá trình này là một phủ chu trình của đồ thị $\vec{G}$ coi như bài tập cho bạn đọc (bài tập 2) (dpcm).

Figure 2: (a) Một cặp ghép hoàn hảo khác (các cạnh màu đỏ) của đồ thị hai phía trong Figure 1(b). (b) Một dãy cạnh $ad', df', fa'$ của cặp ghép bắt đầu từ $a$ và kết thúc tại $a'$ như trong chứng minh chiều ngược của Theorem 1. Dãy đỉnh trong $A$ tương ứng với dãy cạnh này là $\{a,d,f\}$. (c) Chu trình tương ứng trong $\vec{G}$ với dãy đỉnh $\{a,d,f\}$.

Phủ đỉnh trong đồ thị hai phía

Bài toán tìm một phủ đỉnh (vertex cover) có ít đỉnh nhất (cực tiểu) trong đồ thị (tổng quát) là một bài toán NP-hard mà mình giới thiệu trước đây. Tuy nhiên, nếu đồ thị đầu vào là hai phía thì ta có thể tìm một phủ đỉnh cực tiểu trong thời gian đa thức, sử dụng cặp ghép. Trước hết ta nhắc lại khái niệm phủ đỉnh:

Trong bài này, ta chỉ xét đồ thị đầu vào là đồ thị hai phía, kí hiệu $G(A\cup B, E)$. Gọi $M$ là một cặp ghép cực đại của $G(A\cup B, E)$ và $\tau(G)$ là một phủ đỉnh cực tiểu của $G$. Ta có:

 
Chứng minh: Ta sẽ chứng minh hai chiều của Theorem 2.

$|M| \leq |\tau(G)|$: do $\tau(G)$ là một phủ đỉnh, ít nhất một trong hai đỉnh của mỗi cạnh $e\in M$ phải thuộc $\tau(G)$.

$|\tau(G)| \leq |M|$: Gọi $U \in V\setminus V(M)$ là một tập các đỉnh không được ghép của $G$. Ta gọi $U$ là tập các đỉnh tự đo. Gọi $u \in U$ là một đỉnh tự do. Không mất tỉnh tổng quát, ta giả sử $u \in A$. Ta thực hiện định hướng cạnh của $G(A\cup B, E)$ như trong thuật toán tìm đường tăng của đồ thị hai phía: định hướng các cạnh $E\setminus M$ từ $A$ sang $B$ và các cạnh của $M$ từ $B$ sang $A$.

Từ $u$, ta xây dựng cây BFS, kí hiệu $T_u$, có hướng (trên đồ thị đã định hướng) gốc tại $u$. Ta gán nhãn chẵn/lẻ cho các đỉnh của $T_u$ như sau: gốc $u$ có nhãn chẵn và với mọi cung $u\rightarrow v$ ($u$ là cha của $v$) trong $T_u$, nhãn của $v$ ngược với nhãn của $u$ ($u$ lẻ thì $v$ chẵn và ngược lại). Ta đưa tất cả các đỉnh có nhãn lẻ vào $\tau(G)$. Gọi $H = G\setminus V(T_u)$ là đồ thị thu được sau khi xóa các đỉnh của $T_u$ ra khỏi $G$. Ta có nhận xét sau:

Nhận xét: (i) $T_u$ chỉ chứa $u$ là đỉnh tự do duy nhất, (ii) mọi cạnh trong tập $E\setminus E(H)$ đều có một đầu mút là một đỉnh lẻ của $T_u$, (iii) với mỗi cạnh $e \in M\cap T_u$, ta chỉ đưa đúng một đầu mút (có nhãn lẻ) của nó vào $\tau(G)$, (iv) nếu $u \in A$ ($u\in B$) thì tất cả các đỉnh nằm trong $A$ ($B$) của $T_u$ có nhãn chẵn.

Nhận xét (i) là do $M$ là một cặp ghép cực đại: nếu tồn tại một đỉnh tự do khác trong $T_u$ thì ta sẽ tìm được một đường tăng của $M$ trong $G$. Nhận xét (iii) khá hiển nhiên từ cách ta thêm đỉnh vào $\tau(G)$. Nhật xét (iv) có thể chứng minh bằng quy nạp; chi tiết không đề cập ở đây. Để chứng minh nhận xét (ii), gọi $e$ là một cạnh trong $E\setminus E(H)$. Nếu $e$ có cả hai đầu mút trong $T_u$, một đầu mút của $e$ phải có nhãn lẻ và đầu mút còn lại có nhãn chẵn vì $G$ hai phía ($G$ không có chu trình lẻ). Nếu đúng một đầu mút của $e$ trong $T_u$, đầu mút đó phải có nhãn lẻ vì nếu không, đầu mút kia sẽ bị thêm vào cây $T_u$ trong quá trình BFS. Do đó, nhận xét (ii) đúng. Xem minh họa trong Figure 2(a-c).

Sau khi đã xây dựng $T_u$, ta xóa tất cả các đỉnh của $T_u$ ra khỏi đồ thị gốc $G(A\cup B, E)$. Ta lặp lại quá trình xây dựng cây đối với các đỉnh tự do khác. Mỗi lần xây dựng một cây mới, ta lại thêm các đỉnh có nhãn lẻ của cây đó vào $\tau(G)$. Chú ý, nếu ta xây dựng cây cho đỉnh tự do $v \in B$, ta sẽ phải định hướng đồ thị ngược lại: các cạnh $E\setminus M$ sẽ được định hướng từ $B$ sang $A$ và các cạnh của $M$ sẽ được định hướng từ $A$ sang $B$.

Phần còn lại cuối cùng của đồ thị sau khi ta đã xóa hết các đỉnh tự do (và các đỉnh trong cây tương ứng) là một đồ thị con của $G$ có các cạnh (còn lại) của $M$ là một cặp ghép hoàn hảo. Xem minh họa trong Figure 2(d). Ta chỉ việc thêm tất cả các đỉnh của đồ thị con nằm trong $A$ vào $\tau(G)$. Bước này kết thúc quá trình xây dựng $\tau(G)$.

Dựa trên nhận xét (ii), không khó để chứng minh $\tau(G)$ là một phủ đỉnh của $G$ (bài tập 3). Từ nhận xét (iii), ta suy ra $|\tau(G)| = |M|$ (dpcm).

Figure 2: (a) Một đồ thị hai phía $G(A\cup B, E)$ và một cặp ghép cực đại $M$ (các cạnh màu đỏ) của đồ thị. Các đỉnh $1,9,c,f$ là các đỉnh tự do. (b) Cây $T_1$ thu được khi ta thực hiện BFS từ đỉnh tự do 1 trên đồ thị định hướng theo mô tả trong chứng minh của Theorem 2. Ta thêm $\{a,d\}$ vào $\tau(G)$ tại bước này. (c) Đồ thị thu được sau khi xóa cây $T_1$ khỏi $G$. Các bạn nên đối chiếu các nhận xét trong chứng minh Theorem 2 tại bước này. (d) Tiếp tục xây dựng cây BFS $T_c$ từ đỉnh tự do $c$. Chú ý, $c \in B$ nên ta phải thay đổi cách định hướng cạnh. Ta thêm $\{3,7,8\}$ vào $\tau(G)$ tại bước này. (e) Phần còn lại sau khi đã xóa cây $T_c$ và các đỉnh tự do cô lập ra khỏi đồ thị. Các cạnh của $M$ chính là một cặp ghép hoàn hảo của đồ thị con. Giả sử ta thêm các đỉnh bên trái $\{4,6\}$ vào $\tau(G)$, ta thu được $\tau(G) = \{a,d,3,7,8,4,6\}$. Dễ thấy $|\tau(G)| = |M| = 7$.

Chứng minh của Theorem 2 cũng cho ta cách tìm một phủ đỉnh cực tiểu của $G(A\cup B, E)$ khi ta đã biết một cặp ghép cực đại $M$ của $G$ trong thời gian $O(m+n)$.

Remark: Để thực thi được thuật toán mô tả trong chứng minh Theorem 2 trong thời gian $O(n+m)$ (bài tập 4), bạn đọc cần phải cẩn thận một chút. Trong thực thi thuật toán, ta sẽ không định hướng tất cả các cạnh như trong mô tả của chứng minh. Cách mô tả này chỉ phục vụ việc hiểu thuật toán dễ dàng hơn mà thôi. Chi tiết bạn có thể tham khảo trong cách thực thi tìm cặp ghép cực đại của đồ thị hai phía.

Xóa hàng/cột trong ma trận

Xem ví dụ minh họa trong Figure 3.

Figure 3: (a) Một ma trận $9\times 9$. Các phần tử bỏ trống trong ma trận là các phần tử khác 0. (b) Một cách xóa 7 hàng/cột của ma trận; 7 cũng là số hàng/cột nhỏ nhất mà ta có thể xóa sao cho ma trận sau khi xóa không chứa phần tử 0.

Một ứng dụng của bài toán này là trong thuật toán Hungary giải bài toán tìm cặp ghép cực đại trên đồ thị hai phía có trọng số.

Ta sẽ quy bài toán xóa hàng/cột trong ma trận này về bài toán tìm phủ đỉnh cực tiểu trên đồ thị hai phía (mà ta đã giải ở trên). Gọi $G(A \cup B, E)$ là đồ thị hai phía trong đó đỉnh thứ $i$ của $A$ đại diện cho hàng thứ $i$ của $X$ và đỉnh thứ $j$ của $B$ đại diện cho cột thứ $j$ của $X$. $|A| = |B| = n$. $G$ có cạnh $(i,j)$ khi và chỉ khi $X[i,j] = 0$. Gọi $\eta(X)$ là một tập các hàng/cột có kích thước nhỏ nhất sao cho sau khi xóa các hàng/cột trong $\eta(X)$, ma trận thu được có các phần tử đều khác 0. Ta có:

 
Chứng minh Theorem 3 coi như bài tập cho bạn đọc. Nếu để ý kĩ, bạn sẽ thấy ma trận trong Figure 3(a) có đồ thị quy dẫn tương ứng $G(A\cup B, E)$ chính là đồ thị trong Figure 2(a). Trong Figure 2, ta đã tìm được một tập phủ đỉnh cực tiểu $\tau(G) = \{a,d,3,4,6,7,8\}$. Các hàng/cột bị xóa đi trong Figure 3(b) chính là các hàng/cột tương ứng với các đỉnh trong $\tau(G)$.

Tham khảo

[1] J. Erickson. Notes on Applications of Maximum Flow. UIUC, 2013.
[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2001) [1990]. 27.3 Maximum Bipartite Matching. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416–424. ISBN 0-262-03293-7.

Bài tập

Bài 1: Chứng minh rằng $M$ trong chiều thuận của chứng minh Theorem 1 là cặp ghép của $G(A\cup B, E)$.

Bài 2: Chứng minh rằng $\mathcal{C}$ thu được từ thuật toán trong chiều nghịch của chứng minh Theorem 1 là một phủ chu trình của $\vec{G}$.

Bài 3: Sử dụng nhận xét (ii), chứng minh rằng $\tau(G)$ thu được trong chứng minh chiều $|\tau(G)| \leq |M|$ của Theoremm 2 là một phủ đỉnh. Gợi ý: sử dụng quy nạp.

Bài 4: Mô tả chi tiết cách thực thi tìm một phủ đỉnh cực tiểu của đồ thị hai phía khi biết một cặp ghép. Bạn có thể giả sử cặp ghép được mô tả bởi một mảng $M[1,2,\ldots, |A| + |B|]$ trong đó $M[i]$ chính là đỉnh được ghép với đỉnh $i$.

Bài 5: Chứng minh Theorem 3.