BÀI TOÁN MAXIMUM FLOW(LUỒNG CỰC ĐẠI - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.ppt) (55 trang)

Trang chủ

Thạc sĩ - Cao học

Khoa học tự nhiên

BÀI TOÁN MAXIMUM FLOW(LUỒNG CỰC ĐẠI

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (336.3 KB, 55 trang )

BÀI TOÁNMAXIMUM FLOW(LUỒNG CỰC ĐẠI)Trình bày: Nhóm 6- KHMT BNguyễn Văn SửuNguyễn ĐềNguyễn Đức NghĩaNguyễn Đức QuêNguyễn Thị ThuNội dung trình bày Một số khái niệm, định lý Bài toán luồng cực đại Thuật toán Ford-Fulkerson Thuật toán Edmonds-Karp Một số ứng dụng của mạng và luồngMột số khái niệm, định lý1. Mạng vận tảiLà một đồ thị có hướng, không có khuyên và có trọng sốG=(V,E) gồm n đỉnh, m cạnh thỏa mãn:- Mỗi cung e=(u,v)∈ E (u,v∈ V) có trọng số c(e)=c[u,v] làmột số nguyên không âm và được gọi là khả năng thôngqua của cung e-Có một và chỉ một đỉnh s không có cung đi vào đượcgọi là lối vào hay đỉnh phát- Có một và chỉ một đỉnh t không có cung đi ra được gọilà lối ra hay đỉnh thu của mạngMột số khái niệm, định lý (tt)Trọng số215sĐỉnh phát9158364115151515863161517t10Đỉnh thu7Ví dụ: hình mạng vận tải với đỉnh phát là s và đỉnh thu là tMột số khái niệm, định lý (tt)2. LuồngCho mạng G=(V,E) Luồng ϕ trên G là một phép gán cho mỗi cung e=(u,v)một số thực ϕ (e)= ϕ [u,v] ≥ 0, thỏa mãn:• Luồng không vượt quá khả năng của cung đó0 ≤ ϕ [u,v] ≤ c[u,v], ∀ (u,v)∈ E•Nếu v ≠ s,t thì tổng luồng đi vào v bằng tổng luồngđi ra khỏi v (v∈ V\{s,t})Giá trị của 1 luồng bằng tổng luồng trên các cung đi rakhỏi s, và bằng tổng luồng đi vào tMột số khái niệm, định lý (tt)a6c5Mạng vận tải G36ts53bad15c5Một luồng f = 7616ts20b11dMột số khái niệm, định lý (tt)3. Lát cắt Lát cắt (X,Y) là một phân hoạch tập đỉnh V của mạngthành hai tập rời nhau X,Y trong đó X chứa đỉnh phát và Ychứa đỉnh thuKhả năng thông qua của lát cắt (X,Y) là tổng tất cả cáckhả năng thông qua của các cung (u,v) có u∈X và v∈YLát cắt với khả năng thông qua nhỏ nhất là lát cắt cực tiểuLuồng f(X,Y) bằng tổng luồng trên các cung (u,v) với(u∈X,v∈Y) và tổng luồng trên các cung (w,z) với z∈X,w∈YMột số khái niệm, định lý (tt)Ví dụ: Lát cắt χ=(X,Y):Khả năng thông qua: c(χ) = 6+7+9+2 = 24Luồng:f(χ) = 2+(-1)+3+2+2 = 8Y2X2/61/163/73/311/334/53/542/22/95Một số khái niệm, định lý (tt)Định lý 1Cho mạng G=(V,E), và luồng f, khi đó luồng thông qua látcắt (X,Y) bất kỳ bằng |f|6ac5356ts53b1Gd6a5c61ts20b11dMột số khái niệm, định lý (tt)Định lý 2Cho mạng G=(V,E), và luồng f, khi đó f(X,Y)≤c(X,Y)f(X,Y) = 7 ≤ c(X,Y) = 13Ga6c5356ts53b1d6a5/6c61/3st0/32b1/1d1Một số khái niệm, định lý (tt)Định lý 3Cho mạng G=(V,E), và luồng f bất kỳ, lát cắt (X,Y) bất kỳ.khi đó|f| ≤ c(X,Y)f(X,Y) = 8 ≤ c(X,Y) = 13Ga6c5356ts53b1d6a5/6c62/3st1/33b1/1d2Một số khái niệm, định lý (tt)Đồ thị tăng luồngCho f là 1 luồng trên mạng G, Từ mạng G =(V,E) ta xâydựng đồ thị có trọng số G1= (V,Ef) như sau:• Nếu f[u,v]fu,v])BeginThen{Xét v kề u}Trace[v]:=u;If v=t Then {Nếu đến đích thì dừng}Beginpath:=True;Exit;End;Findpath(v);End;If path=true Then exit;End;Sơ đồ khối thuật toán tăng luồngBeginv:= P[t] ; u:= t ; delta=maxintEndFalseu≠sTruev:= -vf[v,u]:=f[v,u] - deltaFalsev>0u:=v; v:=P[u]Truef[v,u]:=f[v,u] +deltaVí dụ: cho mạng G = (V,E)Ký hiệu 6(5): khả năng thông qua (luồng)25(5)6(5)46(6)3(1)613(0)5(2)6(1)3Bước 1: khởi tạo luồng f=025(0)1(1)6(0)543(0)6(0)613(0)5(0)6(0)31(0)5Bước 1: khởi tạo luồng f=025(0)6(0)46(0)3(0)613(0)5(0)6(0)3Bước 2: Đồ thị tăng luồng Gf251(0)65436613563Chọn đường tăng luồng P=(1,2,4,6)∆P = min(5,6,6)=5Tăng luồng dọc theo P ta thu được luồng mới f=5155(5)6(5)246(5)3(0)613(0)5(0)6(0)351(0)Đồ thị tăng luồng552143516135Chọn đường tăng luồng P=(1,3,5,6)∆P = min(5,1,6)=1Tăng luồng dọc theo P ta thu được luồng mới f=66315

Tài liệu liên quan

BÀI TOÁN XÂU TRONG CỰC ĐẠI VÀ LỜI GIẢI
- 14
- 1
- 7
BÀI TOÁN XÂU TRONG CỰC ĐẠI
- 22
- 550
- 6
TIỂU LUẬN TOÁN ỨNG DỤNG BÀI TOÁN TÌM LUỒNG CỰC ĐẠI TRONG MẠNG THEO THUẬT TOÁN FORD-FULKERSON
- 35
- 1
- 8
Tiểu luận môn Thuật Toán và Phương Pháp Giải Quyết Vấn Đề ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
- 22
- 732
- 3
Một số kỹ năng giải bài toán tiếp tuyến, cực trị của các hàm số cơ bản
- 86
- 517
- 0
Đồ thị và bài toán cây khung cực tiểu
- 17
- 585
- 2
Về bài toán rời rạc và đại số tổ hợp luận văn thạc sĩ toán học
- 59
- 507
- 1
BÀI TOÁN MAXIMUM FLOW(LUỒNG CỰC ĐẠI
- 55
- 650
- 0
Hướng dẫn học sinh lớp 12 sử dụng kỹ năng tính tích phân các hàm số hữu tỉ để giải một số bài toán trong đề thi đại học và đề thi HSG
- 20
- 288
- 0
tiếp cận bấ đẳng thức thông qua các bài toàn trong đề thi đại học, cao đẳng 2007 2016 nguyễn đại dương
- 27
- 405
- 0