Bài giảng Lý thuyết đồ thị - Chương 5: Luồng trong mạng. Những nội dungc hính được trình bày trong chương này gồm có: Giới thiệu, luồng trong mạng, bài toán luồng cực đại, thuật toán Ford Fulkerson, một số ứng dụng của bài toán luồng cực đại. . | Bài giảng Lý thuyết đồ thị Đặng Nguyễn Đức Tiến HCMUS – 2009 Giới thiệu Luồng trong mạng Bài toán luồng cực đại Thuật toán Ford Fulkerson Một số ứng dụng của bài toán luồng cực đại HCMUS – 2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến Nguyễn Đức Nghĩa, Nguyễn Tô Thành, Toán rời rạc, ltb. 1, nxb. Giáo dục, 1998, ch. 7, tr. 215 – 236. Đỗ Minh Hoàng, Bài giảng Chuyên đề Giải thuật & Lập trình, ĐHSP Hà Nội, 2004, ch. 10, tr. 257 – 267. Dương Anh Đức, Trần Đan Thư, Bài giảng lý thuyết đồ thị, 2002, ch. 5. HCMUS – 2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến Luồng cực đại là một trong những bài toán tối ưu trên đồ thị tìm được những ứng dụng rất rộng rãi trong cả thực tế cũng như trong lý thuyết tổ hợp. Bài toán được đề xuất vào đầu những năm 1950 và gắn liền với tên tuổi của 2 nhà toán học Mỹ: Ford (Lester Randolph Ford: 1927 - ) và Fulkerson (Delbert Ray Fulkerson: 1924 - 1976). HCMUS – 2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến Mạng (network) là | Bài giảng Lý thuyết đồ thị Đặng Nguyễn Đức Tiến HCMUS – 2009 Giới thiệu Luồng trong mạng Bài toán luồng cực đại Thuật toán Ford Fulkerson Một số ứng dụng của bài toán luồng cực đại HCMUS – 2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến Nguyễn Đức Nghĩa, Nguyễn Tô Thành, Toán rời rạc, ltb. 1, nxb. Giáo dục, 1998, ch. 7, tr. 215 – 236. Đỗ Minh Hoàng, Bài giảng Chuyên đề Giải thuật & Lập trình, ĐHSP Hà Nội, 2004, ch. 10, tr. 257 – 267. Dương Anh Đức, Trần Đan Thư, Bài giảng lý thuyết đồ thị, 2002, ch. 5. HCMUS – 2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến Luồng cực đại là một trong những bài toán tối ưu trên đồ thị tìm được những ứng dụng rất rộng rãi trong cả thực tế cũng như trong lý thuyết tổ hợp. Bài toán được đề xuất vào đầu những năm 1950 và gắn liền với tên tuổi của 2 nhà toán học Mỹ: Ford (Lester Randolph Ford: 1927 - ) và Fulkerson (Delbert Ray Fulkerson: 1924 - 1976). HCMUS – 2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến Mạng (network) là một đồ thị có hướng G = (V, E) trong đó: Có duy nhất một đỉnh s không có cung đi vào, được gọi là đỉnh phát (source) Có duy nhất một đỉnh t không có cung đi ra, được gọi là đỉnh thu (sink) Mỗi cạnh e = (u, v) E được gán một số nguyên không âm c(e) = c[u, v] và gọi là khả năng thông qua của cung đó (capacity). Ta quy ước nếu mạng không có cung (u, v) thì ta thêm vào cung (u, v) với khả năng thông qua c[u, v] bằng 0. HCMUS – 2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến Với một mạng G = (V, E, c), ta ký hiệu: W-(x) = {(u, v) E | u V}: tập các cung đi vào đỉnh v. W+(x) = {(v, u) E | u V}: tập các cung đi ra khỏi đỉnh v. HCMUS – 2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến Giả sử cho mạng G = (V, E). Ta gọi luồng f trong mạng là ánh xạ f: E R+ gán cho mỗi cung e = (u, v) E một số thực không âm f(e) = f[u, v], thoả mãn các điều kiện sau: ĐK 1 (Capacity Constraint): Luồng trên mỗi cung e E không vượt quá khả năng thông qua của nó: 0 ≤ f(e) ≤ c(e) .
