Lý Thuyết đồ Thị : Bài Toán Luồng Cực đại Trong Mạng - VOER

Mạng. Luồng trong mạng. Bài toán luồng cực đại

Định nghĩa 1 Ta gọi mạng là đồ thị có hướng G = (V,E), trong đó duy nhất một đỉnh s không có cung đi vào gọi là đỉnh phát, duy nhất một đỉnh t không có cung đi ra gọi là điểm thu và mỗi cung e=(v,w) ∈ E được gán với một số không âm c(e) =c(v,w) gọi là khả năng thông qua của cung e.

Để thuận tiện cho việc trình bày ta sẽ qui ước rằng nếu không có cung (v,w) thì khả năng thông qua c(v,w) được gán bằng 0.

Định nghĩa 2 Giả sử cho mạng G=(V,E). Ta gọi mạng f trong mạng G=(V,E) ;là ánh xạ f: E→R+ gán cho mỗi cung e =(v,w) ∈ E một số thực không âm f(e)=f(v,w), gọi là luồng trên cung e, thoả mãn các điểu kiện sau:

- Luồng trên cung e ∈ E không vượt quá khả năng thông qua của nó:

- Đ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 đi 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:

trong đó N-(v) – tập các đỉnh của mạng mà từ đó có cung đến v, N+(v) - tập các đỉnh của mạng mà từ v có cung đến nó:

Giá trị của luồng f là số

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

Cho mạng G(V,E). Hãy tìm luồng f* trong mạng với giá trị luồng val(f*) là lớn nhất. Luồng như vậy ta sẽ gọi là luồng cực đại trong mạng.

Bài toán như vậy có thể xuất hiện trong rất nhiều ứng dụng thực tế. Chẳng hạn khi cần xác định cường độ lớn nhất của dòng vận tải giữa hai nút của một bản đồ giao thông. Trong ví dụ này lời giải của bài toán luồng cực đại sẽ chỉ cho ta các đoạn đường đông xe nhất và chúng tạo thành "chỗ hẹp" tương ứng với dòng giao thông xét theo hai nút được chọn. Một ví dụ khác là nếu xét đồ thị tương ứng với một hệ thống đường ống dẫn dầu. Trong đó các ống tương ứng với các cung, điểm phát có thể coi là tầu chở dầu, điểm thu là bể chứa, còn những điểm nối giữa các ống là các nút của đồ thị. Khả năng thông qua của các cung tương ứng với tiết diện của 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