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 formula _ 1 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 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 thì mở_rộng nó bằng một đường tương_ứng trong B Cụ_thể hơn BULLET nếu P đi qua hai cạnh u v 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
Thuật_toán ghép cặp của Edmonds