1476412
Thuật toán Dinitz
https://vi.wikipedia.org/wiki?curid=1476412
Title: Thuật toán Dinitz
Trong mạng lưới xây dựng từ bài toán ghép cặp trên đồ thị hai phía, số lần tìm luồng ngăn chặn là formula_57, nên thời gian chạy là không quá formula_58. Thuật toán này còn được biết đến là thuật toán Hopcroft–Karp. Tổng quát hơn, chặn trên cho thời gian chạy này đúng cho mọi "mạng đơn vị" — mạng trong đó mỗi đỉnh, ngoại trừ đỉnh phát và đỉnh thu, hoặc có đúng một cung vào với khả năng thông qua bằng một, hoặc đúng một cung ra với khả năng thông qua bằng một và tất cả các cung khác có khả năng thông qua là số nguyên tùy ý.
Ví dụ.
Dưới đây là một ví dụ thực hiện thuật toán Dinitz. Trong đồ thị tầng formula_26, nhãn đỏ của các đỉnh là các giá trị formula_16. Các đường màu xanh tạo thành một luồng ngăn chặn.
Lịch sử.
Thuật toán Dinitz được xuất bản năm 1970 bởi nhà nghiên cứu khoa học máy tính người Nga (khi đó) Yefim (Chaim) A. Dinitz, nay là thành viên của khoa Khoa học Máy tính tại đại học Ben-Gurion (Israel), trước thuật toán Edmonds–Karp, xuất bản năm 1972 nhưng được phát hiện trước đó. Họ chứng minh một cách độc lập rằng trong thuật toán Ford–Fulkerson, nếu mỗi đường tăng luồng luôn là đường tăng ngắn nhất, chiều dài của đường tăng luồng là không giảm.