Luồng trên mạng

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.
Cho một đồ thị formula_1 với các nút formula_2 và các cung formula_3, và hai nút đặc biệt: nút phát formula_4 (bậc trong bằng 0) và nút thu formula_5 (bậc ngoài bằng 0).
Cho formula_6 là dòng từ nút formula_7 tới nút formula_8, và formula_9 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 formula_10 với ba tính chất sau cho tất cả các nút formula_7 và formula_8:
Lưu ý rằng formula_6 là tổng luồng từ formula_7 tới formula_8. 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ừ formula_7 tới formula_8, và một luồng thực gồm 3 đơn vị chảy từ formula_8 tới formula_7, ta có formula_29 và formula_30.
Khả năng thông qua còn dư ("residual capacity") của một cạnh là formula_31. Khái niệm đó định nghĩa một mạng còn dư ("residual network"), ký hiệu là formula_32, thể hiện lượng khả năng thông qua "hiện có". Để ý rằng có thể có một cung từ formula_7 tới formula_8 trong mạng còn dư, ngay cả khi không có cung từ formula_7 tới formula_8 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ừ formula_8 tới formula_7 tương đương với "tăng" luồng từ formula_7 tới formula_8. Một đường tăng ("augmenting path") là một đường đi formula_41, trong đó formula_42, formula_43, và formula_44, nghĩa là có thể gửi thêm luồng dọc theo đường đi này.
Ví dụ.
Trên hình bên phải là một mạng vận tải với nguồn formula_4, nút thu formula_5, và bốn nút khác. Luồng và khả năng thông qua được ký hiệu formula_47. 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ừ formula_4 tới formula_5 là 5, dễ thấy từ thực tế là tổng luồng từ formula_4 ra có giá trị bằng 5, và cũng bằng tổng luồng vào formula_5. 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 formula_52. 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 formula_53, formula_54 và formula_55, đó là các đường tăng. Khả năng thông qua của đường thứ nhất là formula_56. Đườ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ừ formula_57 tới formula_58 đồng thời với một luồng có giá trị bằng 1 từ formula_58 to formula_57, nhưng ta chỉ quản lý luồng tổng.
Ứng dụng.
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.
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 formula_61 có một chi phí cho trước formula_62, và chi phí gửi luồng formula_6 qua cung đó là formula_64. 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 formula_65, ngoài formula_9 còn có một cận dưới formula_67. 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 formula_68 và formula_69. 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.
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.
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.