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.

Ví dụ

Trên hình bên phải là một mạng vận tải với nguồn , nút thu , và bốn nút khác. Luồng và khả năng thông qua được ký hiệu . 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ừ  tới  là 5, dễ thấy từ thực tế là tổng luồng từ  ra có giá trị bằng 5, và cũng bằng tổng luồng vào . 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 . 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 ,  và , đó là các đường tăng. Khả năng thông qua của đường thứ nhất là . Đườ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ừ  tới  đồng thời với một luồng có giá trị bằng 1 từ  to , 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  có một chi phí cho trước , và chi phí gửi luồng  qua cung đó là . 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 , ngoài  còn có một cận dưới . 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  và . Do luồng tuần hoàn trong mạng nên bài toán được đặt tên như vậy.