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 (lý thuyết đồ thị)|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<sub>B</sub>* 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<sub>B</sub> → 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 đổi*F* 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**

## Tham khảo