Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 6: Bài toán luồng cực đại - Nguyễn Đức Nghĩa
Chương 6
Bài toán luồng cực đại
Maximum Flow Problem
c
v
3/3
4/6
1/1
t
4/7
1/9
3/3
s
w
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
c
v
3/3
4/6
1/1
t
4/7
1/9
3/3
s
w
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
3
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
4
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
5
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.
❖In 1979, the renowned Fulkerson Prize was established
which is now awarded every three years for outstanding
papers in discrete mathematics jointly by the
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
6
Network Flows
Ravindra K. Ahuja, Thomas Magnanti and James Orlin. Network
Flows. Prentice Hall, 1993.
1 1
4
2
1
2
1
2
s
t
3
1
2
3
864 pages!
1 1
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
2008/5/2
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
8
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
3
6
1
t
7
9
3
s
w
5
1
5
z
u
2
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
9
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)
eE− (v)
eE+ (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.
Định nghĩa. Giá trị của luồng f là
(*)
val( f ) =
f (e) =
f (e)
eE+ (s)
eE− (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
10
LUỒNG TRONG MẠNG – Ví dụ
Ví dụ:
v
1/3
2/6
1/1
t
3/7
2/9
3/3
s
w
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
11
Bài toán luồng cực đại
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
v
1/3
2/6
1/1
t
3/7
2/9
3/3
s
w
Bài toá n tì m luồng cực đại
trong mạng G được gọi là bài
toá n luồng cực đại
4/5
1/1
3/5
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
2/9
3/3
s
w
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
12
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
9
10
5
15
15
10
4
3
s
6
t
8
6
10
10
15
4
15
Capacity
4
7
30
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
13
Luồng
Luồng từ s đến t là hàm f: E → R thoả mãn:
Với mỗi e E:
0 f(e) c(e)
(hạn chế kntq)
Với mỗi v V – {s, t}:
(cân bằng luồng)
f (e) =
f (e)
e vµo v
e ra khái v
f (e) :=
f (v,w)
f (e) :=
f (w,v)
eE+ (v)
eE- (v)
w:(v,w)E
w:(w,v)E
0
9
2
5
4
10
0
10
0
15
0
15
4
3
4
0
5
4
10
4
8
s
6
t
0
6
0
10
15 0
kntq
Capacity
4
0
15
0
Luồng
Flow
4
7
30
0
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
14
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 ) = f (e) = f (e)
eE+ (s)
eE− (t)
0
9
2
5
4
10
0
10
0
15
15
0
4
3
4
0
5
4
10
4
8
s
6
t
0
6
0
10
kntq
15 0
4
0
15
0
Giá trị = 4
Luồng
4
7
30
0
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
15
Luồng
Luồng có giá trị 24 trong mạng:
6
9
2
5
10
10
6
10
0
15
15
0
4
3
4
3
5
8
10
8
8
s
6
t
1
6
10
10
15 0
4
0
15
11
kntq
Giá trị = 24
Luồng
4
7
30
11
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
16
Luồng
Luồng có giá trị 28 trong mạng:
9
9
2
5
10
10
9
10
1
15
15
0
4
3
0
4
5
9
10
8
8
s
6
t
4
6
10
10
15 0
4
0
15
14
kntq
Giá trị = 28
Luồng
4
7
30
14
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
17
Luồng trong mạng
Mạng
Đỉnh
Cung
Luồng
trạm giao dịch,
máy tính, vệ tinh
cáp nối, cáp quang,
voice, video,
packets
truyền thông
cổng, registers,
processors
mạng điện
cơ khí
dây dẫn
dòng điện
joints
rods, beams, springs heat, energy
hồ chứa, trạm bơm,
nguồn nước
dòng nước,
đường ống
thuỷ lợi
chất lỏng
tài chí nh
nhà băng
giao dịch
tiền
hàng hoá ,
phương tiện,
hành khá ch
sâ n bay, ga tàu,
giao lộ
đường cao tốc, ray,
đường bay
giao thô ng
hoá học
sites
bonds
energy
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
18
Luồng trong mạng
Mạng
Đỉnh
Cung
Luồng
telephone exchanges, cables, fiber optics,
computers, satellites microwave relays
voice, video,
packets
communication
gates, registers,
wires
circuits
current
processors
mechanical
joints
rods, beams, springs heat, energy
reservoirs, pumping
stations, lakes
hydraulic
financial
pipelines
fluid, oil
money
stocks, currency
transactions
freight,
vehicles,
passengers
airports, rail yards,
street intersections
highways, railbeds,
airway routes
transportation
chemical
sites
bonds
energy
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
19
Các ứng dụng/qui dẫn
Network connectivity.
Network reliability.
Bipartite matching.
Data mining.
Security of statistical data.
Distributed computing.
Egalitarian stable matching.
Distributed computing.
Many many more . . .
Open-pit mining.
Airline scheduling.
Image processing.
Project selection.
Baseball elimination.
Toán rời rạc – Fall 2005
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
20
Tải về để xem bản đầy đủ
83 trang
27460
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 6: Bài toán luồng cực đại - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_phan_2_ly_thuyet_do_thi_chuong_6_bai.ppt
