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
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) eOut(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 aP 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) eOut(a) eIn(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 ...
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) eOut(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 aP 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) eOut(a) eIn(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ìm kiếm theo từ khóa liên quan:
Bài giảng Lý thuyết đồ thị Lý thuyết đồ thị Bài toán luồng cực đại Bài toán ghép cặp Thuật toán Ford-FulkersonGợi ý tài liệu liên quan:
-
Đề cương chi tiết học phần Lý thuyết đồ thị (Graph Theory)
13 trang 218 0 0 -
Bài toán phân luồng giao thông và ứng dụng
11 trang 179 1 0 -
Bài giảng Lý thuyết đồ thị: Chương 3 - Các thuật toán tìm kiếm trên đồ thị
18 trang 115 0 0 -
Bài giảng Lý thuyết đồ thị - Bài 1: Đại cương về đồ thị
39 trang 113 0 0 -
Giáo trình toán rời rạc - Phụ lục 2
15 trang 84 0 0 -
Giáo trình Lý thuyết đồ thị: Phần 1 - PGS. Nguyễn Cam, PTS. Chu Đức Khánh
98 trang 75 0 0 -
Một số đánh giá hình học mạng lưới tàu điện đô thị Hà Nội theo lý thuyết đồ thị
9 trang 65 0 0 -
Bài giảng Lý thuyết đồ thị - Chương 2: Biểu diễn đồ thị
15 trang 45 0 0 -
Bài giảng Lý thuyết đồ thị: Chương 1 - Tôn Quang Toại
37 trang 45 0 0 -
Giáo trình Toán rời rạc và lý thuyết đô thị
226 trang 44 0 0