Lưu lượng tối đa DSA

Vấn đề dòng chảy tối đa

Bài toán Luồng cực đại là tìm luồng cực đại qua đồ thị có hướng, từ vị trí này đến vị trí khác trong đồ thị.

Cụ thể hơn, luồng xuất phát từ đỉnh nguồn \(s\) và kết thúc ở đỉnh chìm \(t\) và mỗi cạnh trong biểu đồ được xác định bằng một luồng và dung lượng, trong đó dung lượng là lớn nhất luồng mà cạnh đó có thể có.

Việc tìm luồng tối đa có thể rất hữu ích:

• Để quy hoạch các con đường trong thành phố nhằm tránh ùn tắc giao thông trong tương lai.
• Để đánh giá hiệu quả của việc tháo bỏ đường ống nước, dây điện hoặc cáp mạng.
• Để tìm ra vị trí nào trong mạng lưới luồng, việc mở rộng công suất sẽ dẫn đến luồng tối đa cao nhất, với mục đích tăng chẳng hạn như lưu lượng truy cập, lưu lượng dữ liệu hoặc lưu lượng nước.

Thuật ngữ và khái niệm

Mạng luồng thường được gọi là đồ thị có hướng với luồng chạy qua nó.

Dung lượng \(c\) của một cạnh cho chúng ta biết lưu lượng được phép chảy qua cạnh đó là bao nhiêu.

Mỗi cạnh cũng có một giá trị luồng cho biết luồng hiện tại ở cạnh đó là bao nhiêu.

Cạnh trong hình trên \( v_1 \rightarrow v_2 \), đi từ đỉnh \( v_1 \) đến đỉnh \( v_2 \), có luồng và dung lượng được mô tả là 0/7 , có nghĩa là luồng là 0 , và công suất là 7 . Vì vậy, luồng ở cạnh này có thể tăng lên tới 7, nhưng không nhiều hơn.

Ở dạng đơn giản nhất, mạng luồng có một đỉnh nguồn \(s\) nơi luồng đi ra và một đỉnh chìm \(t\) nơi luồng đi vào. Các đỉnh khác chỉ có luồng đi qua chúng.

Đối với tất cả các đỉnh ngoại trừ \(s\) và \(t\), có sự bảo toàn dòng chảy , có nghĩa là cùng một lượng dòng chảy đi vào một đỉnh cũng phải đi ra khỏi đỉnh đó.

Luồng tối đa được tìm thấy bằng các thuật toán như Ford-Fulkerson hoặc Edmonds-Karp, bằng cách gửi ngày càng nhiều luồng qua các cạnh trong mạng luồng cho đến khi dung lượng của các cạnh đạt đến mức không thể gửi thêm luồng nào nữa. Đường dẫn như vậy có thể gửi nhiều luồng hơn được gọi là đường dẫn tăng cường .

Thuật toán Ford-Fulkerson và Edmonds-Karp được triển khai bằng cách sử dụng một thứ gọi là mạng dư . Điều này sẽ được giải thích chi tiết hơn ở các trang tiếp theo.

Mạng dư được thiết lập với dung lượng dư trên mỗi cạnh, trong đó dung lượng dư của một cạnh là dung lượng trên cạnh đó trừ đi luồng. Vì vậy, khi lưu lượng tăng ở một cạnh, công suất dư sẽ giảm với cùng một lượng.

Đối với mỗi cạnh trong mạng dư, cũng có một cạnh đảo ngược hướng theo hướng ngược lại với cạnh ban đầu. Dung lượng còn lại của cạnh đảo ngược là dòng chảy của cạnh ban đầu. Các cạnh được đảo ngược rất quan trọng để gửi luồng trở lại trên một cạnh như một phần của thuật toán luồng tối đa.

Hình ảnh bên dưới hiển thị các cạnh đảo ngược trong biểu đồ từ mô phỏng ở đầu trang này. Mỗi cạnh đảo ngược chỉ theo hướng ngược lại và do không có luồng nào trong biểu đồ bắt đầu nên dung lượng dư của các cạnh đảo ngược là 0.

Một số khái niệm này, như mạng dư và cạnh đảo ngược, có thể khó hiểu. Đó là lý do tại sao những khái niệm này được giải thích chi tiết hơn và có ví dụ ở hai trang tiếp theo.

Khi tìm thấy luồng tối đa, chúng ta sẽ nhận được giá trị tổng cộng có bao nhiêu luồng có thể được gửi qua mạng luồng.

Nhiều đỉnh nguồn và đỉnh chìm

Thuật toán Ford-Fulkerson và Edmonds-Karp kỳ vọng một đỉnh nguồn và một đỉnh chìm có thể tìm được luồng cực đại.

Nếu đồ thị có nhiều hơn một đỉnh nguồn hoặc nhiều hơn một đỉnh chìm thì đồ thị phải được sửa đổi để tìm luồng cực đại.

Để sửa đổi biểu đồ để bạn có thể chạy thuật toán Ford-Fulkerson hoặc Edmonds-Karp trên đó, hãy tạo một đỉnh siêu nguồn bổ sung nếu bạn có nhiều đỉnh nguồn và tạo thêm một đỉnh siêu chìm nếu bạn có nhiều đỉnh chìm .

Từ đỉnh siêu nguồn, tạo các cạnh tới các đỉnh nguồn ban đầu, với dung lượng vô hạn. Và tạo các cạnh từ đỉnh chìm đến đỉnh siêu chìm một cách tương tự, với khả năng vô hạn.

Hình ảnh bên dưới hiển thị một biểu đồ như vậy có hai nguồn \(s_1\) và \(s_2\) và ba phần chìm \(t_1\), \(t_2\) và \(t_3\).

Để chạy Ford-Fulkerson hoặc Edmonds-Karp trên biểu đồ này, một siêu nguồn \(S\) được tạo với các cạnh có dung lượng vô hạn đối với các nút nguồn ban đầu và một siêu nguồn \(T\) được tạo với các cạnh có dung lượng vô hạn đến nó từ bồn rửa ban đầu.

Thuật toán Ford-Fulkerson hoặc Edmonds-Karp hiện có thể tìm luồng cực đại trong biểu đồ có nhiều đỉnh nguồn và đỉnh chìm, bằng cách đi từ siêu nguồn \(S\), đến siêu chìm \(T\).

Định lý cắt tối thiểu dòng chảy tối đa

Để hiểu định lý này nói gì, trước tiên chúng ta cần biết vết cắt là gì.

Chúng ta tạo hai tập hợp đỉnh: một tập hợp chỉ có đỉnh nguồn bên trong nó được gọi là "S" và một tập hợp có tất cả các đỉnh khác bên trong nó (bao gồm cả đỉnh chìm) được gọi là "T".

Bây giờ, bắt đầu từ đỉnh nguồn, chúng ta có thể chọn mở rộng tập S bằng cách bao gồm các đỉnh liền kề và tiếp tục bao gồm các đỉnh liền kề bao nhiêu tùy thích miễn là chúng ta không bao gồm đỉnh chìm.

Tập mở rộng S sẽ thu nhỏ tập T, vì bất kỳ đỉnh nào cũng thuộc về tập S hoặc tập T.

Trong cách thiết lập như vậy, với bất kỳ đỉnh nào thuộc tập S hoặc tập T, sẽ có một "điểm cắt" giữa các tập hợp. Phần cắt bao gồm tất cả các cạnh trải dài từ tập S đến tập T.

Nếu chúng ta cộng tất cả dung lượng từ các cạnh đi từ tập S đến tập T, chúng ta sẽ có được dung lượng của vết cắt, đó là tổng luồng có thể có từ nguồn đến điểm chìm trong vết cắt này.

Mức cắt tối thiểu là mức cắt chúng ta có thể thực hiện với tổng công suất thấp nhất, đây sẽ là điểm nghẽn.

Trong hình ảnh bên dưới, ba vết cắt khác nhau được thực hiện trong biểu đồ từ mô phỏng ở đầu trang này.

Đường cắt A: Đường cắt này có các đỉnh \(s\) và \(v_1\) trong tập S, và các đỉnh khác nằm trong tập T. Tổng dung lượng của các cạnh rời khỏi tập S trong đường cắt này, từ phần chìm đến nguồn, là 3+4+7=14. Chúng tôi sẽ không thêm công suất từ ​​cạnh \(v_2 \rightarrow v_1\), vì cạnh này đi theo hướng ngược lại, từ đích đến nguồn. Vậy lưu lượng lớn nhất có thể có trên đường cắt A là 14.

Vết cắt B: Dòng chảy tối đa có thể là 3+4+3=10 qua vết cắt B.

Đường cắt C: Luồng tối đa có thể là 2+6=8 trên đường cắt C. Nếu chúng tôi kiểm tra tất cả các đường cắt khác trong biểu đồ, chúng tôi sẽ không tìm thấy đường cắt có tổng công suất thấp hơn. Đây là mức cắt giảm tối thiểu. Bạn đã chạy mô phỏng để tìm luồng tối đa ở đầu trang này chưa? Khi đó bạn cũng biết rằng 8 là luồng cực đại, đó chính xác là những gì định lý cắt cực tiểu luồng cực đại nói.

Định lý cắt tối thiểu luồng cực đại nói rằng việc tìm đường cắt tối thiểu trong đồ thị cũng giống như tìm luồng tối đa, bởi vì giá trị của đường cắt tối thiểu sẽ bằng giá trị của luồng tối đa.

Ý nghĩa thực tiễn của Định lý cắt tối thiểu dòng chảy cực đại

Việc tìm luồng tối đa trong biểu đồ bằng thuật toán như Ford-Fulkerson cũng giúp chúng ta hiểu điểm cắt tối thiểu ở đâu: Điểm cắt tối thiểu sẽ là nơi các cạnh đã đạt hết công suất.

Điểm cắt tối thiểu sẽ là nơi có nút cổ chai, vì vậy nếu chúng ta muốn tăng lưu lượng vượt quá giới hạn tối đa, thường xảy ra trong các tình huống thực tế, giờ đây chúng ta biết cạnh nào trong biểu đồ cần được sửa đổi để tăng lưu lượng tổng thể.

Việc sửa đổi các cạnh ở mức cắt tối thiểu để cho phép có nhiều dòng chảy hơn có thể rất hữu ích trong nhiều trường hợp:

• Có thể đạt được lưu lượng giao thông tốt hơn vì các nhà quy hoạch thành phố giờ đây đã biết nơi nào cần tạo thêm làn đường, nơi nào để định tuyến lại giao thông hoặc nơi nào để tối ưu hóa tín hiệu giao thông.
• Trong sản xuất, có thể đạt được sản lượng cao hơn bằng cách nhắm mục tiêu cải tiến ở những điểm nghẽn, ví dụ như nâng cấp thiết bị hoặc phân bổ lại nguồn lực.
• Trong logistics, biết nút thắt ở đâu, chuỗi cung ứng có thể được tối ưu hóa bằng cách thay đổi tuyến đường hoặc tăng công suất tại các điểm quan trọng, đảm bảo hàng hóa được vận chuyển từ kho đến người tiêu dùng hiệu quả hơn.

Vì vậy, việc sử dụng thuật toán luồng tối đa để tìm ra mức cắt tối thiểu sẽ giúp chúng tôi hiểu được hệ thống có thể được sửa đổi ở đâu để cho phép thông lượng cao hơn nữa.

Vấn đề dòng chảy tối đa được mô tả bằng toán học

Bài toán luồng cực đại không chỉ là một chủ đề trong Khoa học Máy tính mà nó còn là một dạng Tối ưu hóa Toán học, thuộc lĩnh vực Toán học.

Trong trường hợp bạn muốn hiểu điều này tốt hơn về mặt toán học, bài toán luồng cực đại được mô tả bằng thuật ngữ toán học bên dưới.

Tất cả các cạnh (\(E\)) trong biểu đồ, đi từ đỉnh (\(u\)) đến đỉnh (\(v\)), đều có luồng (\(f\)) nhỏ hơn, hoặc bằng dung lượng (\(c\)) của cạnh đó:

\[ \forall (u,v) \in E: f(u,v) \leq c(u,v) \]

Về cơ bản, điều này chỉ có nghĩa là luồng ở một cạnh bị giới hạn bởi dung lượng ở cạnh đó.

Ngoài ra, đối với tất cả các cạnh (\(E\)), luồng theo một hướng từ \(u\) đến \(v\) cũng giống như có luồng âm theo hướng ngược lại, từ \(v\) đến \(u\):

\[ \forall (u,v) \in E: f(u,v) = -f(v,u) \]

Và biểu thức bên dưới nói rằng việc bảo toàn dòng được giữ cho tất cả các đỉnh (\(u\)) ngoại trừ đỉnh nguồn (\(s\)) và cho đỉnh chìm (\(t\)):

\[ \forall u \in V \setminus \{s,t\} \Rightarrow \sum_{w \in V} f(u,w) = 0 \]

Điều này chỉ có nghĩa là lượng luồng đi vào một đỉnh bằng với lượng luồng đi ra khỏi đỉnh đó (ngoại trừ các đỉnh nguồn và đỉnh chìm).

Và cuối cùng, tất cả luồng rời khỏi đỉnh nguồn \(s\), phải kết thúc ở đỉnh đích \(t\):

\[ \sum_{(s,u) \in E} f(s,u) = \sum_{(v,t) \in E} f(v,t) \]

Phương trình trên phát biểu rằng việc cộng tất cả luồng đi ra trên các cạnh từ đỉnh nguồn sẽ cho chúng ta cùng một tổng như cộng luồng ở tất cả các cạnh đi vào đỉnh đích.