perfect-matching

You are currently browsing articles tagged perfect-matching.

Bài này mở đầu cho một loạt bài về lý thuyết cặp ghép (matching) trong đồ thị. Mình khuyến khích bạn đọc xem lại một số khái niệm về đồ thị tại đây; chúng ta sẽ không nhắc lại những khái niệm đồ thị cơ bản trong bài này nữa.

Trong bài viết về luồng trong mạng, mình đã giới thiệu một phương pháp tìm cặp ghép trong đồ thị hai phía sử dụng phương pháp luồng cực đại. Trong chuỗi bài tiếp theo, mình viết về cặp ghép như một lý thuyết riêng. Lý thuyết cặp ghép là một lý thuyết rất đẹp trong tổ hợp nói chung và đồ thị nói riêng. Có nguyên một cuốn sách dầy [1] chỉ để giới thiệu về lý thuyết này. Chuỗi bài này mình hi vọng truyền tải được cái đẹp của lý thuyết này đến cho bạn đọc.

Khái niệm

Một cặp ghép (matching) của một đồ thị $G(V,E)$ là một tập cạnh $M$ sao cho không có hai cạnh nào của $M$ có chung một đầu mút. Xem hình minh họa trong Figure 1(a). $M$ được gọi là tối đại (maximal) nếu ta không thể thêm cạnh nào của đồ thị vào $M$ sao cho tập cạnh sau khi thêm vẫn là một cặp ghép. $M$ được gọi là cực đại (maximum) nếu là cặp ghép có số cạnh nhiều nhất.

Chú ý: Cặp ghép cực đại cũng là cặp ghép tối đại nhưng điều ngược lại chưa chắc đã đúng. Xem minh họa trong Figure 1(b).

matching-example
Figure 1: (a) Các cạnh màu đỏ thuộc một cặp ghép. (b) Một cặp ghép tối đại (maximal matching) nhưng không phải cực đại (maximum matching).

Một đỉnh của đồ thị được gọi là đã ghép (matched) nếu nó là đầu mút của một cạnh trong $M$. Ngược lại, ta gọi đỉnh đó là đỉnh chưa ghép (unmatched). Một cặp ghép được gọi là hoàn hảo (perfect matching) nếu mọi đỉnh của đồ thị đều đã ghép. Dễ thấy một cặp ghép hoàn hảo là một cặp ghép cực đại (nhưng điều ngược lại chưa chắc đã đúng).

Một đường pha (alternating path) của cặp ghép $M$ là một đường đi trên đồ thị sao cho với bất kì hai cạnh liên tục nào trên đường đi, đúng một trong hai cạnh thuộc $M$. Một chu trình pha (alternating cycle) là một đường pha mà điểm đầu và điểm cuối giống nhau.

Ví dụ: Trong Figure 1(b), đường $P = \{1,2,3,5,4\}$ là một đường pha. Đường pha có thể bắt đầu hoặc/và kết thúc bằng một đỉnh thuộc cặp ghép hoặc không thuộc cặp ghép (xem Figure 3(a)). Như vậy, đường $Q = \{2,3,5,4\}$ cũng là đường pha. Chu trình $C = \{2,3,4,5,2\}$ (Figure 1(b)) là một chu trình pha.

Tiếp theo ta tìm hiểu khái niệm hiệu đối xứng (symmetric difference) giữa hai tập hợp. Đây là khái niệm rất quan trọng trong chứng minh các tính chất của cặp ghép cực đại.

Hiệu đối xứng(symmetric difference): Cho hai tập $A$ và $B$. Hiệu đối xứng của $A$ và $B$, kí hiệu $A \oplus B$, là một tập hợp thỏa mãn:

$A \oplus B = (A\setminus B) \cup (B\setminus A) \qquad (1)$

 
Figure 2 dưới đây minh họa biểu đồ Venn của hiệu đối xứng.
symmetric-diff
Figure 2: Hiệu đối xứng $A \oplus B$ chính là phần tô màu đỏ. Hình được sửa đổi từ wikipedia.

Tại sao chúng ta phải quan tâm đến hiệu đối xứng?

Theorem 1: Nếu $M$ là một cặp ghép của $G(V,E)$ và $P$ là một đường pha, trong đó mỗi đỉnh của $P$ hoặc là đỉnh chưa ghép, hoặc là đỉnh đã ghép bới một cạnh của $M$ thuộc $P$, thì $M \oplus P$ cũng là một cặp ghép của $G(V,E)$.

 
Chứng minh Theorem 1 không khó và mình coi như bài tập cho bạn đọc (Bài tập 1).

Theorem 1 cho chúng ta một cách để tìm cặp ghép mới từ cặp ghép hiện tại sử dụng đường pha. Vậy khi nào thì $M\oplus P$ có nhiều cạnh hơn $M$, i.e, $|M \oplus P|$ > $|M|$?

agumenting
Figure 3: Các cạnh màu đỏ là các cạnh thuộc cặp ghép. Hình (a) minh họa ba loại đường pha khác nhau. Hình (b) minh họa các cạnh của cặp ghép sau khi lấy hiệu đối xứng $M \oplus P$. Ta thấy chỉ có trường hợp đường pha ở giữa có $|M \oplus P|$ > $|M|$. Ta gọi đường ở giữa là một đường tăng.

Theo hình minh họa Figure 3(b) thì khi $P$ bắt đầu và kết thúc bằng một đỉnh chưa ghép thì $|M \oplus P|$ > $|M|$. Từ đó ta có khái niệm đường tăng (agumenting path).

Đường tăng (augmenting path): Một đường pha được gọi là một đường tăng nếu nó có điểm đầu và điểm cuối là hai đỉnh chưa ghép.

 

Theo các nhận xét vừa thảo luận, ta có:

Lemma 1: Nếu $M$ là một cặp ghép của $G(V,E)$ và $P$ là một đường tăng, ta có :

$|M \oplus P|$ > $|M| \qquad (2)$

 

Tìm cặp ghép cực đại trong đồ thị

Lemma 1 cho chúng ta một giải thuật khá đơn giản sau để tìm cặp ghép.

FindMaximumMatching($G(V,E)$):
    $M \leftarrow \emptyset$
    while there is an augmenting path $P$ in $G$
        $M \leftarrow M\oplus P$
    return $M$

 

Có hai vấn đề cần phải làm rõ về giải thuật FindMaximumMatching:

  1. Làm thế nào để tìm đường tăng $P$ một cách hiệu quả?
  2. Đầu ra của thuật toán có phải là cặp ghép cực đại hay không?

Câu hỏi đầu tiên thực sự là một câu hỏi không tầm thường. Hầu hết các công trình nghiên cứu tập trung vào làm thế nào để tìm được đường tăng một cách hiệu quả. Chuỗi bài về cặp ghép của mình cũng chỉ tập trung vào thảo luận một số câu trả lời cho câu hỏi này mà thôi. Ta tạm gác câu hỏi này lại và tìm câu trả lời cho câu hỏi 2 ở đây.

Theorem 2: Đầu ra của thuật toán FindMaximumMatching là một cặp ghép cực đại.

 
Trước khi chứng minh Theorem 2, ta có nhận xét sau:

Observation 1: Gọi $M_1, M_2$ là hai cặp ghép của đồ thị $G(V,E)$. Đồ thị con $H(V, M_1\oplus M_2)$ sẽ bao gồm: (1) các đỉnh cô lập (isolated vertices), i.e, các đỉnh không kề với cạnh nào cả, (2) các đường pha và (3) các chu trình pha.

 
Chứng minh: Xem minh họa trong Figure 4. Do $M_1, M_2$ là các cặp ghép, đỉnh của đồ thị con (subgraph) $H(V, M_1\oplus M_2)$ có bậc (trong $H$) không quá 2.


matching-sym-diff
Figure 4: (a) Một cặp ghép (chưa cực đại) $M$ gồm các cạnh màu đỏ và một cặp ghép cực đại $M'$ gồm các cạnh màu xanh. (b) Đồ thị $H(V, M_1\oplus M_2)$.

Chứng minh Theorem 2: Gọi $M$ là tập cạnh trả về bởi FindMaximumMatching. Theo chi tiết thuật toán, không tồn tại đường tăng của $M$ trong đồ thị.

Gọi $M'$ là một cặp ghép cực đại. Xét đồ thị con $H(V, M \oplus M')$. Theo Observation 1, có 3 loại đỉnh trong $H$: các đỉnh cô lập, các đỉnh thuộc các đường pha và các đỉnh thuộc các chu trình pha.

Không khó để thấy các cạnh thuộc $M \cap M'$ khi lấy hiệu đối xứng $M\oplus M'$ sẽ tạo ra các đỉnh cô lập. Với mỗi chu trình pha $C$, ta có $M \cap C = M \cap C'$. Do đó, nếu $|M| < |M'|$ thì sẽ tồn tại ít nhất một đường pha $P$ mà ở đó $|P\cap M| < |P \cap M'|$. Do đó, $P$ có đỉnh bắt đầu và kết thúc ghép bởi $M'$ nhưng chưa được ghép bởi $M$. Do đó, $P$ là một đường tăng của $M$, trái với giải thiết ban đầu. Như vậy, $M$ cũng phải là cặp ghép cực đại.


Tìm cặp ghép cực đại trong đồ thị hai phía

Đồ thị hai phía có cấu trúc đặc biệt khiến bài toán tìm cặp ghép cực đại trở nên dễ dàng hơn nhưng cũng không kém phần thú vị. Gọi $G(A\cup B, E)$ là đồ thị với hai tập đỉnh riêng biệt $A$ và $B$, trong đó các cạnh $E$ của đồ thị có đúng một đầu mút thuộc $A$ và đầu mút kia thuộc $B$. Ta gọi $G$ là một đồ thị hai phía (bipartite graph).

Từ định nghĩa ta dễ dàng suy ra được đồ thị hai phía không có chu trình có số cạnh lẻ (odd cycles). Điều ngược lại cũng đúng. Đồ thị không có chu trình lẻ là đồ thị hai phía. Do đó, để kiểm tra xem một đồ thị có phải là hai phía hay không, ta chỉ cần kiểm tra xem nó có chu trình lẻ hay không; bài toán này có thể giải quyết bằng phương pháp duyệt theo chiều rộng BFS. Chi tiết coi như bài tập cho bạn đọc. Đồ thị trong Figure 1(a) chính là một đồ thị hai phía. Theo bạn thì $A$ và $B$ sẽ gồm những đỉnh nào trong Figure 1(a)?

Tìm đường tăng trong đồ thị hai phía

Gọi $M$ là một cặp ghép (chưa cực đại) của $G(A\cup B, E)$ và $P$ là một đường tăng của $M$. Theo định nghĩa đường tăng, $P$ phải có số cạnh lẻ. Do đó một điểm đầu của $P$ phải thuộc $A$ và đầu kia thuộc $B$. Như vậy, tìm $P$ cũng đồng nghĩa với tìm một đường pha bắt đầu từ một đỉnh chưa ghép của $A$ và kết thúc bằng một đỉnh chưa ghép của $B$.

Gọi $G(A\cup B, \vec{E})$ là đồ thị có hướng thu được bằng cách định hướng mỗi cạnh $e$ như sau: nếu $e \not \in M$, ta định hướng nó từ $A$ sang $B$. Ngược lại, ta định hướng $e$ từ $B$ sang $A$. Xem minh họa trong Figure 5. Ta có nhận xét:

Observation 2: $M$ có đường tăng khi và chỉ khi tồn tại một đường đi có hướng từ một đỉnh chưa ghép của $A$ tới một đỉnh chưa ghép của $B$ trong $G(A\cup B, \vec{E})$.

 

edge-orientation
Figure 5: (a) Một cặp ghép trong đồ thị hai phía và (b) đồ thị định hướng $G(A\cup B, \vec{E})$.

Observation 2 cho phép chúng ta quy bài toán tìm đường tăng về bài toán tìm đường trong đồ thị có hướng; bài toán này về mặt trực quan có vẻ dễ hơn nhiều. Một phương pháp đơn giản nhất để tìm đường là lần lượt sử dụng BFS (hoặc DFS), bắt đầu từ một đỉnh chưa ghép của $A$, tìm đường tới một đỉnh chưa ghép của $B$. Phương pháp cho chúng ta thuật toán với thời gian $O(mn)$ để tìm được một đường tăng ($m = |E|$ và n = $|A \cup B|$). Tuy nhiên, ta có thể giảm thời gian xuống còn $O(m+n)$ bằng cách thêm vào 2 đỉnh ảo $s$ và $t$. Thêm các cạnh có hướng từ $s$ tới mọi đỉnh chưa ghép của $A$ và cạnh có hướng từ mọi đỉnh chưa ghép của $B$ tới $t$. Gọi $G(A\cup B\cup {s,t}, \vec{E})$ là đồ thị thu được sau khi thêm $s,t$. Ta có:

Lemma 2: $M$ có đường tăng khi và chỉ khi tồn tại một đường đi (có hướng) từ $s$ tới $t$ trong $G(A\cup B\cup \{s,t\}, \vec{E})$.

 

Theo Lemma 2, bài toán tìm đường tăng có thể giải được bằng BFS/DFS với thời gian $O(m+n)$. Do đó ta có:

Theorem 3: Ta có thể tìm cặp ghép cực đại trong đồ thị hai phía trong thời gian $O(mn)$.

 
Trong bài tiếp theo, ta tìm hiểu thuật toán Hopcroft-Karp tìm cặp ghép cực đại trong đồ thị hai phía với thời gian $O(m\sqrt{n})$.

Cài đặt

Tuy mô tả ở trên cho chúng ta thuật toán $O(mn)$, nhưng ta sẽ không cài đặt theo đúng mô tả đó. Nghĩa là ta sẽ không định hướng cạnh, rồi thêm đỉnh ảo, cuối cùng là tìm đường. Mô tả trên ta chỉ coi như một cách giải thích thuật toán mà thôi.

Trước hết, ta biểu diễn đồ thị hai phía bằng danh sách kề. Với mỗi đỉnh $i \in A$, ta lưu một danh sách $N[i]$ là các hàng xóm của nó trong $B$. Trong cài đặt thuật toán, ta không cần thiết phải lưu danh sách các hàng xóm của $B$, vì theo phân tích ở trên, trong đồ thị có hướng mà ta tạo ra, mỗi đỉnh của $B$ có bậc lui (out degree) không quá $1$, và được định nghĩa dựa trên cặp ghép $M$.

Để biểu diễn cặp ghép, ta sẽ dùng một mảng $M[1,2,\ldots, |B|]$ để biểu diễn đỉnh được ghép đôi trong $A$ với mỗi đỉnh trong $B$. Cụ thể, $M[j] = -1$ nếu đỉnh $j \in B$ là một đỉnh chưa ghép, và $M[j] = i$ nếu $j \in B$ được ghép với $i \in A$. Trong giả mã dưới đây, ta sử dụng DFS để tìm đường.

BipartiteMaximumMatching($G(A \cup B, E)$):
    $M \leftarrow \emptyset$
    repeat
        mark every vertex of $G$ unvisited
        for each $u \in A$
            if $u$ is univisited and unmatched
                Augmenting $(G, u, M)$
    until no augmenting path exists
    return $M$

 

Augmenting($G(A \cup B, E), u, M$):
    mark $u$ visited
    for each $v \in N[u]$             $\ll v \in B \gg$
        if $v$ is unmatched             $\ll$ found an augmenting path $\gg$
            $M[v] \leftarrow u$             $\ll$ augmenting $\gg$
            return True
        if $v$ is unvisited
            mark $v$ visited
            if $M[v]$ unvisited and Augmenting ($G, M[v], M$)
                $M[v] \leftarrow u$
                return True
    return False

 

Code C:
to-do

Trong giả mã trên, thủ tục Augmenting luôn được gọi trên đệ quy trên đỉnh thuộc $A$. Ta không bao giờ gọi đệ quy thủ tục này trên đỉnh thuộc $B$. Thủ tục này sau khi tìm được đường tăng (augmenting path), ta sẽ thực hiện tăng ngay sau đó (lấy hiệu đối xứng dọc theo đường tăng).

Tham khảo

[1] L. Lovász and M. D. Plummer. Matching Theory. Vol. 367. American Mathematical Soc., 2009.
[2] U. Zwick. Maximum Matching in Bipartite and Non-bipartite Graphs. Lecture Note, 2009. Accessed 10-2017.

Bài tập

Bài tập 1: Chứng minh Theorem 1.

Bài tập 2: Chứng minh rằng một đồ thị là hai phía khi và chỉ khi nó không có chu trình lẻ. Thiết kế thuật toán kiểm tra xem một đồ thị cho trước có phải là hai phía hay không trong thời gian $O(n+m)$.

Bài tập 3: Chứng minh Observation 2.

Bài tập 4: Trong phần mô tả ngay sau Observation 2, ta có nói đến thuật toán tìm đường tăng trong thời gian $O(mn)$ bằng cách thực hiện DFS/BFS từ mỗi đỉnh chưa ghép của $A$. Trong thuật toán BipartiteMaximumMatching (vòng lặp repeat-until), về cơ bản ta cũng thực hiện DFS/BFS trên mỗi đỉnh chưa ghép cho đến khi nào tìm được đường tăng. Tuy nhiên, ta chỉ phải trả thời gian $O(m+n)$. Hai phương pháp này khác nhau ở chỗ nào?

Bài tập 5: Chứng minh rằng một cặp ghép tối đại bất kì của đồ thị có kích thước ít nhất một nửa cặp ghép cực đại của đồ thị đó.

Tags: , , , ,

« Older entries