Trong lý thuyết đồ thị, một luồng trên mạng, thường được gọi tắt là luồng, là một cách gán các luồng (dòng chảy) cho các cung của một đồ thị có hướng (trong trường hợp này được gọi là một mạng vận tải) trong đó mỗi cung có một khả năng thông qua, sao cho dung lượng luồng qua một cung không vượt quá khả năng thông qua của nó. Ngoài ra, ta còn có một điều kiện rằng dung lượng luồng vào một nút phải bằng dung lượng luồng ra khỏi nút đó, ngoại trừ trường hợp nó là một nút phát (hay nút nguồn) - nơi chỉ có dòng ra, hoặc một nút thu - nơi chỉ có luồng vào. Một mạng vận tải có thể được dùng để giả lập giao thông trên một hệ thống đường sá, dòng chảy trong các đường ống, dòng trong một mạch điện, hoặc bất cứ cái gì tương tự di chuyển qua một mạng lưới gồm các nút.

Định nghĩa[sửa | sửa mã nguồn]

Cho một đồ thị ${\displaystyle G(V,E)}$ với các nút ${\displaystyle V}$ và các cung ${\displaystyle E}$, và hai nút đặc biệt: nút phát ${\displaystyle s}$ (bậc trong bằng 0) và nút thu ${\displaystyle t}$ (bậc ngoài bằng 0). Cho ${\displaystyle f(u,v)}$ là dòng từ nút ${\displaystyle u}$ tới nút ${\displaystyle v}$, và ${\displaystyle c(u,v)}$ là khả năng thông qua (dòng lớn nhất có thể) của cung đó. Một luồng trên mạng là một hàm số giá trị thực ${\displaystyle f:V\times V\rightarrow R}$ với ba tính chất sau cho tất cả các nút ${\displaystyle u}$ và ${\displaystyle v}$:

1. Đối xứng: ${\displaystyle \ f(u,v)=-f(v,u)}$. Tổng luồng từ ${\displaystyle u}$ tới ${\displaystyle v}$ phải bằng đối của tổng luồng từ ${\displaystyle v}$ tới ${\displaystyle u}$ (Xem ví dụ).
2. Các điều kiện về khả năng thông qua: ${\displaystyle \ f(u,v)\leq c(u,v)}$. Luồng dọc theo một cung không thể vượt quá khả năng thông qua của nó.
3. Cân bằng luồng: ${\displaystyle \ \sum _{w\in V}f(u,w)=0}$, trừ khi ${\displaystyle u=s}$ hoặc ${\displaystyle u=t}$. Tổng luồng tới một nút bằng 0, ngoại trừ trường hợp đó là nút nguồn - nơi sinh luồng, và nút thu - nơi "tiêu thụ" luồng.

Lưu ý rằng ${\displaystyle f(u,v)}$ là tổng luồng từ ${\displaystyle u}$ tới ${\displaystyle v}$. Nếu đồ thị biểu diễn một mạng vật lý, và nếu có một luồng thực sự, chẳng hạn gồm 4 đơn vị, chảy từ ${\displaystyle u}$ tới ${\displaystyle v}$, và một luồng thực gồm 3 đơn vị chảy từ ${\displaystyle v}$ tới ${\displaystyle u}$, ta có ${\displaystyle f(u,v)=1}$ và ${\displaystyle f(v,u)=-1}$.

Khả năng thông qua còn dư (residual capacity) của một cạnh là ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$. Khái niệm đó định nghĩa một mạng còn dư (residual network), ký hiệu là ${\displaystyle G_{f}(V,E_{f})}$, thể hiện lượng khả năng thông qua hiện có. Để ý rằng có thể có một cung từ ${\displaystyle u}$ tới ${\displaystyle v}$ trong mạng còn dư, ngay cả khi không có cung từ ${\displaystyle u}$ tới ${\displaystyle v}$ trong mạng ban đầu. Do các luồng theo các hướng ngược nhau triệt tiêu lẫn nhau, giảm luồng từ ${\displaystyle v}$ tới ${\displaystyle u}$ tương đương với tăng luồng từ ${\displaystyle u}$ tới ${\displaystyle v}$. Một đường tăng (augmenting path) là một đường đi ${\displaystyle (u_{1},u_{2},\dots ,u_{k})}$, trong đó ${\displaystyle u_{1}=s}$, ${\displaystyle u_{k}=t}$, và ${\displaystyle c_{f}(u_{i},u_{i+1})>0}$, nghĩa là có thể gửi thêm luồng dọc theo đường đi này.

Ví dụ[sửa | sửa mã nguồn]

Trên hình bên phải là một mạng vận tải với nguồn ${\displaystyle s}$, nút thu ${\displaystyle t}$, và bốn nút khác. Luồng và khả năng thông qua được ký hiệu ${\displaystyle f/c}$. Lưu ý rằng trong mạng này, các điều kiện về đối xứng, khả năng thông qua và cân bằng luồng đã được thỏa mãn. Tổng luồng từ ${\displaystyle s}$ tới ${\displaystyle t}$ là 5, dễ thấy từ thực tế là tổng luồng từ ${\displaystyle s}$ ra có giá trị bằng 5, và cũng bằng tổng luồng vào ${\displaystyle t}$. Ta biết rằng không có luồng mới xuất hiện hoặc biến mất tại bất cứ nút nào khác.

Bên dưới là hình vẽ mạng còn dư từ luồng đã cho. Lưu ý rằng có khả năng thông qua trên một số cung mà khả năng thông qua ban đầu bằng 0, ví dụ đối với cung ${\displaystyle (d,c)}$. Luồng này không phải là một luồng cực đại. Có cung với khả năng thông qua dương suốt dọc theo các đường ${\displaystyle (s,a,c,t)}$, ${\displaystyle (s,a,b,d,t)}$ và ${\displaystyle (s,a,b,d,c,t)}$, đó là các đường tăng. Khả năng thông qua của đường thứ nhất là ${\displaystyle min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))=min(5-3,3-2,2-1)=min(2,1,1)=1}$. Đường đi cuối cùng không tồn tại trong mạng ban đầu, nhưng nếu ta gửi luồng theo đường đó, ta vẫn có một luồng hợp lệ.

Nếu đây là một mạng thực sự, có thể có một luồng có giá trị bằng 2 từ ${\displaystyle a}$ tới ${\displaystyle b}$ đồng thời với một luồng có giá trị bằng 1 từ ${\displaystyle b}$ to ${\displaystyle a}$, nhưng ta chỉ quản lý luồng tổng.

Ứng dụng[sửa | sửa mã nguồn]

Một mạng vận tả có thể được sử dụng để giả lập một hệ thống bất kỳ nếu nó có các điều kiện như trong định nghĩa ở trên.

Hình dung một loại đường ống nối với nhau thành một mạng. Mỗi đường ống có một độ rộng nhất định, do đó nó chỉ có thể cho phép một dòng chảy với một lượng nước nhất định. Mỗi khi các đường ống gặp nhau, tổng lượng nước chảy vào điểm nối phải bằng lượng chảy ra từ đó. Ta có một nguồn nước, đó là điểm phát, và một điểm tập trung nước, đó là điểm thu. Khi đó một luồng có thể là một cách lấy nước từ nguồn tới nút thu. sao cho tổng lượng nước ra khỏi nút thu là không đổi. Về trực quan, tổng luồng của một mạng chính là tỷ lệ nước chảy ra từ điểm thu.

Luồng có thể so sánh với người hoặc vật liệu trên các mạng giao thông vận tải, hoặc với điện trên các hệ thống phân phối điện. Với mỗi mạng vật lý như vậy, luồng vào mỗi nút trung gian phải bằng luồng ra khỏi đó. Bollobás nêu đặc trưng này theo Kirchhoff's current law, trong khi các tác giả sau này (Chartrand) nhắc đến su duy rộng tới một số phương trình quy ước (conservation equation).

Tổng quát hóa và chuyên biệt hóa[sửa | sửa mã nguồn]

Bài toán đơn giản nhất và thông dụng nhất cho luồng trên mạng là bài toán tìm luồng cực đại trong một đồ thị cho trước, với kết quả mong muốn là luồng tổng lớn nhất có thể từ điểm nguồn đến điểm thu. Có nhiều bài toán khác có thể được giải bằng các thuật toán luồng cực đại, nếu chúng được mô hình hóa dưới dạng các mạng vận tải, chẳng hạn như các bài cặp ghép hai phía, bài toán phân công công việc (assignment problem), bài toán vận tải.

Trong một bài toán luồng đa (multi-commodity flow problem), ta có nhiều điểm phát, nhiều điểm thu, và nhiều loại "hàng" cần chảy từ một nút phát cho trước tới một nút thu cho trước. Ví du, nhiều loại hàng được sản xuất tại nhiều nhà máy, và cần được chuyên chở đến cho các khách hàng khác nhau qua cùng một mạng giao thông.

Trong một bài toán luồng chi phí cực tiểu, mỗi cung ${\displaystyle u,v}$ có một chi phí cho trước ${\displaystyle k(u,v)}$, và chi phí gửi luồng ${\displaystyle f(u,v)}$ qua cung đó là ${\displaystyle f(u,v)\cdot k(u,v)}$. Mục tiêu là gửi một luồng có dung lượng cho trước từ nguồn tới điểm thu với chi phí thấp nhất.

Trong một bài toán luồng tuần hoàn (circulation problem), với mỗi cung ${\displaystyle (u,v)}$, ngoài ${\displaystyle c(u,v)}$ còn có một cận dưới ${\displaystyle l(u,v)}$. Mỗi cung cũng có một chi phí. Thông thường, trong bài toán luồng tuần hoàn, điều kiện cân bằng luồng sẽ phải áp dụng cho mọi nút, và có một kết nối giữa điểm thu ngược trở lại điểm phát. Bằng cách này, ta có thể áp đặt luồng tổng bằng ${\displaystyle l(t,s)}$ và ${\displaystyle c(t,s)}$. Do luồng tuần hoàn trong mạng nên bài toán được đặt tên như vậy.

Mối quan hệ giữa các bài toán luồng[sửa | sửa mã nguồn]

Nhiều biến thể của các bài toán luồng có quan hệ với nhau với hình thức bài này là tổng quát hóa hay chuyên biệt hóa của bài kia. Trong cây dưới đây, một bài toán có thể được giải bằng một lời giải cho bài toán cha.

• Bài toán luồng với các điều kiện và hàm mục tiêu tùy ý.
  • Bài toán luồng với các điều kiện tuyến tính.
    • Bài toán luồng tuần hoàn đa (Multi-commodity circulation problem). Thuật toán thời gian đa thức duy nhất được biết là giải bằng quy hoạch tuyến tính.
      • Bài toán luồng đa chi phí cực tiểu. Đặt tất cả các cận dưới bằng 0.
        • Bài toán luồng chi phí cực tiểu. Giải với một loại hàng, 1 thu, 1 phát.
          • Bài toán luồng cực đại. Đặt tất cả chi phí bằng 0 và cực đại hóa luồng.
          • Bài toán tìm một đường đi ngắn nhất. Đặt tất cả các khả năng thông qua bằng 1, tìm luồng có độ lớn 1.
        • Bài toán luồng đa. Đặt tất cả chi phí bằng 0.
          • Đặt tất cả chi phí bằng 0. Giải với một loại hàng, 1 thu, 1 phát.
        • Bài toán tìm đường đi ngắn nhất cho mọi cặp đỉnh. Cho các khả năng thông qua là vô hạn, tìm luồng độ lớn 1 cho ${\displaystyle v(v-1)/2}$ loại hàng, mỗi loại cho 1 cặp đỉnh.
      • Bài toán luồng tuần hoàn. Giải với một loại hàng, 1 thu, 1 phát.

Trong tất cả các bài toán trên, ta có thể tìm một luồng cực đại hoặc một luồng có độ lớn cho trước.

Liên kết ngoài[sửa | sửa mã nguồn]

• Maximum Flow Problem Lưu trữ 2008-01-11 tại Wayback Machine
• Maximum Flow
• Ford-Fulkerson Max Flow Labeling Algorithm Lưu trữ 2006-03-03 tại Wayback Machine

Tham khảo[sửa | sửa mã nguồn]

Đọc thêm[sửa | sửa mã nguồn]

• Bollobás, Béla (1979). Graph Theory: An Introductory Course. Heidelberg: Springer-Verlag. ISBN 3-540-90399-2.
• Chartrand, Gary & Oellermann, Ortrud R. (1993). Applied and Algorithmic Graph Theory. New York: McGraw-Hill. ISBN 0-07-557101-3.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
• Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. ISBN 0-914894-21-8.
• Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge: Cambridge University Press. ISBN 0-521-28881-9 ISBN 0-521-24659-8.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. “26”. Introduction to Algorithms (ấn bản 2). MIT Press and McGraw-Hill. tr. 696–697. ISBN 0262032937.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)

Xem thêm[sửa | sửa mã nguồn]

• Định lý luồng cực đại lát cắt cực tiểu