Đị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:

== Định nghĩa ==
Giả sử formula_1 là một đồ thị có hướng hữu hạn và mỗi cung formula_2 có một khả năng thông qua formula_3 (một giá trị thực không âm). Ngoài ra, giả sử có hai đỉnh, đỉnh phát formula_4 và đỉnh thu formula_5, đã đượ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 formula_6 và formula_7, sao cho formula_4 thuộc tập formula_6 và formula_5 thuộc formula_7. Do đó, trong một đồ thị có formula_12 lát cắt có thể.

Khả năng thông qua của một lát cắt formula_13 là

Đó 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 formula_6 tới vùng formula_7.

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

1. formula_17 là một luồng cực đại trong đồ thị formula_18
2. Mạng còn dư ("residual network") formula_19 không chứa đường tăng ("augmenting path").
3. formula_20 với lát cắt formula_13 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 formula_6 gồm các nút tới được từ formula_4 trong mạng còn dư, và formula_7 gồm các nút không tới được. Khi đó formula_25 phải bằng 0. Nếu không, tồn tại một cung formula_2 với formula_27, nhưng khi đó, từ formula_4 lại đến được formula_29 nên formula_29 không thể nằm trong formula_7.

== Ví dụ ==
Hình bên phải là một mạng với các nút formula_32, và luồng cực đại là một luồng tổng từ nút phát formula_4 tới nút thu formula_5 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 formula_35, khả năng thông qua lát cắt là formula_36. Với formula_37 nó là formula_38. Và với formula_39 là formula_40.

Lưu ý rằng formula_41 không phải là một lát cắt cực tiểu, tuy trong luồng đã cho cả formula_42 và formula_43 đều đầy. Đó là do trong mạng còn dư formula_19 có một cung (r,q) với khả năng thông qua formula_45.

== 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
- Bài toán luồng cực đại trên mạng - Các thuật toán đa thức

Tiếng Anh:
- A review of current literature on computing maximum flows
- Max-Flow Min-Cut Animation
- Max-Flow Problem: Ford-Fulkerson Algorithm

== 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.