1483310
Thuật toán ghép cặp của Edmonds
https://vi.wikipedia.org/wiki?curid=1483310
Title: Thuật toán ghép cặp của Edmonds
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".