Lý thuyết đô thị - Chương 7: Bài toán luồng cực đại trong mạng

Chương 7Bài toán luồng cực đại trong mạngKhái niệm mạngĐịnh nghĩa. Mạng là một đồ thị có hướng G = , trong đó: Có duy nhất một đỉnh s không có cạnh đi vào, gọi là điểm phát. Có duy nhất một đỉnh t không có cung đi ra, gọi là điểm thu. Mỗi cạnh của đồ thị được gán với một con số không âm gọi là khả năng thông qua (băng thông) của cạnh đó.*Lý thuyết đồ thị*st123443323143Luồng trên mạngĐịnh nghĩa. Xét mạng G = . Ta gọi luồng f trong mạng là ánh xạ f: E  R+, gán cho mỗi cạnh e = (u,v) một số thực không âm f(e), gọi là luồng trên cung e, thỏa mãn các điều kiện sau:Luồng trên mỗi cung không đượt vượt quá khả năng thông qua của nó: f(e)  c(e).Tại mỗi đỉnh, tổng luồng đi vào phải bằng tổng luồng đi ra (trừ tại s và t).Giá trị của mỗi luồng f được tính bằng tổng luồng đi ra tại s (cũng chính là tổng luồng đi vào tại t).*Lý thuyết đồ thị*Luồng trên mạng (tt)VD:Ký hiệuĐiều kiện cân bằng luồng:Giá trị của luồng f:*Lý thuyết đồ thị*st123443323143(1)(3)(1)(1)(1)(1)(2)(3)Val(f) = 4Lát cắtMột lát cắt (X,X*) là một cách phân hoạch tập đỉnh V của mạng thành hai tập X và X* = V\X, trong đó sX và tX*.Khả năng thông qua của lát cắt (X,X*) là số:Lát cắt với khả năng thông qua nhỏ nhất được gọi là lát cắt hẹp nhất*Lý thuyết đồ thị*Lát cắt (tt)VD:Xét lát cắt (X,X*) với X = {s, 3, 4}, X* = {t, 1, 2}Ta có c(X, X*) = 4 + 1 + 2 + 4 = 11Lát cắt nhỏ nhất???Lát cắt nhỏ nhất là: X = {s, 1}, X* = {t, 2, 3, 4}*Lý thuyết đồ thị*st123443323143Lát cắt (tt)Bổ đề: Giá trị của luồng f trong mạng luôn nhỏ hơn hay bằng khả năng thông qua của lát cắt bất kỳ.Bổ đề: Giá trị luồng cực đại trong mạng không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng.*Lý thuyết đồ thị*Đồ thị tăng luồngXét mạng G với luồng f như sau:*Lý thuyết đồ thị*st123443323143(1)(3)(1)(1)(1)(1)(2)(3)st12343Mạng G và luồng f112331111231Đồ thị tăng luồng GfCung nghịchCung thuậnĐồ thị tăng luồng (tt)Xét P = (s = v0 v1 v2 vk = t) là một đường đi trên đồ thị tăng luồng.Gọi  là giá trị trọng số nhỏ nhất của một cạnh trên cung này.Ta xây dựng luồng f’ trên mạng G theo quy tắc như sau:f’ được gọi là đường tăng luồng dọc theo P*Lý thuyết đồ thị*, nếu (u,v)  P là cung thuận, nếu (u,v)  P là cung nghịch, nếu (u,v)  PĐồ thị tăng luồng (tt)VD:*Lý thuyết đồ thị*st12343112331111231st123443323143(1)(3)(1)(1)(1)(1)(2)(3)= 1(2)(0)(2)(2)Đồ thị tăng luồng GfMạng G và luồng mới f’Val(f’) = 5Đường tăng luồng Định nghĩa: Đường tăng luồng f là một đường đi bất kỳ từ s đến t trong đồ thị Gf.Định lý: Các điều sau là tương đương:f là luồng cực đại trong mạngKhông tồn tại đường tăng luồng fval(f) = c(X,X*) với một lát cắt (X,X*) nào đó*Lý thuyết đồ thị*Thuật toán tìm luồng cực đạiÝ tưởng thuật toánBắt đầu từ một luồng f bất kỳ - có thể là luồng 0Xây dựng đồ thị tăng luồng Gf.Từ Gf, tìm đường tăng luồng PNếu không có đường tăng luồng nào thì kết thúc.Nếu có đường tăng luồng P thì xây dựng luồng mới f’ và lặp lại quá trình trên cho đến khi không tìm thêm được đường tăng luồng mới.*Lý thuyết đồ thị*Một số kết quả lý thuyếtĐịnh lý: Luồng cực đại trong mạng bằng khả năng thông qua của lát cắt hẹp nhất.Định lý: Nếu tất cả các khả năng thông qua là các con số nguyên thì luôn tìm được luồng cực đại với luồng trên các cung là các số nguyên*Lý thuyết đồ thị*Một số bài toán luồng tổng quátTự đọc thêm trong tài liệu (Chương 7)Nguyễn Đức Nghĩa, Nguyễn Tô Thành. Toán Rời Rạc. NXB Giáo Dục, 1999*Lý thuyết đồ thị*Một số ứng dụng trong tổ hợpTự đọc thêm trong tài liệu (chương 7):Nguyễn Đức Nghĩa, Nguyễn Tô Thành. Toán Rời Rạc. NXB Giáo Dục, 1999*Lý thuyết đồ thị*