Bài toán luồng

I / Một số khái niệm :
Định nghĩa mạng :
Mạng là đồ thị có hướng G(V,E) , V là tập đỉnh , E là tập cung thoả mãn các điều kiện sau đây :
+ Tồn tại duy nhất 1 đỉnh S không có cung vào ( bán bậc vào bằng 0 )
+ Tồn tại duy nhất 1 đỉnh T không có cung ra ( bán bậc ra bằng 0 )
+ Mỗi cung e thuộc E tương ứng với 1 số không âm A(e)

Định nghĩa luồng :
Cho mạng G(V,E) với ma trận trọng số A .
Luồng là 1 ánh xạ F từ tập cung E vào tập số thực
F : E ---> R
e ---> F(e)
thoả mãn các tính chất sau đây :
+ F(e) ( 0 ( e
+ A(e) ( F(e) ( e
+ W(i) = ( F(e+) - ( F(e-) = 0 ( đỉnh i khác S và T ( e+ là mọi cung ra khỏi đỉnh i , e- là mọi cung đi tới i ) . Ngoài ra nếu đặt W(S) = W thì W(T) = -W.

W(i) gọi là thông lượng của luồng tại đỉnh i .
F(e) gọi là giá trị của luồng trên cung e .
W là giá trị của luồng .

II / Bài toán luồng thứ nhất :

1 ) Bài toán : Tìm luồng có giá trị lớn nhất ( giá trị W ) trong tất cả các luồng xác định trên mạng .
2 ) ý nghĩa thực tế : Tìm lưu lượng lớn nhất của hàng hoá vận chuyển trên mạng giao thông .
3 ) Thuật toán : Dựa trên định lý của Ford Fulkerson “ giá trị của luồng cực đại bằng khả năng thông qua của lát cắt hẹp nhất “ . người ta xây dựng thuật toán tìm luồng cực đại .

Trước hết ta định nghĩa nhãn của các đỉnh i như sau
+ Nhãn của đỉnh i là i (+j , v ) nghĩa là : có thể tăng giá trị luồng trên cung (j,i) một lượng không vượt quá v
+ Nhãn của đỉnh i là i (-j,v) nghĩa là : có thể giảm giá trị của luồng trên cung (i,j) một lượng không vượt quá v .

Để thực hiện thuật toán , người ta xử dụng các động tác sau :

* Khởi trị : tạo 1 luồng ban đầu trên mạng ( có thể chọn luồng tầm thường là F sao cho F(e) = 0 ( e . Giá trị của luồng là W=0
Đầu tiên tất cả các đỉnh chưa có nhãn , và đánh dấu là chưa xét
Gán nhãn S(+S, ( ) . Cho S vào stack .

* Sửa nhãn : dùng đỉnh j ( j lấy từ đỉnh stack ) để sửa nhãn cho các đỉnh i chưa đánh dấu và i kề với j :

Giả sử nhãn đỉnh j (+k,v) hoặc j(-k,v) .

+ Nếu cung (j,i) ( E , F[j,i] < A[j,i] thì nhãn mới của i là i(+j,v0) ,
ở đây v0 = Min ( v, A[j,i]-F[j,i] )
+ Nếu cung (i,j) ( E , F[i,j] >0 thì nhãn mới của i là i(-j,v0 ),
ở đây v0 = Min ( v, F[j,i] )

Sửa xong nhãn thì cho đỉnh i vào stack

Cuối cùng , sau khi tất cả các đỉnh i được sửa nhãn , ta đá