Danh mục

Bài giảng Lý thuyết đồ thị: Chương 6 - ThS. Trần Quốc Việt

Số trang: 44      Loại file: pdf      Dung lượng: 1.53 MB      Lượt xem: 28      Lượt tải: 0    
tailieu_vip

Xem trước 5 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

Bài giảng Lý thuyết đồ thị: Chương 6 Một số ứng dụng, cung cấp cho người đọc những kiến thức như: Bài toán luồng cực đại (Max-flow problem); Bài toán ghép cặp (Matching problem);... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị: Chương 6 - ThS. Trần Quốc Việt CHƯƠNG 6 GV: TRẦN QUỐC VIỆT 1 Giới thiệu 2 ứng dụng:  Bài toán luồng cực đại (Max-flow problem)  Bài toán ghép cặp (Matching problem) 2 3  Mạng (network) là một đồ thị có hướng có trọng số G = (V,E) trên đó ta chọn một đỉnh gọi là đỉnh phát (source vertex) và 1 đỉnh gọi là đỉnh thu (sink vertex). 3 Ví dụ 5 5 2 6 2 source sink 8 4 4 3 4  Một mạng G = (V,E) với đỉnh phát là a, đỉnh thu là z, c(e)  N là trọng số của cung e. Với mỗi đỉnh x, ta đặt: In(x) = {e  E | e tới trong x} Out(x) = {e  E | e tới ngoài x} b 3 d 5 5 In(c)={ac, bc} 2 6 2 a z Out(c)={cd, ce} 8 4 4 c 3 e 5  Một hàm tải (flow function) trên G được định nghĩa bởi ánh xạ: φ: E  N thỏa các điều kiện (i) 0 ≤ φ(e) ≤ c(e), e  E (Giới hạn của luồng) (i) φ(e) = 0, e  In(a)  Out(z) (Giá trị luồng) (iii)   (e)    (e) ,  x  V \ a, z bằngluồng) e In(x) eOut(x) (Cân 6 (fa) = 0 (zg) = 0 b d (ab) = 4 3,1 c[u,v]/f[u,v] (ac) = 1 5,4 2,1 5,4 (fc) = 0 6,2 2,1 z (gc) = 0 a 4,1 (bd) = 1 4,1 8,2 (be) = 1 4,0 c 3,1 (2,0) (bc) = 2 e (cd) = 2 3,0 1,0 (ce)=1 f g (dz) = 4 (ez) = 1 (ed) = 1 7  Một phép cắt (cut) xác định bởi 1 tập hợp con P của V, ký hiệu (P, P ) là tập hợp: (P, P ) = { xy | x  P và y  P } Trong đó P  V \ P  Phép cắt (P, P ) gọi là 1 phép cắt a-z nếu aP và z P  Trọng số (capacity) của một phép cắt được định nghĩa là: c(P, P)   c(e) 8 e(P,P ) b 3 d 5 5 2 6 2 a z 8 4 4 c  P={a,b, c} 3 e  P={d, e,z}  (P,P)={bd,be,cd,ce}  c(P,P)=16 9 Gọi  là một hàm tải trên mạng G và P  V\{a,z} thì:   (e)    (e) e(P, P ) e ( P , P) Ví dụ: b 3,1 d P 5,4 5,4 2,1 2,1 a 6,2 z 4,1 8,2 4,1 4,0 3,1 (2,0) c e 3,0 1,0 f g 10  Với mọi hàm tải φ trên mạng G, lượng tải khỏi a bằng lượng tải vào z, nghĩa là:   (e)    (e) eOut(a) eIn(z) b d 3,1 5,4 5,4 2,1 2,1 a 6,2 z 4,1 8,2 4,1 4,0 ...

Tài liệu được xem nhiều: