1749906
Luồng cực đại
https://vi.wikipedia.org/wiki?curid=1749906
Title: Luồng cực đại
Bổ đề 1. giá trị của mọi luồng f trong mạng luôn nhỏ hơn bằng khả năng thông qua lát cắt (X,X*) bất kỳ trong nó: val(f) £ c(X,X*).
Hệ quả 1. Giá trị luồng cực đại trong mạng không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng.
Giả sử f là một luồng trong mạng G = (V,E). Từ mạng G = (V,E) ta xây dựng đồ thị có trọng số trên cung Gf =(V,Ef), với tập cung Ef và trọng số trên các cung được xác định theo quy tắc sau:
 * Nếu e = (v,w) ∈ E với f(v,w) = 0, thì (v,w)∈ Ef với trọng số c(v,w);
 * Nếu e = (v,w) ∈ E với f(v,w) = c(v,w), thì (w,v)∈ Ef với trọng số f(v,w);
 * Nếu e = (v,w) ∈ E với 0 &lt;f(v,w) &lt; c(v,w), thì (v,w)∈ Ef với trọng số c(v,w) - f(v,w) và (w,v) ∈ Ef với trọng số f(v,w).
Các cung của Gf đồng thời cũng là cung của G được gọi là cung thuận, các cung còn lại gọi là cung nghịch. Đồ thị Gf được gọi là đồ thị tăng luồng.
"Ví dụ: Các số viết cạnh các cung của G ở hình 1 theo thứ tự là luồng trên cung và khả năng thông qua"
Đường tăng luồng.
Giả sử P = (s = v0,v1,v2,…,vk= t) là một đường đi từ s đến t trên đồ thị tăng luồng Gf. Gọi d là giá trị nhỏ nhất của các trọng số của các cung trên đường đi P. Xây dựng luồng f' trên mạng G theo quy tắc sau:
 f(u,v) + d, nếu (u,v) ∈ P là cung thuận
 f(u,v) = f(u,v) - d, nếu (u,v) ∈ P là cung nghịch
 f(u,v), nếu (u,v) không ∈ P 