Luồng cực đại

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Luồng cực đại là một trong những bài toán tối ưu trên đồ thị tìm được những ứng dụng rất rộng rãi trong cả thực tế cũng như trong lý thuyết tổ hợp. Bài toán được đề xuất vào đầu những năm 1950 và gắn liền với tên tuổi của 2 nhà toán học Mỹ Lester Randolph FordDelbert Ray Fulkerson.

Mạng[sửa | sửa mã nguồn]

  • Mạng (network) là một đồ thị có hướng G = (V, E) trong đó:
    Có duy nhất một đỉnh s không có cung đi vào, được gọi là đỉnh phát (source)
    Có duy nhất một đỉnh t không có cung đi ra, được gọi là đỉnh thu (sink)

Mỗi cạnh e = (u, v) ∈ E được gán một số nguyên không âm c(e) = c[u, v] và gọi là khả năng thông qua của cung đó (capacity).

  • Ta quy ước nếu mạng không có cung (u, v) thì ta thêm vào cung (u, v) với khả năng thông qua c[u, v] bằng 0.
  • Với một mạng G = (V, E, c), ta ký hiệu:

W-(x) = {(u, v) ∈ E | u ∈ V}: tập các cung đi vào đỉnh v.

W+(x) = {(v, u) ∈ E | u ∈ V}: tập các cung đi ra khỏi đỉnh v.

Luồng trên mạng[sửa | sửa mã nguồn]

  • Giả sử cho mạng G = (V, E). Ta gọi luồng f trong mạng là ánh xạ f: E → R+ gán cho mỗi cung e = (u, v) ∈ E một số thực không âm f(e) = f[u, v], thoả mãn các điều kiện sau:
  1. ĐK 1 (Capacity Constraint): Luồng trên mỗi cung e ∈ E không vượt quá khả năng thông qua của nó: 0 ≤ f(e) ≤ c(e)
  2. ĐK 2 (Flow Conversion): Đ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 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: t(W-(x)) = t(W+(x)), ∀x ≠ s, t

Tính chất của luồng[sửa | sửa mã nguồn]

Với tập B ⊆ V, ký hiệu:

W-(B) = { (a, b)∈ E | a∉B,b∈B } - tập cạnh từngoài B đi vào B.

W+(B) = { (a, b)∈ E | a∈B,b∉B } - tập cạnh từ B đi ra khỏi B.

Khi đó nếu tập con các đỉnh B không chứa x0 và z thì: t (W-(B)) =t (W+(B)).Theo tính chất b) của luồng: ∑ t (W-(x)) =∑ t (W+(x)).

Cạnh kề với đỉnh x nếu có đỉnh đầu và đỉnh cuối đều nằm trong tập B thì nó sẽ có mặt ở cả hai vế củađẳng thức đúng một lần, do đó có thể giản ước.

Giá trị của luồng[sửa | sửa mã nguồn]

  • Giá trị của một luồng được tính bằng tổng giá trị trên các cung đi ra từ đỉnh nguồn s (đỉnh 1 Hình 1), hoặc tổng giá trị trên các cung đi vào đỉnh thứ t (đỉnh 6 Hình 1).
val(f) = t(W+(s)) = t(W-(t))
Hình 1: Luồng cực đại. Hai số trên từng cạnh tương ứng là giá trị luồng và khả năng thông qua của từng cặp cạnh. 1 là đỉnh phát, 6 là đỉnh thu.

Ứng dụng thực tế. Ví dụ[sửa | sửa mã nguồn]

  • Xét đồ thị tương ứng hệ thống ống dẫn dầu. Trong đó các ống tương ứng với các cung, điểm phát là tàu chở dầu, điểm thu là bể chứa, các điểm nối của ống là các nút của đồ thị. Khả năng thông qua của các cung tương ứng là tiết diện 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.
  • Xác định cường độ lớn nhất của dòng vận tải giữa 2 nút của một bản đồ giao thông.
  • Bài toán cặp ghép: có m chàng trai và n cô gái. Mỗi chàng trai ưa thích một số cô gái. Hãy tìm cách ghép cặp sao cho số cặp ghép được là nhiều nhất.

Một số thuật toán về luồng cực đại[sửa | sửa mã nguồn]

Bài toán luồng cực đại trên mạng:[sửa | sửa mã nguồn]

Lát cắt. Đường tăng luồng[sửa | sửa mã nguồn]

Định nghĩa. Ta gọi lát cắt (X,X*) là một cách phân hoạch tập đỉnh V của mạng ra thành hai tập X và X*=V \ X, trong đó s ∈ X và t ∈ X*. Khả năng thông qua của lát cắt (X,X*) là số

Lát cắt với khả năng thông qua nhỏ nhất được gọi là lát cắt hẹp nhất.

Bổ đề 1. giá trị của mọi luồng f trong mạng luôn nhỏ hơn bằng khả năng thông qua lát cắt (X,X*) bất kỳ trong nó: val(f) £ c(X,X*).

Hệ quả 1. Giá trị luồng cực đại trong mạng không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng. Giả sử f là một luồng trong mạng G = (V,E). Từ mạng G = (V,E) ta xây dựng đồ thị có trọng số trên cung Gf =(V,Ef), với tập cung Ef và trọng số trên các cung được xác định theo quy tắc sau:

     *     Nếu e = (v,w) ∈ E  với f(v,w) = 0, thì (v,w)∈ Ef với trọng số c(v,w);
     *     Nếu e = (v,w) ∈ E  với f(v,w) = c(v,w), thì (v,w)∈ Ef với trọng số f(v,w);
     *     Nếu e = (v,w) ∈ E  với  0 <f(v,w) < c(v,w), thì (v,w)∈ Ef với trọng số  c(v,w) - f(v,w) và (w,v) ∈ Ef  với trọng số f(v,w).

Các cung của Gf đồng thời cũng là cung của G được gọi là cung thuận, các cung còn lại gọi là cung nghịch. Đồ thị Gf được gọi là đồ thị tăng luồng.

Ví dụ: Các số viết cạnh các cung của G ở hình 1 theo thứ tự là khả năng thông qua và luồng trên cung

Mạng G và luồng f. Đồ thị có trọng số Gf tương ứng.

Đường tăng luồng. Giả sử P = (s = v0,v1,v2,…,vk= t) là một đường đi từ s đến t trên đồ thị tăng luồng Gf. Gọi d là giá trị nhỏ nhất của các trọng số của các cung trên đường đi P. Xây dựng luồng f' trên mạng G theo quy tắc sau:

                                f(u,v) + d,    nếu (u,v) ∈  P là cung thuận
                 f(u,v) =       f(u,v) -  d,   nếu (u,v) ∈ P là cung nghịch
                                f(u,v),         nếu (u,v) không ∈ P 
Đường tăng luồng

Dễ dàng kiểm tra được rằng f' được xây dựng như trên là luồng trong mạng và val(f')= val(f) + d. Ta sẽ gọi thủ tục biến đổi luồng vừa nêu là tăng luồng dọc theo đường P.

Luồng trên mạng G trước và sau khi tăng.

Sau biến đổi ta có luồng mới mang giá trị 9. val(f,) = 4 + 3 - 3 + 2 + 3 = 9

Thuật toán Ford-Fulkerson[sửa | sửa mã nguồn]

Đến Thuật toán

Luồng cực đại với khả năng thông qua các cung và các đỉnh[sửa | sửa mã nguồn]

Giả sử trong đồ thị G = (V,E), ngoài khả năng thông qua của các cung c(u,v), ở mỗi đỉnh còn có khả năng thông qua của đỉnh là d(v), và đòi hỏi tổng luồng đi vào đỉnh v không còn vượt quá d(v), tức là ∑ f (w, v) < d(v), với w ∈ V

Cần phải tìm luồng cực đại giữa s và t trong mạng như vậy. Xây dựng một mạng G’ sao cho: mỗi đỉnh v của G tương ứng với hai đỉnh (v+ v-) trong G’, mỗi cung (u,v) trong G ứng với cung (u,v+) trong G’ mỗi cung (v,w) trong G ứng với cung (v- w+) trong G’. Ngoài ra, mỗi cung (v+ v-) trong G’ có khả năng thông qua là d(v), tức là bằng khả năng thông qua của đỉnh v trong G.

Giải quyết bài toán Từ mạng G = (V,E) khả năng thông qua các cung và các đỉnh. Ta sẽ giải quyết theo hai bước sau:

* Xác định mạng G’. 
* Tìm luồng cực đại trong mạng G’. Bắt đầu từ luồng 0 với khả năng thông qua cung. 

Ma trận biểu diễn đồ thị của bài toán luồng cực đại

1 Biểu diễn mạng G với khả năng thông qua các cung và đỉnh Giả sử mạng G = (V,E), |V| = n. Ta có thể biểu diễn bởi ma trận trọng số A cấp (n x n) như sau:

Dinh1.png

Trong đó: di là khả năng thông qua đỉnh i; C[i,j] khả năng thông qua cung [i,j].

2 Biểu diễn mạng G’ tương ứng với mạng G Mạng tương ứng với G = (V,E), |V | = n là mạng G’ = (V’,E’), |V’| = 2 |V |, |E’| = 2 |E | - 1. Được biểu diễn thông qua ma trận A’ cấp (2n x 2n) như sau:

Dinhnghia.png

Như thí dụ trên có mạng G như sau:

H8.png

Tương tự mạng G'

Matran.png

Áp dụng T.T Ford-Fulkerson tìm luồng cực đại cho mạng G’ ta được mạng cực đại và ma trận biểu diễn nó như sau

Saumatran.png

Thuật toán kéo luồng sau đỉnh[sửa | sửa mã nguồn]

  • Đây là thuật toán cụ thể thuộc phương pháp kéo luồng sau. Ở đây các đỉnh lệch được đẩy vào hàng đợi. Với mỗi đỉnh lệch lấy từ hàng đợi, ta sẽ kéo luồng vào các cung ưu tiên một cách tối đa cho tới khi đỉnh trở thành không lệch hoặc không còn cung ưu tiên nữa. Nếu không còn cung ưu tiên nữa và đỉnh còn lệch thì ta tăng độ sâu và đẩy nó vào hàng đợi.
  • Bây giờ ta có thể mô tả thuật toán kéo luồng sau đỉnh như sau:

1. Khởi tạo: Xây dựng luồng sau xuất phát với các cung đi đến đỉnh đích có luồng bằng khả năng thông qua, còn các cung khác có luồng bằng 0. Chọn hàm độ sâu d(v) là độ dài đường đi ngắn nhất từ đỉnh nguồn a đến đỉnh v. Đẩy các đỉnh lệch vào hàng đợi Q.

2. Tiêu chuẩn dừng: Nếu Q = ∅, luồng trước f trở thành luồng cực đại. Kết thúc. Nếu Q ≠ ∅, sang bước 3.

3. Xử lý đỉnh lệch: Lấy đỉnh lệch v từ hàng đợi.

Duyệt các cung ưu tiên (u,v) ∈ Gf. Kéo trên cung (u,v) một luồng có giá trị min{−delta,cf(u,v)}, trong đó delta (< 0) là độ lệch luồng của đỉnh v. Nếu đỉnh u là đỉnh lệch mới, thì đẩy đỉnh u vào hàng đợi Q.

Nếu đỉnh v vẫn còn lệch, thì tăng độ sâu của đỉnh v như sau:

           d(v):= 1 + min{d(u) | (u,v) ∈ Gf}

sau đó đẩy v vào hàng đợi Q. Quay lại bước 2.

  • Ví dụ. Tìm luồng cực đại của mạng G sau
Thuật toán kéo luồng sau đỉnh 1.png
 Ghi chú: Tại mỗi đỉnh v ta có hai tham số v(d(v),e(v)), trong đó d(v) là độ sâu của v và e(v) là độ lệch luồng của v.

Quá trình giải được mô tả bằng các hình vẽ sau:

  • Khởi tạo:
Thuật toán kéo luồng sau đỉnh 2.png
  • Cân bằng c:
Thuật toán kéo luồng sau đỉnh 3.png
  • Cân bằng e:
Thuật toán kéo luồng sau đỉnh 4.png
 Ghi chú: sau khi kéo luồng giá trị 2 từ đỉnh d về e, đỉnh e vẫn còn lệch và chỉ có duy nhất một cung (z,e) ∈ Gf, nhưng nó không phải cung ưu tiên. Vì vậy ta phải tăng độ sâu của đỉnh e theo công thức.
           d(e):= 1 + min{d(u) | (u,e) ∈ Gf} = 1 + d(z) = 1 + 3 = 4
  • Cân bằng b:
Thuật toán kéo luồng sau đỉnh 5.png
  • Cân bằng d:
Thuật toán kéo luồng sau đỉnh 6.png
  • Cân bằng e:
Thuật toán kéo luồng sau đỉnh 7.png

Đến đây hàng đợi Q = ∅, thuật giải kết thúc và luồng cuối cùng là luồng cực đại với giá trị luồng là 6.

Thuật toán hoán chuyển nguồn đích tìm luồng cực đại[sửa | sửa mã nguồn]

Điểm mấu chốt của thuật toán Ford-Fulkerson là tìm đường đi tăng trưởng. Công đòi hỏi tiêu tốn quá nhiều thời gian trong quá trình giải. Vì vậy việc giảm khối lượng tính toán ở cung đoạn sẽ làm tăng đáng kể hiệu quả thuật toán. Ý tưởng của phương pháp này là gán nhãn các đỉnh đồng thời từ đỉnh nguồn và đỉnh đích.

  • Đầu vào: Mạng G = (V,E) với nguổn a, đích z, khả năng thông qua C = (ci,j),(i,j) ∈ G.

Các đỉnh trong G được sắp xếp theo thứ tự nào đó.

  • Đầu ra: Luồng cực đại F = (fi,j),(i,j) ∈ G.
  • Các bước.

1. Khởi tạo: Luồng xuất phát: fi,j: = 0 ∀(i,j) ∈ G. Đặt nhãn tiến (↑) cho đỉnh nguồn và nhãn lùi (↓) cho đỉnh đích.

       a(↑,∅,∞) & z(↓,∅,∞)

Tạo lập tập S gồm các đỉnh đã có nhãn tiến nhưng chưa được dùng để sinh nhãn tiến, S' là tập đỉnh được gán nhãn tiến nhờ các đỉnh của tập S.

       S: = {a},S': = ∅

Tạo lập tập T gồm các đỉnh đã có nhãn lùi nhưng chưa được dùng để sinh nhãn lùi, T' là tập đỉnh được gán nhãn lùi nhờ các đỉnh của tập T.

       T: = {z},T': = ∅

2. Sinh nhãn tiến:

2.1. Chọn đỉnh sinh nhãn tiến
  • Trường hợp S ≠ ∅: Chọn đỉnh u ∈ S nhỏ nhất (theo thứ tự). Loại u khỏi S, S:= S\{u}. Ký hiệu nhãn tiến của u là (↑,p,α) và A là tập các đỉnh chưa có nhãn tiến và kề đỉnh sinh nhãn tiến u.
Sang bước 2.2.
  • Trường hợp S = ∅ và S' ≠ ∅: Gán S:= S' và S':= ∅. Sang bước 3.
  • Trường hợp S = ∅ và S' = ∅, thì kết thúc, luồng F là cực đại.
2.2. Gán nhãn tiến cho đỉnh chưa có nhãn tiến và kề đỉnh sinh nhãn tiến u.
  • Trường hợp A = ∅: Quay lại bước 2.1.
  • Trường hợp A ≠ ∅: Chọn t ∈ A nhỏ nhất (theo thứ tự). Loại t khỏi A, A:= A\{t}. Gán nhãn tiến cho t như sau:
Nếu (u,t) ∈ E và fu,t < cu,t, đặt nhãn tiến đỉnh t là (↑, u, min{α,cu,t - fu,t}).
Nếu (t,u) ∈ E và ft,u > 0, đặt nhãn tiến đỉnh t là (↑, u, min{α,ft,u}).
Nếu t không được gán nhãn tiến, thì quay lại bước 2.2.
Nếu t được gán nhãn tiến và t có nhãn lùi, thì sang bước hiệu chỉnh tăng luồng 4.
Nếu t được gán nhãn tiến và t không có nhãn lùi, thì bổ sung t vào S', S':= S' ∪ {t}, và quay lại bước 2.2.

3. Sinh nhãn lùi:

3.1. Chọn đỉnh sinh nhãn lùi.
  • Trường hợp T ≠ ∅: Chọn đỉnh v ∈ T nhỏ nhất (theo thứ tự). Loại v khỏi T, T:= T\{v}. Ký hiệu nhãn lùi của v là (↓, q, β) và B là tập các đỉnh chưa có nhãn lùi và kề đỉnh sinh nhãn lùi v.
Sang bước 3.2.
  • Trường hợp T = ∅ và T' ≠ ∅: Gán T:= T' và T':= ∅. Quay lại bước 2.
  • Trường hợp T = ∅ và T' = ∅, thì kết thúc, luồng F là cực đại.
3.2. Gán nhãn lùi cho đỉnh chưa có nhãn lùi và kề đỉnh sinh nhãn lùi v
  • Trường hợp B = ∅: Quay lại bước 3.1.
  • Trường hợp B ≠ ∅: Chọn t ∈ B nhỏ nhất (theo thứ tự). Loại t khỏi B, B:= B\{t}. Gán nhãn lùi cho t như sau:
Nếu (t,v) ∈ E và ft,v < ct,v, đặt nhãn lùi đỉnh t là (↓, v, min{β,ct,v - ft,v}).
Nếu (v,t) ∈ E và fv,t > 0, đặt nhãn lùi đỉnh t là (↓, v, min{β,fv,t})
Nếu t không được gán nhãn lùi, thì quay lại bước 3.2.
Nếu t được gán nhãn lùi và t có nhãn tiến, thì sang bước hiệu chỉnh tăng luồng 4.
Nếu t được gán nhãn lùi và t không có nhãn tiến, thì bổ sung t vào T', T':= T' ∪ {t}, và quay lại bước 3.2.

4. Hiệu chỉnh tăng luồng:

Ký hiệu t là đỉnh được gán nhãn tiến ở bước 2.2 hoặc nhãn lùi ở bước 3.2 để thuật toán dẫn đến bước 4. Giả sử t có nhãn tiến (↑, p, α) và nhãn lùi (↓, q, β). Đặt δ = min{α, β}.
Ta hiệu chỉnh luồng f như sau.
4.1. Hiệu chỉnh ngược từ t về a theo nhãn tiến.
4.1.1. Khởi tạo
    j:= t, i:= p
4.1.2. Hiệu chỉnh
Nếu cung (i,j) ∈ G, thì hiện chỉnh fij = fij + δ
Nếu cung (j,i) ∈ G, thì hiện chỉnh fji = fji - δ
4.1.3. Tịnh tiến
Nếu i = a, thì sang bước 4.2
Nếu i ≠ a, thì đặt j:= i và i:= h, với h là thành phần thứ hai của nhãn tiến đỉnh j.
Sau đó quay lại bước 4.1.2.
4.2. Hiệu chỉnh từ t đến z theo nhãn lùi
4.2.1. Khởi tạo
    i:= t, j:= q
4.2.2. Hiệu chỉnh
Nếu cung (i,j) ∈ G, thì hiện chỉnh fij = fij + δ
Nếu cung (j,i) ∈ G, thì hiện chỉnh fji = fji - δ
4.2.3. Tịnh tiến
Nếu i = z, thì sang bước 4.3.
Nếu i ≠ z, thì đặt i:= j và j:= k, với k là thành phần thứ hai của nhãn lùi đỉnh i.
Sau đó quay lại bước 4.2.2.
4.3. Xóa tất cả nhãn của các đỉnh trên mạng, trừ đỉnh nguồn a và đỉnh đích z, và quay lại bước 2.

Code luồng cực đại[sửa | sửa mã nguồn]

#include<iostream>
#include<deque>
#include<conio.h>
#define max 1001
using namespace std;
typedef struct node *ptr;
struct node
{       int data,cost;ptr pnext;
};
void chen(ptr &f,int v,int c)
{   ptr p = new node;
     p->data=v;
     p->cost=c;
     p->pnext=f;
     f=p; }
ptr a[max];
int c[max][max]; //ma trận biểu diễn khả năng tăng qua giữa các cung
int f[max][max]; //ma trận biểu diễn luồng trên các cung
int trace[max];  //lưu vết đường tăng luồng
int n,m,t,s;     //số đỉnh, số cạnh, đỉnh phát, đỉnh thu
int u,v, k;      //cập đỉnh u, v và khả năng thông qua của cập đỉnh này
int res=0;
deque<int>q;
void ReaderFile()
{       FILE * f;
        f = fopen("input.txt", "rt");
        if(f == NULL)
        {
                printf("\nKhong mo duoc file");
                exit(0);
        }
        fscanf (f,"%d%d%d%d",&n,&m,&s,&t);
        for (int i=1;i<=m;i++)
       {
       fscanf (f,"%d%d%d",&u,&v,&k);
       c[u][v]=k;
       chen(a[u],v,k);
       }fclose(f);
}
bool findpath()  // Tìm đường tăng luồng trên Gf. Trả về true nếu tìm thấy
{
    q.clear();                  // hàng đợi dùng cho BFS
    memset(trace,0,sizeof(trace));
    q.push_back(s);     
    trace[s]=n+1;               //tran(s) = 0 --> s chưa thăm
    while (q.size())
    {
          int u=q.front();
           q.pop_front();
          ptr p = a[u]; // lấy u ra khỏi hàng đợi
          while (p)
          {
                int v=p->data;
                if (!trace[v]&&c[u][v]>f[u][v]) //Xét với mọi v chưa thăm kề u trên Gf
                {
                   trace[v]=u;
                   if (v==t)                     // Đến lượt t thì thuật toán dừng
                        return true;
                   q.push_back(v);               // Đẩy v vào hàng đợi
                }
                p=p->pnext;
          }
    }
    return false; }
void incflow()  //Tăng luồng f
{    int u,v,delta=1000000000;
    v=t;
    while (v!=s)
    {
          u=trace[v];
          delta=min(delta,c[u][v]-f[u][v]); 
          v=u;     }
    v=t;
    while (v!=s)
    {
          u=trace[v];
          f[u][v]+=delta; //Nếu là cung thuận
          f[v][u]-=delta; //Nếu là cung nghịch
          v=u;     }
}
int main()
 {  ReaderFile();
    while (1)
    {     if (!findpath())
              break;
          incflow();    }
    for (int v=1;v<=n;v++)
        if (f[s][v]>0)               // chỉ quan tâm đến những cung có luồng dương
            res+= f[s][v];      
   printf ("%d",res);           //Xuất luồng cực đại
   getch();
   return 0; }


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

Trần Quốc Chiến, Thuật toán hoán chuyển nguồn đích có trọng sốtìm luồng cực đại. Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng, 3(26)/2008

Trần Quốc Chiến, Nguyễn Thanh Tuấn, Phương pháp kéo luồng sau tìm luồng cực đại. Hội thảo khoa học 30 năm Trường Đại học Sưphạm - Đại học Đà Nẵng, 11-2005.

Book - Bookmarks, Đại học sư phạm Hà Nội 1999 - 2004

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

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

Phương tiện liên quan tới Ford-Fulkerson's algorithm tại Wikimedia Commons