Định lý luồng cực đại lát cắt cực tiểu

Định lý luồng cực đại lát cắt cực tiểu là một phát biểu trong ngành lý thuyết tối ưu hóa về các luồng cực đại trong các mạng vận tải (flow network). Định lý phát biểu rằng:

Lượng cực đại của một luồng bằng khả năng thông qua của một lát cắt tối thiểu.

Định nghĩa

Giả sử ${\displaystyle G(V,E)}$ là một đồ thị có hướng hữu hạn và mỗi cung ${\displaystyle (u,v)}$ có một khả năng thông qua ${\displaystyle c(u,v)}$ (một giá trị thực không âm). Ngoài ra, giả sử có hai đỉnh, đỉnh phát ${\displaystyle s}$ và đỉnh thu ${\displaystyle t}$, đã được xác định.

Một lát cắt là một cách chia các nút mạng thành hai tập ${\displaystyle S}$ và ${\displaystyle T}$, sao cho ${\displaystyle s}$ thuộc tập ${\displaystyle S}$ và ${\displaystyle t}$ thuộc ${\displaystyle T}$. Do đó, trong một đồ thị có ${\displaystyle 2^{|V|-2}\,}$ lát cắt có thể.

Khả năng thông qua của một lát cắt ${\displaystyle (S,T)}$ là

${\displaystyle c(S,T)=\sum _{u\in S,v\in T|(u,v)\in E}c(u,v)}$,

Đó là tổng của các khả năng thông qua của tất cả các cung đi qua lát cắt, từ vùng ${\displaystyle S}$ tới vùng ${\displaystyle T}$.

Ba điều kiện sau là tương đương:

1. ${\displaystyle f}$ là một luồng cực đại trong đồ thị ${\displaystyle G}$
2. Mạng còn dư (residual network) ${\displaystyle G_{f}}$ không chứa đường tăng (augmenting path).
3. ${\displaystyle |f|=c(S,T)}$ với lát cắt ${\displaystyle (S,T)}$ nào đó.

Phác thảo chứng minh: Nếu có một đường tăng, ta có thể gửi luồng theo đó và thu được một luồng lớn hơn, do đó nó không thể là luồng cực đại, và ngược lại. Nếu không có đường tăng nào, ta chia đồ thị thành ${\displaystyle S}$ gồm các nút tới được từ ${\displaystyle s}$ trong mạng còn dư, và ${\displaystyle T}$ gồm các nút không tới được. Khi đó ${\displaystyle c(S,T)}$ phải bằng 0. Nếu không, tồn tại một cung ${\displaystyle (u,v)}$ với ${\displaystyle c(u,v)>0}$, nhưng khi đó, từ ${\displaystyle s}$ lại đến được ${\displaystyle v}$ nên ${\displaystyle v}$ không thể nằm trong ${\displaystyle T}$.

Ví dụ

Một mạng với luồng cực đại và ba lát cắt cực tiểu

Hình bên phải là một mạng với các nút ${\displaystyle V=\{s,o,p,q,r,t\}}$, và luồng cực đại là một luồng tổng từ nút phát ${\displaystyle s}$ tới nút thu ${\displaystyle t}$ có giá trị bằng 5. (Đây thực ra là luồng cực đại duy nhất ta có thể tìm thấy trong mạng này.)

Có ba lát cắt cực tiểu trong mạng. Đối với lát cắt ${\displaystyle S=\{s,p\},T=\{o,q,r,t\}}$, khả năng thông qua lát cắt là ${\displaystyle c(s,o)+c(p,r)=3+2=5}$. Với ${\displaystyle S=\{s,o,p\},T=\{q,r,t\}}$ nó là ${\displaystyle c(o,q)+c(p,r)=3+2=5}$. Và với ${\displaystyle S=\{s,o,p,q,r\},T=\{t\}}$ là ${\displaystyle c(q,t)+c(r,t)=2+3=5}$.

Lưu ý rằng ${\displaystyle S=\{s,o,p,r\},T=\{q,t\}}$ không phải là một lát cắt cực tiểu, tuy trong luồng đã cho cả ${\displaystyle (o,q)}$ và ${\displaystyle (r,t)}$ đều đầy. Đó là do trong mạng còn dư ${\displaystyle G_{f}}$ có một cung (r,q) với khả năng thông qua ${\displaystyle c_{f}(r,q)=c(r,q)-f(r,q)=0-(-1)=1}$.

Lịch sử

Định lý này được chứng minh bởi P. Elias, A. Feinstein, và C.E. Shannon năm 1956, và cũng năm đó, nó được chứng minh một cách độc lập bởi L.R. Ford, Jr. và D.R. Fulkerson. Tìm các luồng cực đại là một dạng bài toán quy hoạch tuyến tính đặc biệt, và định lý luồng cực đại lát cắt cực tiểu có thể được coi là một trường hợp đặc biệt của định lý đôi (duality theorem) cho quy hoạch tuyến tính.

Xem thêm

• Thuật toán Ford-Fulkerson

Liên kết ngoài

Tiếng Việt:

• Bài toán luồng cực đại trên mạng Lưu trữ 2008-05-07 tại Wayback Machine
• Bài toán luồng cực đại trên mạng - Các thuật toán đa thức Lưu trữ 2006-08-19 tại Wayback Machine

Tiếng Anh:

• A review of current literature on computing maximum flows Lưu trữ 2008-02-12 tại Wayback Machine
• Max-Flow Min-Cut Animation Lưu trữ 2006-05-16 tại Wayback Machine
• Max-Flow Problem: Ford-Fulkerson Algorithm Lưu trữ 2008-01-11 tại Wayback Machine

Tham khảo

• P. Elias, A. Feinstein, and C. E. Shannon. Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, 117–119, 1956.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 26: Maximum Flow, pp. 643–700.