Luồng cực đại

Luồng cực đại là một trong những bài toán tối ưu trên đồ thị tìm được những ứng dụng rất rộng rãi trong cả thực tế cũng như trong lý thuyết tổ hợp. Bài toán được đề xuất vào đầu những năm 1950 và gắn liền với tên tuổi của 2 nhà toán học Mỹ Lester Randolph Ford và Delbert Ray Fulkerson.

Mạng
Mạng (network) là một đồ thị có hướng G = (V, E) trong đó:
:Có duy nhất một đỉnh s không có cung đi vào, được gọi là đỉnh phát (source)
:Có duy nhất một đỉnh t không có cung đi ra, được gọi là đỉnh thu (sink)
Mỗi cạnh e = (u, v) ∈ E được gán một số nguyên không âm c(e) = c[u, v] và gọi là khả năng thông qua của cung đó (capacity).
Ta quy ước nếu mạng không có cung (u, v) thì ta thêm vào cung (u, v) với khả năng thông qua c[u, v] bằng 0.
Với một mạng G = (V, E, c), ta ký hiệu:
W-(x) = {(u, v) ∈ E | u ∈ V}: tập các cung đi vào đỉnh v.

W+(x) = {(v, u) ∈ E | u ∈ V}: tập các cung đi ra khỏi đỉnh v.

Luồng trên mạng
Giả sử cho mạng G = (V, E). Ta gọi luồng f trong mạng là ánh xạ f: E → R+ gán cho mỗi cung e = (u, v) ∈ E một số thực không âm f(e) = f[u, v], thoả mãn các điều kiện sau:
ĐK 1 (Capacity Constraint): Luồng trên mỗi cung e ∈ E không vượt quá khả năng thông qua của nó: 0 ≤ f(e) ≤ c(e)
ĐK 2 (Flow Conversion): Điều kiện cân bằng luồng trên mỗi đỉnh của mạng: Tổng luồng trên các cung vào đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh v, nếu v ≠ s, t: t(W-(x)) = t(W+(x)), ∀x ≠ s, t

Tính chất của luồng

Với tập B ⊆ V, ký hiệu:

W-(B) = { (a, b) ∈ E | a ∉ B, b ∈ B } - tập cạnh từ ngoài B đi vào B.

W+(B) = { (a, b) ∈ E | a ∈ B, b ∉ B } - tập cạnh từ B đi ra khỏi B.

Khi đó nếu tập con các đỉnh B không chứa x0 và z thì: t (W-(B)) =t (W+(B)).Theo tính chất b) của luồng: ∑ t (W-(x)) =∑ t (W+(x)).

Cạnh kề với đỉnh x nếu có đỉnh đầu và đỉnh cuối đều nằm trong tập B thì nó sẽ có mặt ở cả hai vế củađẳng thức đúng một lần, do đó có thể giản ước.

Giá trị của luồng
Giá trị của một luồng được tính bằng tổng giá trị trên các cung đi ra từ đỉnh nguồn s, hoặc tổng giá trị trên các cung đi vào đỉnh thứ t.
:::::::::::::::::::val(f) = t(W+(s)) = t(W-(t))

Ứng dụng thực tế. Ví dụ
Xét đồ thị tương ứng hệ thống ống dẫn dầu. Trong đó các ống tương ứng với các cung, điểm phát là tàu chở dầu, điểm thu là bể chứa, các điểm nối của ống là các nút của đồ thị. Khả năng thông qua của các cung tương ứng là tiết diện các ống. Cần phải tìm luồng dầu lớn nhất có thể bơm từ tàu chở dầu vào bể chứa.
Xác định cường độ lớn nhất của dòng vận tải giữa 2 nút của một bản đồ giao thông.
Bài toán cặp ghép: có m chàng trai và n cô gái. Mỗi chàng trai ưa thích một số cô gái. Hãy tìm cách ghép cặp sao cho số cặp ghép được là nhiều nhất.

Một số thuật toán về luồng cực đại
Bài toán luồng cực đại trên mạng

Lát cắt. Đường tăng luồng
Định nghĩa. Ta gọi lát cắt (X,X) là một cách phân hoạch tập đỉnh V của mạng ra thành hai tập X và X=V \ X, trong đó s ∈ X và t ∈ X. Khả năng thông qua của lát cắt (X,X) là số

Lát cắt với khả năng thông qua nhỏ nhất được gọi là lát cắt hẹp nhất.

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 + 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:
:
A=(a_{ij}) =
\begin{cases}
d_i & \text{nếu } i=j \\
c[i,j] & \text{nếu } [i,j] \in E \\
0 & \text{nếu } [i,j] \not\in E
\end{cases}

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
Mạng tương ứng với G = (V,E), |V | = n là mạng G' = (V',E'), |V'| = 2 |V |, |E'| = 2 |E | - 1. Được biểu diễn thông qua ma trận A' cấp (2n x 2n) như sau:
:
A^\prime=(a^\prime_{ij}) =
\begin{cases}
0 & \text{nếu } i=j \\
c[i,j] & \text{nếu } [i,j] \in E^\prime
\end{cases}

Như thí dụ trên có mạng G như sau:

Tương tự mạng G'

Áp dụng Thuật toán Ford-Fulkerson tìm luồng cực đại cho mạng G' ta được mạng cực đại và ma trận biểu diễn nó như sau

Giả mã luồng cực đại

Chú thích

Đọc thêm
Thuật toán Ford-Fulkerson
Luồng trên mạng
Liên kết ngoài
Bài toán luồng cực đại trên mạng - Các thuật toán đa thức
Animation of Ford-Fulkerson algorithm

Sách trực tuyến về Lý thuyết đồ thị Busbutao
Hướng dẫn về lý thuyết đồ thị
Bài giảng của một môn học về các thuật toán đồ thị
Minh họa hoạt hình về các thuật toán đồ thị
Lần bước thuật toán để tìm hiểu.
Tóm tắt các trang minh họa thuật toán
Dữ liệu test chuẩn cho các bài toán đồ thị con đầy đủ lớn nhất (Maximum Clique), tập con độc lập lớn nhất (Maximum Independent Set), phủ đỉnh nhỏ nhất (Minimum Vertex Cover) và tô màu đỉnh (Vertex Coloring)
Sưu tập ảnh số 1: một số mạng lưới thực
Sưu tập ảnh số 1: một số mạng lưới thực
Sưu tập các liên kết về đồ thị
Các tạp chí lý thuyết đồ thị
Sách về lý thuyết đồ thị