Chương này trình bày một số ứng dụng của bài toán luồng cực đại như: Bài toán với nhiều điểm phát và điểm thu, bài toán với hạn chế thông qua ở nút, bài toán cặp ghép cực đại trong đồ thị hai phía, độ tin cậy của mạng. Mời các bạn cùng tham khảo.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 6 (tt) - Nguyễn Đức Nghĩa
- Các ứng dụng của
Bài toán luồng cực đại
BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • NGUYỄN ĐỨC NGHĨA
- Max Flow Applications
s
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
t Bộ môn KHMT 2
- NỘI DUNG
Một số bài toán luồng tổng quát
– Bài toán với nhiều điểm phát và điểm thu
– Bài toán với hạn chế thông qua ở nút
Một số ứng dụng trong tổ hợp
– Bài toán cặp ghép cực đại trong đồ thị hai phía
– Độ tin cậy của mạng
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 3
- Một số bài toán luồng tổng quát
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 4
- M¹ng víi nhiÒu ®iÓm ph¸t vµ ®iÓm thu
XÐt m¹ng G víi p ®iÓm ph¸t s 1 , s 2 ,..., s p v ới lượ ng ph¸t là a 1 ,
a 2 , ..., a p vµ q ®iÓm thu t 1 , t 2 ,..., t q v ới lượng thu là b 1 , b 2 , ..., b q
Gi¶ s ö r»ng luång c ã thÓ ®i tõ mé t ®iÓm ph¸t bÊt kú ®Õn tÊt c ¶
c ¸c ®iÓm thu.
T×m luång c ùc ®¹i tõ c ¸c ®iÓm ph¸t ®Õn c ¸c ®iÓm thu
s1 t1
s2 t2
sp tq
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 5
- M¹ng víi nhiÒu ®iÓm ph¸t vµ ®iÓm thu
Đa vµo mé t ®iÓm ph¸t g i¶ s vµ mé t ®iÓm thu g i¶ t vµ c ¸c c ¹nh nè i s víi
tÊt c ¶ c ¸c ®iÓm ph¸t vµ c ¸c c ¹nh nè i c ¸c ®iÓm thu víi t.
Kntq c ña c ung (s ,s i) s Ï b»ng a i là lîng ph¸t c ña s i.
Kntq c ña (t i, t) s Ï b ằng b i là lîng thu c ña ®iÓm thu t i.
Bài to ¸n d ẫn v ề bài to ¸n v ới 1 điểm ph¸t và m ột điểm thu.
s1 t1
a1 b1
s2 t2
a2 b2 t
s
ap bq
sp tq
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 6
- Bài toán với hạn chế thông qua ở nút
Gi¶ s ö tro ng m¹ng G, ng o µi kh¶ n¨ng th«ng qua c ña
c ¸c c ung c (u, v ), ë mç i ®Ønh v ˛ V 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 vît qu¸ d (v ), tø c lµ
du
f(w,v) d(v).
w V 5 u 4 dt
ds
s 1 t
2 3
v
dv
• T×m luång c ùc ®¹i từ s đ ến t tro ng m¹ng G.
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 7
- Bài toán với hạn chế thông qua ở nút
X©y dùng mé t m¹ng G' s ao c ho : mç i ®Ønh v c ña G t¬ng ø ng víi
2 ®Ønh v +, v tro ng G', mç i c ung (u, v ) tro ng G ø ng víi c ung (u,
v +) tro ng G', mç i c ung (v ,w ) tro ng G ø ng víi c ung (v , w +) tro ng
G'. Ng o µi ra, mç i c ung (v +, v ) tro ng 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 tro ng G.
du
du u+ u-
5 4
5 u 4 dt
ds ds dt
1
s 1 t s+
s
- t+
t-
2 3 dv
v 2
v+
v- 3
dv
Qui về bài toán tìm luồng cực đại trong G’
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 8
- Các ứng dụng của bài toán luồng cực đại
ỨNG DỤNG TRONG TỔ HỢP
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 9
- Bài toán ghép cặp
(Matching Problems)
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 10
- Cặp ghép (Matching)
Cho G = (V, E) là đồ thị vô hướng.
Cặp ghép trong đồ thị G là tập các cạnh của đồ thị đôi một không
có đỉnh chung
Bài toán cặp ghép cực đại : Tìm cặp ghép với lực lượng lớn nhất
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 11
- Bài toán cặp ghép cực đại trên đồ thị hai phía
Đồ thị vô hướng G=(V,E)
là hai phía nếu V có thể 1 6
phân hoạch thành 2 tập
X và Y sao cho mỗi cạnh
e E đều có thể biểu diễn 2 7
e=(x, y) với x X và y Y.
Cặp ghép là tập các 3 8
cạnh đôi một không có
đỉnh chung.
4 9
Bài toán cặp ghép cực đại :
Tìm cặp ghép có lực lượng
lớn nhất 5 10
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 12
- Qui dẫn về bài toán luồng cực đại
Xây dựng mạng G’ 1 6 Mỗi cung (j, t)
có kntq là 1.
1
2 7
s 3 8 t
1 4 9
Mỗi cung (s, i)
có kntq là 1. 5 ∞ 10
Mỗi cạnh (x,y)
thay bởi cung
Toán rời rạc – Fall 2005 (x,y) với kntq +∞. NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 13
- Tìm luồng cực đại
1 6
2 7
s 3 8 t
4 9
5 10
Giá trị luồng cực đại từ s đến t là 4.
Cặp ghép cực đại có lực lượng là 4.
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 14
- Bipartite Matching: Tính đúng đắn
Đinh lý. Lực lượng của cặp ghép cực đại trong G = giá trị của luồng
cực đại trong G'.
CM. Chỉ cần chứng minh G có cặp ghép lực lượng k khi và chỉ khi G’
có luồng với giá trị k.
) Cho cặp ghép M có lực lượng k.
Xét luồng f đẩy luồng 1 đơn vị dọc theo mỗi một trong k đường đi.
f là luồng có giá trị k. ■
1 1' 1 1'
1 1
2 2' 2 2'
3 3' s 3 3' t
4 4' 4 4'
G G'
5 5' 5 5'
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 15
- Bipartite Matching: Tính đúng đắn
) Cho f là luồng giá trị k trong G'.
Từ định lý về tính nguyên tìm được luồng nguyên: f(e) chỉ là 0
hoặc 1.
Gọi M = tập các cạnh e từ X sang Y với f(e) = 1.
– mỗi đỉnh trong X và Y là đầu mút của một cạnh trong M
– |M| = k, do luồng có giá trị k nên có đúng k cạnh từ X sang Y với
giá trị luồng trên cung là 1 ■
1 1' 1 1'
1 1
2 2' 2 2'
s 3 3' t 3 3'
4 4' 4 4'
G' G
5 5' 5 5'
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 16
- Cặp ghép hoàn hảo (Perfect Matching)
ĐN. Cặp ghép M E được gọi là hoàn hảo (perfect) nếu mỗi
đỉnh của đồ thị là đầu mút của đúng 1 cạnh trong M.
Câu hỏi. Khi nào đồ thị hai phía có cặp ghép hoàn hảo?
Cấu trúc của đồ thị hai phía có cặp ghép hoàn hảo.
Rõ ràng ta phải có |X| = |Y|.
Điều kiện nào là cần nữa?
Các điều kiện đủ là gì?
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 17
- Cặp ghép hoàn hảo
Ký hiệu. Gỉa sử S là tập con các đỉnh, ký hiệu (S) là tập các đỉnh kề
với các đỉnh trong S.
Nhận xét. Nếu đồ thị hai phía G = (X Y, E) có cặp ghép hoàn hảo, thì
| (S)| |S| với mọi tập con S X.
CM. Hai đỉnh bất kỳ trong S gắn với hai đỉnh khác nhau trong (S).
1 1'
2 2'
Không có cặp ghép hoàn hảo:
3 3'
S = { 2, 4, 5 }
(S) = { 2', 5' }.
4 4'
X 5 5' Y
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 18
- Định lý về các đám cưới (Marriage Theorem)
Marriage Theorem. [Frobenius 1917, Hall 1935] Giả sử G = (X Y, E)
là đồ thị hai phía với |X| = |Y|. Khi đó, G có cặp ghép hoàn hảo khi và
chỉ khi | (S)| |S| với mọi tập con S X.
CM. ) Vừa chứng minh ở trên.
1 1'
2 2'
Không có cặp ghép hoàn
3 3'
hảo:
S = { 2, 4, 5 }
4 4'
(S) = { 2', 5' }.
X 5 5' Y
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 19
- Chứng minh định lý về các đám cưới
CM. ) Giả sử G không có cặp ghép hoàn hảo.
Xét bài toán luồng cực đại tương ứng và (A, B) là lát cắt nhỏ nhất trong G'.
Theo định lý luồng cực đại và lát cắt nhỏ nhất, cap(A, B) < | X |.
Gọi XA = X A, XB = X B , YA = Y A.
cap(A, B) = | XB | + | YA |.
Do lát cắt nhỏ nhất không sử dụng cạnh : (XA) YA. Suy ra:
| (XA )| | YA | = (| XB | + | YA |) - | XB | = cap(A, B) - | XB | < | X | - | XB | = | XA |.
1
Chọn S = XA ta có | (S)| < |S| ?! ■
1
G' 1'
A
2'
2 XA = {2, 4, 5}
1
s XB = {1, 3}
3'
1
3 YA = {2', 5'}
4
4' t (XA) = {2', 5'}
5 1
5'
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT 20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
