Luồng Cực đại – Wikipedia Tiếng Việt

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

[sửa | sửa mã nguồn]

• 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

[sửa | sửa mã nguồn]

• 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:

1. Đ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)
2. Đ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

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồn]

• 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ụ

[sửa | sửa mã nguồn]

• 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

[sửa | sửa mã nguồn]

Bài toán luồng cực đại trên mạng:

[sửa | sửa mã nguồn]

Lát cắt. Đường tăng luồng

[sửa | sửa mã nguồn]

Đị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 <f(v,w) < 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

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

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồn]

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) < 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:

A = ( a i j ) = { d i nếu  i = j c [ i , j ] nếu  [ i , j ] ∈ E 0 nếu  [ i , j ] ∉ E {\displaystyle 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 ′ = ( a i j ′ ) = { 0 nếu  i = j c [ i , j ] nếu  [ i , j ] ∈ E ′ {\displaystyle A^{\prime }=(a_{ij}^{\prime })={\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

[sửa | sửa mã nguồn]

Chú thích

[sửa | sửa mã nguồn]

Đọc thêm

[sửa | sửa mã nguồn]

• Thuật toán Ford-Fulkerson
• Luồng trên mạng

Liên kết ngoài

[sửa | sửa mã nguồn]

• 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
• Animation of Ford-Fulkerson algorithm Lưu trữ 2006-07-17 tại Wayback Machine

Tư liệu liên quan tới Ford-Fulkerson's algorithm tại Wikimedia Commons

• Sách trực tuyến về Lý thuyết đồ thị Busbutao
• Hướng dẫn về lý thuyết đồ thị Lưu trữ 2012-01-16 tại Wayback Machine
• Bài giảng của một môn học về các thuật toán đồ thị Lưu trữ 2005-08-31 tại Wayback Machine
• 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 Lưu trữ 2008-06-01 tại Wayback Machine
• 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) Lưu trữ 2013-05-29 tại Wayback Machine
• 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 Lưu trữ 2012-02-23 tại Wayback Machine
• Sưu tập các liên kết về đồ thị
• Các tạp chí lý thuyết đồ thị Lưu trữ 2013-07-04 tại Wayback Machine
• Sách về lý thuyết đồ thị Lưu trữ 2012-09-11 tại Wayback Machine