Bài giảng môn Lý thuyết đồ thị - Chương 6: Bài toán luồng cực đại

Chương 6

Bài toán luồng cực đại

Maximum Flow Problem

v

3/3

4/6

1/1

t

4/7

3/3

s

w

1/9

3/5

1/1

3/5

z

u

2/2

BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • Nguyễn Đức Nghĩa

Bài toán luồng cực đại Maximum Flow Problem

v

3/3

4/6

1/1

t

4/7

3/3

s

w

1/9

3/5

1/1

3/5

z

u

2/2

BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • Nguyễn Đức Nghĩa

NỘI DUNG

 Bài toán luồng cực đại trong mạng.

 Lát cắt, Đường tăng luồng.

 Định lý về luồng cực đại và lát cắt hẹp nhất.

 Thuật toán Ford-Fulkerson

 Thuật toán Edmond-Karp.

 Các ứng dụng

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

L. R. Ford; D. R. Fulkerson (1962). Flows in Networks. Princeton, NJ: Princeton University Press.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Lester Randolph Ford, Jr (1927 ~)

Lester Randolph Ford, Jr. (born September 23, 1927), son of Lester R. Ford, Sr., is an American mathematician specializing in network flow programming. His 1956 paper with D. R. Fulkerson on the maximum flow problem established the maxflow-mincut theorem.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Delbert Ray Fulkerson (August 14, 1924 - January 10, 1976)

Delbert Ray Fulkerson was a mathematician who co- developed the Ford-Fulkerson algorithm, one of the most used algorithms to compute maximal flows in networks. Ph.D, Univ. of Wisconsin-Madison, 1951.

In 1956, he published his famous paper on the Ford- Fulkerson algorithm together with Lester Randolph Ford.

discrete mathematics

jointly

In 1979, the renowned Fulkerson Prize was established which is now awarded every three years for outstanding the papers Mathematical Programming Society and the American Mathematical Society.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Network Flows

Ravindra K. Ahuja, Thomas Magnanti and James Orlin. Network Flows. Prentice Hall, 1993.

s

t

864 pages!

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Mạng và luồng trong mạng

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

MẠNG (Network)

Mạng là đồ thị có hướng G = (V,E) :  Có duy nhất một đỉnh s không có cung đi vào gọi là đỉnh phát (nguồn) và duy nhất một đỉnh t không có cung đi ra gọi là đỉnh thu (đích).

 Mỗi cung e của G được gắn với một số không âm

c(e) được gọi là khả năng thông qua của e.

Ví dụ:

v

t

s

w

z

u

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

LUỒNG TRONG MẠNG

Định nghĩa. Luồng f trong mạng G=(V,E) là phép gán số f(e) cho mỗi cạnh e ( f(e) được gọi là luồng trên cạnh e) thoả mãn các điều kiện:

1) Hạn chế về khả năng thông qua (Capacity Rule):

Với mỗi cung e, 0  f (e)  c(e)

2) Điều kiện cân bằng luồng (Conservation Rule): Với mỗi v s, t

f e ( )



f e ( )



-  e E v ( )

+  e E v ( )

trong đó E-(v) và E+(v) tương ứng là tập các cung đi vào và đi ra khỏi đỉnh v.

f e ( )

val

(*) 



(

)

f e ( )

Định nghĩa. Giá trị của luồng f là 



+  e E s ( )

-  e E t ( )

(Đẳng thức (*) thu được bằng cách cộng tất cả các điều kiện cân bằng luồng.)

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

LUỒNG TRONG MẠNG – Ví dụ

Ví dụ:

v

1/3

2/6

1/1

t

3/7

3/3

s

w

2/9

4/5

1/1

3/5

z

u

2/2

 Trong 2 số viết bên mỗi cạnh: giá trị luồng trên cạnh là số màu

đỏ, số còn lại là khả năng thông qua.

 Các điều kiện 1) và 2) được thoả mãn => f là luồng trên mạng.

 Giá trị luồng là:

8 = f(s,v) + f(s,u) + f(s,w) = f(v,t) + f(w,t) + f(z,t)

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Bài toán luồng cực đại

v

1/3

2/6

Luồng trong mạng G được gọi là luồng cực đại nếu trong số tất cả các luồng trong mạng G nó là luồng có giá trị lớn nhất

1/1

t

3/7

3/3

s

w

2/9

4/5

1/1

3/5

toán tìm luồng cực đại Bài trong mạng G được gọi là bài toán luồng cực đại

z

u

2/2

Luồng với giá trị 8 = 2 + 3 + 3 = 1 + 3 + 4

v

3/3

4/6

1/1

t

3/7

3/3

s

w

2/9

4/5

1/1

3/5

z

u

2/2

Luồng cực đại có giá trị 10 = 4 + 3 + 3 = 3 + 3 + 4

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Mạng

Mạng: G = (V, E, s, t, c) .



(V, E) = đồ thị có hướng, không có cung lặp.

 Có hai đỉnh đặc biệt: s = phát/nguồn (source), t = thu/đích (sink).

 c(e) = khả năng thông qua (capacity) của cung e.

2

5

10 15 15 10 4

3

6 t

s

5 8 10

15 4 6 10 15

Capacity

4

7 Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Luồng

(hạn chế kntq)

 Với mỗi e  E:

f e ( )

(cân bằng luồng)

 Với mỗi v  V – {s, t}:

Luồng từ s đến t là hàm f: E  R thoả mãn: 0  f(e)  c(e)  



-  e E v ( )

+  e E v ( )

f e

( ) :



f v w ( , )

f e

( ) :



f w v , ) (



w v w : ( ,

)



w w v : ( , )



+  e E v ( )

(

-  e E v

)

2

5

0 9

4 10 15 0 15 0 0 10 4 4

3 s

6 t

0 5 4 8 4 10

15 0 4 0 0 6 0 10

kntq Capacity

15 0

7

4 NGUYỄN ĐỨC NGHĨA

Luồng Toán rời rạc – Fall 2005 Flow

30 0

Bộ môn KHMT

Luồng

Bài toán luồng cực đại: Tìm luồng có tổng luồng trên các cạnh đi ra khỏi đỉnh phát là lớn nhất:

val

(

)



f e ( )



f e ( )



+ ( e E s 

)

-  e E t ( )

2

5

0 9

4 10 15 0 15 0 0 10 4 4

3

6 t

s

0 5 4 8 4 10

kntq

15 0 4 0 0 6 0 10

Giá trị = 4

15 0

Luồng

4

7 Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

30 0

Bộ môn KHMT

Luồng

Luồng có giá trị 24 trong mạng:

2

5

6 9

10 10 15 0 15 0 6 10 4 4

3 s

6 t

3 5 8 8 8 10

15 0 4 0 1 6 10 10

kntq

Giá trị = 24

15 11

Luồng

4

7

30 11

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Luồng

Luồng có giá trị 28 trong mạng:

2

5

9 9

10 10 15 1 15 0 9 10 4 0

3 s

6 t

4 5 8 8 9 10

15 0 4 0 4 6 10 10

kntq

Giá trị = 28

15 14

Luồng

4

7

30 14

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Luồng trong mạng

Mạng

Đỉnh

Cung

Luồng

cáp nối, cáp quang,

truyền thông

voice, video, packets

trạm giao dịch, máy tính, vệ tinh

mạng điện

dây dẫn

dòng điện

cổng, registers, processors

cơ khí

joints

rods, beams, springs

heat, energy

thuỷ lợi

đường ống

hồ chứa, trạm bơm, nguồn nước

dòng nước, chất lỏng

tài chính

nhà băng

giao dịch

tiền

giao thông

sân bay, ga tàu, giao lộ

đường cao tốc, ray, đường bay

hàng hoá, phương tiện, hành khách

hoá học

sites

bonds

energy

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Luồng trong mạng

Mạng

Đỉnh

Cung

Luồng

communication

telephone exchanges, computers, satellites

cables, fiber optics, microwave relays

voice, video, packets

circuits

wires

current

gates, registers, processors

mechanical

joints

rods, beams, springs

heat, energy

hydraulic

pipelines

fluid, oil

reservoirs, pumping stations, lakes

financial

stocks, currency

transactions

money

transportation

airports, rail yards, street intersections

highways, railbeds, airway routes

freight, vehicles, passengers

chemical

sites

bonds

energy

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Các ứng dụng/qui dẫn

 Network connectivity.

 Network reliability.

 Bipartite matching.

 Security of statistical data.

 Data mining.

 Distributed computing.

 Open-pit mining.

 Egalitarian stable matching.

 Airline scheduling.

 Distributed computing.



Image processing.

 Many many more . . .

 Project selection.

 Baseball elimination.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Lát cắt – Đường tăng luồng

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Lát cắt (Cuts)

Lát cắt là cách phân hoạch tập đỉnh (S, T) sao cho s  S, t  T.  Khả năng thông qua cap(S,T) của lát cắt (S, T) là số:

Lát cắt nhỏ nhất (hẹp nhất) là lát cắt với kntq nhỏ nhất.

2

5

10 15 15 10 4

s

t

3

6

5 8 10

15 4 6 10 15

kntq = 30

4

7 Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Lát cắt

Lát cắt (S1, T1), S1={s,2,3,4}, T={5,6,7,t) có khả năng thông qua 62:

2

5

10 15 15 10 4

s

t

3

6

5 8 10

15 4 6 10 15

cap(S1,T1)= 62

4

7 Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Lát cắt

Lát cắt (S2, T2), S2={s,3,4,7}, T2={2,5,6,t) có khả năng thông qua 28:

2

5

10 15 15 10 4

s

t

3

6

5 8 10

15 4 6 10 15

cap(S2,T2) = 28

4

7 Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Luồng và lát cắt

f e ( )

val

e ( )



(

)

Bổ đề 1. Giả sử f là luồng, và (S, T) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng: 



  e S T

  e T

+ e E s ( )

trong đó S  T = {(v,w)E: vS, wT} và T S = {(v,w)E: vT, w S}

2

5

6 9

Giá trị = 24

10 10 15 0 15 0 6 10 4 4

s

3

6 t

4 5 8 8 8 10

15 0 4 0 0 6 10 10

15 10

4

7 Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

30 10

Bộ môn KHMT

Luồng và lát cắt

Bổ đề 1. Giả sử f là luồng, và (S, T) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng:

2

5

6 9

Giá trị = 24

10 10 15 0 15 0 6 10 4 4

s

3

6 t

4 5 8 8 8 10

15 0 4 0 0 6 10 10

15 10

4

7

30 10

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Luồng và lát cắt

Bổ đề 1. Giả sử f là luồng, và (S, T) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng:

2

5

6 9

Giá trị = 24

10 10 15 0 15 0 6 10 4 4

s

3

6 t

4 5 8 8 8 10

15 0 4 0 0 6 10 10

15 10

4

7

30 10

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Luồng và lát cắt

f e ( )



f e ( )



val

(

)



  e S T

  e T

Chứng minh bổ đề: Giả sử f là luồng còn (S, T) là lá cắt. Khi đó

+ e E s  ( ) CM. Cộng tất cả các ràng buộc cân bằng luồng theo mọi vS, đơn giản biểu thức ta thu được:



f e ( )

f e

( ))

  (



 v S

+  e E v ( )

-  e E v ( )



f e ( )



  e S T

  e T

+  e E s ( )

  

  

v u t

tổng theo các cung xanh

tổng theo các cung tím

S

T

từ đó suy ra đẳng thức cần chứng minh

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Luồng và lát cắt

Bổ đề 2. Giả sử f là luồng, còn (S, T) là lát cắt. Khi đó, val(f) cap(S, T).

val

(

)

f e ( )





  e T

  e S T

CM.

S

T



f e ( )

  e S T



c e ( )

  

4 8 t



  e S T cap( ,

S T

)

7 6

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Luồng cực đại và lát cắt nhỏ nhất Max Flow and Min Cut

Hệ quả. Giả sử f là luồng, còn (S, T) là lát cắt. Nếu val(f) = cap(S, T), thì f là luồng cực đại còn (S, T) là lát cắt hẹp nhất. CM. Xét f’ là luồng bất kỳ và (S’,T’) là lát cắt bất kỳ. Theo bổ đề ta có

val(f’)  cap(S,T) = val(f)  cap(S’,T’).

2

5

9 9

10 10 15 1 15 0 9 10 4 0

s

t

3

6

4 5 8 8 9 10

15 0 4 0 4 6 10 10

15 14

4

7

30 14

Giá trị luồng = 28

kntq của lát cắt = 28

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Định lý về luồng cực đại và lát cắt nhỏ nhất Max-Flow Min-Cut Theorem

Đinh lý (Ford-Fulkerson, 1956): Trong mạng bất kỳ, giá trị của luồng cực đại luôn bằng khả năng thông qua của lát cắt nhỏ nhất.

 Proof (muộn hơn).

2

5

9 9

10 10 15 1 15 0 9 10 4 0

s

t

3

6

4 5 8 8 9 10

15 0 4 0 4 6 10 10

15 14

4

7

30 14

Flow value = 28

Cut capacity = 28

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Ý tưởng thuật toán

Thuật toán tham lam:

 Bắt đầu từ luồng 0 (Luồng có giá trị = 0).

 Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e).

 Tăng luồng dọc theo đường đi P.

 Lặp lại cho đến khi gặp bế tắc.

4

5

0 4

0 4 0 4

0 4

s

2

3 t

0 10 0 13 0 10

Luồng có giá trị = 0

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Ý tưởng thuật toán

Thuật toán tham lam:

 Bắt đầu từ luồng 0 (Luồng có giá trị = 0).

 Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e).

 Tăng luồng dọc theo đường đi P.

 Lặp lại cho đến khi gặp bế tắc.

4

5

0 4

0 4 0 4

0 4 10 10 10

2 s

3 t

X 0 10 X 0 13 X 0 10

Giá trị luồng = 10

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Ý tưởng thuật toán

Thuật toán tham lam:

 Bắt đầu từ luồng 0 (Luồng có giá trị = 0).

 Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e).

 Tăng luồng dọc theo đường đi P.

 Lặp lại cho đến khi gặp bế tắc.

4

5

0 4

0 4 0 4

0 4

s

2

3 t

10 10 10 13 10 10

Thuật toán tham lam cho luồng với giá trị 10.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Ý tưởng thuật toán

Thuật toán tham lam không cho lời giải tối ưu.

TT tham lam: Giá trị luồng = 10

4

5

0 4

0 4 0 4

0 4

2 s

t

3

10 10 10 13 10 10

Tối ưu: Giá trị luồng = 14

4

5

4 4

4 4 4 4

4 4

2 s

t

3

10 10 6 13 10 10

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

ĐỒ THỊ TĂNG LUỒNG- ĐƯỜNG TĂNG LUỒNG

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Đồ thị tăng luồng – Tập cung

kntq

 Cung e = (v, w)  E.

Mạng đã cho G = (V, E).  Luồng f(e), e  E.

v

w

17

6 Luồng

Kntq

w

v

11

Đồ thị tăng luồng: Gf = (V, Ef ).  “thu lại" luồng đã gửi.  Ef = {e: f(e) =0 0 }.  Khả năng thông qua

6 Kntq

e = (u,v)  eR = (v,u)

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Đồ thị tăng luồng - Ví dụ

Đồ thị tăng luồng: Gf = (V, Ef ).  Ef = {e : f(e) < c(e)}  {eR : f(e) > 0}.  cf(e) cho biết lượng lớn nhất có thể tăng luồng trên cung e.  cf(eR) cho biết lượng lớn nhất có thể giảm luồng trên cung e.

4

5

0 4

G

0 4

s

2

3 t

10 10 10 13 10 10

4

5

4 4

Gf

s

2

3 t

10 10 10

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Đường tăng luồng

Đường tăng luồng = đường đi từ s đến t trên đồ thị tăng luồng Gf. Khả năng thông qua của đường đi P là

cf (P) = min {cf (e): e  P }.

4

5

4 0 X 4 4 0 X 4

G

0 X 4 4

0 X 4 6

s

2

3 t

10 10 10 X 13 10 10

4

5 cf (P) = 4

4 4

Gf

s

2

3 t

10 10 10

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Đường tăng luồng

Đường tăng luồng = đường đi từ s đến t trên đồ thị tăng luồng.  Luồng là cực đại  không tìm được đường tăng luồng???

4

5

4 4

G

4 4

s

2

3 t

10 10 6 13 10 10

4

5 Giá trị luồng = 14

4 4

Gf

s

2

3 t

10 6 10

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Định lý về luồng cực đại và lát cắt nhỏ nhất

Định lý đường tăng luồng (Ford-Fulkerson, 1956): Luồng là cực đại khi và chỉ khi không tìm được đường tăng luồng.

Định lý về luồng cực đại và lát cắt nhỏ nhất (Ford-Fulkerson, 1956): Giá trị của luồng cực đại bằng khả năng thông qua của lát cắt nhỏ nhất.

Ta sẽ chứng minh định lý tổng hợp sau:

Định lý. Giả sử f là luồng trong mạng. Ba mệnh đề sau là tương đương

Tìm được lát cắt (S, T) sao cho val(f) = cap(S, T).

(i)

(ii)

f là luồng cực đại.

(iii) Không tìm được đường tăng luồng f.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Thuật toán Ford-Fulkerson:

Để tìm luồng cực đại của mạng vận tải G, ta xuất phát từ luồng tuỳ ý ϕ của G, rồi nâng luồng lên đầy, sau đó áp dụng thuật toán Ford-Fulkerson. Thuật toán gồm 3 bước: Bước 1 (đánh dấu ở đỉnh của mạng):Lối vào v0

được đánh dấu bằng 0.

Nếu đỉnh vi đã được đánh dấu thì ta dùng chỉ số +i để đánh dấu cho mọi đỉnh y chưa được đánh dấu mà (vi,y)∈E và cung này chưa bão hoà (ϕ(vi,y)

Nếu đỉnh v+ đã được đánh dấu thì ta dùng chỉ số −i để đánh dấu cho mọi đỉnh z chưa được đánh dấu mà (z,vi)∈E và luồng của cung này dương (ϕ(z,vi)>0).

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Thuật toán Ford-Fulkerson:

Nếu với phương pháp này ta đánh dấu được tới lối ra vn thì trong G tồn tại giữa v0 và vn một xích α, mọi đỉnh đều khác nhau và được đánh dấu theo chỉ số của đỉnh liền trước nó (chỉ sai khác nhau về dấu). Khi đó chắc chắn ta nâng được giá trị của luồng.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Thuật toán Ford-Fulkerson:

Bước 2 (nâng giá trịcủa luồng): Đểnâng giá trịcủa

luồng ϕ, ta đặt:

ϕ’(e) = ϕ(e), nếu e∉α ϕ’(e) = ϕ(e)+1, nếu e∈α được định hướng theo

chiều của xích α đi từ vo đến vn

ϕ’(e) = ϕ(e)−1, nếu e∈α được định hướng ngược

với chiều của xích α đi từ vo đến vn

ϕ’ thoả mãn các điều kiện về luồng, nên ϕ’ là một

luồng và ta có: ϕ’n= ϕn+1.

Như vậy, ta đã nâng được luồng lên một đơn vị. Sau đó lặp lại một vòng mới. Vì khả năng thông

qua của các cung đều hữu hạn, nên quá trình phải dừng lại sau một số hữu hạn bước.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Thuật toán Ford-Fulkerson:

Bước 3: Nếu với

luồng ϕ0 bằng phương pháp trên ta không thể nâng giá trị của luồng lên nữa, nghĩa là ta không thể đánh dấu được đỉnh vn, thì ta nói rằng quá trình nâng luồng kết thúc và ϕ0 đã đạt giá trịcực đại, đồng thời gọi ϕ0 là luồng kết thúc.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Thuật toán Ford – Fulkerson

Tăng luồng f dọc theo đường tăng P

Augment(f,P) b  cf(P) FOR e  P DO

IF (e  E) THEN // cạnh thuận

Ví dụ

f(e)  f(e) + b

ELSE

// cạnh nghịch

f(eR)  f(e) – b

RETURN f

Thuật toán Ford-Fulkerson

Ford_Fulkerson(G,c,s,t); FOR e  E DO // Khởi tạo luồng 0

f(e)  0

Gf  đồ thị tăng luồng f

WHILE (tìm được đường tăng luồng P) DO

f  augment(f, P) Sửa lại Gf

RETURN f

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Ví dụ:

 Cho mạng vận tải như hình dưới đây với khả năng thông qua được đặt trong khuyên tròn, luồng được ghi trên các cung. Tìm luồng cực đại của mạng này.

Toán rời rạc – Fall 2005

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT

Giải:

 Mạng vận tải G có đỉnh phát là V0 và đỉnh thu

là V8.

 Luồng ϕ có đường đi (v0,v4), (v4,v6), (v6,v8) gồm các cung chưa bão hoà nên nó chưa đầy. Do đó có thể nâng luồng của các cung này lên một đơn vị, để được ϕ1