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
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.