Thực đơn
Thuật_toán_Ford–Fulkerson Thuật toánCho một đồ thị G ( V , E ) {\displaystyle G(V,E)} , với các khả năng thông qua c ( u , v ) {\displaystyle c(u,v)} và luồng f ( u , v ) = 0 {\displaystyle f(u,v)=0} trên các cung từ u {\displaystyle u} đến v {\displaystyle v} , ta muốn tìm luồng cực đại từ đầu nguồn s {\displaystyle s} đến điểm thoát t {\displaystyle t} . Sau mỗi bước, các điều kiện sau đây được duy trì:
Điều này có nghĩa là một luồng đi qua một mạng là một luồng hợp lệ sau mỗi vòng của thuật toán. Chúng ta định nghĩa mạng còn dư G f ( V , E f ) {\displaystyle G_{f}(V,E_{f})} là mạng với sức chứa c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} và luồng bằng không. Chú ý rằng không chắc chắn là E = E f {\displaystyle E=E_{f}} , bởi vì việc gửi luồng theo cung u , v {\displaystyle u,v} có thể làm ngắt u , v {\displaystyle u,v} (làm nó bão hòa), nhưng lại mở một cung mới v , u {\displaystyle v,u} trong mạng còn dư.
Đầu vào: Đồ thị G với khả năng thông qua c, một nút nguồn s, và một nút thoát tKết quả: Luồng f sao cho f là cực đại từ s đến tCó thể tìm đường đi trong G f ( V , E f ) {\displaystyle G_{f}(V,E_{f})} bằng các phương pháp chẳng hạn như tìm kiếm theo chiều rộng (breadth-first-search) hoặc tìm kiếm theo chiều sâu (depth-first-search). Nếu sử dụng cách thứ nhất, thuật toán sẽ được gọi là Edmonds-Karp.
Thực đơn
Thuật_toán_Ford–Fulkerson Thuật toánLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ thiên văn học Thuật ngữ lý thuyết đồ thị Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật toán Kruskal Thuật ngữ ngữ âm họcTài liệu tham khảo
WikiPedia: Thuật_toán_Ford–Fulkerson http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/ma... http://laptrinh.sourceforge.net/hoctap/maxflow/ https://web.archive.org/web/20060717041622/http://...