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 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 "vB" thì mở rộng nó bằng một đường tương ứng trong "B". Cụ thể hơn:
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