1749906
Luồng cực đại
https://vi.wikipedia.org/wiki?curid=1749906
Title: Luồng cực đại
"Dễ dàng kiểm tra được rằng f' được xây dựng như trên là luồng trong mạng và val(f')= val(f) + d. Ta sẽ gọi thủ tục biến đổi luồng vừa nêu là tăng luồng dọc theo đường P."
"Sau biến đổi ta có luồng mới mang giá trị 9". val(f,) = 4 + 3 - 3 + 2 + 3 = 9
Thuật toán Ford-Fulkerson.
Đến Thuật toán
Luồng cực đại với khả năng thông qua các cung và các đỉnh:.
Giả sử trong đồ thị G = (V,E), ngoài khả năng thông qua của các cung c(u,v), ở mỗi đỉnh còn có khả năng thông qua của đỉnh là d(v), và đòi hỏi tổng luồng đi vào đỉnh v không còn vượt quá d(v), tức là ∑ f (w, v) &lt; d(v), với w ∈ V
Cần phải tìm luồng cực đại giữa s và t trong mạng như vậy.
Xây dựng một mạng G’ sao cho: mỗi đỉnh v của G tương ứng với hai đỉnh (v+ v-) trong G’, mỗi cung (u,v) trong G ứng với cung (u,v+) trong G’ mỗi cung (v,w) trong G ứng với cung (v- w+) trong G’. Ngoài ra, mỗi cung (v+ v-) trong G’ có khả năng thông qua là d(v), tức là bằng khả năng thông qua của đỉnh v trong G.
Giải quyết bài toán
Từ mạng G = (V,E) khả năng thông qua các cung và các đỉnh. Ta sẽ giải quyết 
theo hai bước sau: 
 * Xác định mạng G’. 
 * Tìm luồng cực đại trong mạng G’. Bắt đầu từ luồng 0 với khả năng thông qua cung. 
Ma trận biểu diễn đồ thị của bài toán luồng cực đại
1 Biểu diễn mạng G với khả năng thông qua các cung và đỉnh
Giả sử mạng G = (V,E), |V| = n. Ta có thể biểu diễn bởi ma trận trọng số A cấp n x n như sau:
Trong đó: di là khả năng thông qua đỉnh i; C[i,j] khả năng thông qua cung [i,j].
2 Biểu diễn mạng G’ tương ứng với mạng G 