Thuật toán ghép cặp của Edmonds

Thuật toán ghép cặp của Edmonds (còn gọi là thuật toán bông hoa) là một thuật toán trong lý thuyết đồ thị để tìm cặp ghép cực đại trong đồ thị. Thuật toán được tìm ra bởi Jack Edmonds năm 1961, và xuất bản năm 1965. Cho trước một đồ thị vô hướng G = (V, E), thuật toán tìm ra cặp ghép M sao cho mỗi đỉnh trong V kề với tối đa một cạnh trong M và |M| là lớn nhất có thể. Cặp ghép được xây dựng bằng cách khởi đầu từ cặp ghép rỗng và tăng dần lên bằng các đường tăng. Không như cặp ghép cho đồ thị hai phía, ý tưởng mới quan trọng nhất ở đây là có thể thu gọn một chu trình lẻ (bông hoa) thành một đỉnh, và việc tìm kiếm được thực hiện trên đồ thị đã thu gọn.

Thuật toán này là chứng minh đầu tiên cho việc có thể tìm cặp ghép cực đại trong thời gian đa thức. Một đóng góp quan trọng nữa là nó giúp mô tả đa diện quy hoạch tuyến tính của bài toán cặp ghép, từ đó xây dựng thuật toán tìm cặp ghép trọng số nhỏ nhất. Theo Alexander Schrijver, một điểm nổi bật nữa là đa diện này là đa diện đầu tiên được chứng minh là nguyên "không suy ra trực tiếp từ đơn môđula hoàn toàn, và mô tả của nó là một bước đột phá trong tổ hợp đa diện."

Đường tăng

Xét đồ thị G = (V, E) và cặp ghép M của G. Đỉnh v là tự do, nếu không có cạnh nào của M kề với v. Một đường trong G là một đường luân phiên, nếu các cạnh của nó luân phiên nhau không nằm trong M và nằm trong M (hoặc trong M và không trong M). Một đường tăng P là một đường luân phiên bắt đầu và kết thúc ở hai đỉnh tự do. Một phép tăng cặp ghép dọc theo đường tăng P là việc thay M bằng cặp ghép $M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)$.

Có thể chứng minh cặp ghép M là cực đại khi và chỉ khi không tồn tại đường tăng cho M trong G. Do đó, hoặc một cặp ghép là cực đại, hoặc tồn tại đường tăng cho nó. Vì vậy, xuất phát từ một cặp ghép ban đầu (có thể rỗng), có thể tìm cặp ghép cực đại bằng cách tăng cặp ghép dọc theo đường tăng chừng nào còn tồn tại đường tăng, và trả về cặp ghép cuối cùng khi không tồn tại đường tăng nào. Có thể tóm tắt thuật toán như sau:

     Dữ liệu vào:  Đồ thị G, cặp ghép ban đầu M trên G
     Dữ liệu ra: cặp ghép cực đại M* trên G
1    function tìm_cặp_ghép_cực_đại(G, M): M*
2        P ← tìm_đường_tăng(G, M)
3        if P khác rỗng
4            return tìm_cặp_ghép_cực_đại(G, tăng M dọc theo P)
5        else
6            return M

Một điểm chưa rõ trong mô tả trên là cách tìm đường tăng một cách hiệu quả. Việc tìm đường tăng sẽ sử dụng khái niệm bông hoa và thu gọn hoa.

Bông hoa và thu gọn hoa

Xét đồ thị G = (V, E) và cặp ghép M của G. Một bông hoa B là một chu trình trong G gồm 2k + 1 cạnh trong đó đúng k cạnh nằm trong M, và có một đỉnh v của chu trình (đế hoa) sao cho tồn tại một đường luân phiên độ dài chẵn (cuống hoa) từ v đến một đỉnh tự do w.

Định nghĩa đồ thị thu gọn G’ là đồ thị thu được từ G bằng cách thu gọn toàn bộ B vào đỉnh đế hoa, và định nghĩa cặp ghép thu gọn M’ là cặp ghép trong G’ tương ứng với M.

Có thể chứng minh rằng G’ có đường tăng cho M’ khi và chỉ khi G có đường tăng cho M và mỗi đường tăng P’ cho M’ trong G’ có thể được nâng lên thành một đường tăng cho M trong G bằng cách đảo ngược thao tác thu gọn B sao cho nếu P’ đi qua đỉnh đế hoa v_B thì mở rộng nó bằng một đường tương ứng trong B. Cụ thể hơn:

• nếu P’ đi qua hai cạnh u → v_B → w trong G’, thì mở rộng đoạn đường này thành u → (u’ →... → w’) → w trong G, trong đó u’ và w’ là hai đỉnh của hoa và trong hai nửa của B đi từ u’ đến w’, chọn nửa duy trì tính luân phiên của đường đi.

Như vậy có thể thu gọn các bông hoa và việc tìm đường tăng có thể được thực hiện trên đồ thị thu gọn. Thao tác này là ý tưởng chủ đạo của thuật toán Edmonds.

Tìm đường tăng

Việc tìm đường tăng sử dụng một cấu trúc dữ liệu hỗ trợ để lưu trữ một rừng F trong đó mỗi cây ứng với một phần của đồ thị G mà thuật toán đã tìm ra đường luân phiên từ đỉnh gốc của cây tới các đỉnh còn lại trong cây. Rừng F giống như rừng được dùng trong việc tìm cặp ghép trên đồ thị hai phía (ngoại trừ việc thu gọn bông hoa).

Thuật toán gán nhãn cho các đỉnh v của đồ thị. Nhãn gồm hai phần: đỉnh gốc của cây chứa v, và tính chẵn lẻ của độ dài đường luân phiên từ gốc của cây chứa v đến v.

Thuật toán lần lượt xem xét các đỉnh v và cạnh e của G và thay đổiF một cách thích hợp. Nếu v nằm trong một cây T trong rừng F, đặt gốc(v) là đỉnh gốc của T. Nếu cả u và v nằm trong cùng một cây T trong F, đặt khoảng_cách(u,v) là chiều dài đường đi duy nhất từ u đến v trên cây T.

   Dữ liệu vào: Đồ thị G, cặp ghép M trên G
   Dữ liệu ra: đường tăng P trên G hoặc thông báo không tồn tại đường tăng
01 function tìm_đường_tăng(G, M): P
02    F ← rừng rỗng
03    gán nhãn chưa thăm mọi đỉnh và mọi cạnh của G, gán nhãn đã thăm cho mọi cạnh trong M
05    for each đỉnh tự do v
06        tạo một cây chỉ gồm đúng một đỉnh { v } và thêm nó vào F
08    while tồn tại đỉnh v chưa được thăm trong F với khoảng_cách(v, gốc(v)) là chẵn
09        while tồn tại cạnh chưa thăm e = { v, w }
10            if w không nằm trong F
                  // Cập nhật F.
11                x ← đỉnh ghép với w trong M
12                thêm cạnh { v, w } và { w, x } vào cây của v
13            else
14            if khoảng_cách(w, gốc(w)) là lẻ
15                không làm gì
16            else
17            if gốc(v) ≠ gốc(w)
                   // trả về đường tăng trong F $\cup$ { e }.
18                P ← đường (gốc(v) →... → v) → (w →... → gốc(w))
19                return P
20            else
                  // thu gọn bông hoa trong G và tìm đường tăng trong đồ thị thu gọn.
21                B ← bông hoa tạo bởi e và các cạnh trên đường v → w trong T
22                G’, M’ ← thu gọn G và M bằng B
23                P’ ← tìm_đường_tăng(G’, M’)
24                P ← nâng P’ lên đường tăng trong G
25                return P
26            end if
27            đánh dấu đã thăm e
28        end while
29        đánh dấu đã thăm v
30    end while
31    return không tồn tại đường tăng
32 end function