Bài giảng Lý thuyết đồ thị - Chương 7: Mạng và luồng trên mạng

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 7: Mạng và luồng trên mạng

1. Chương 7 Mạng và luồng trên mạng
2. Mạng là gì? ⚫ Cho G(V,E) là đồ thị có hướng. Khi đó nếu G thỏa mãn: – Tồn tại 1 đỉnh s chỉ có cung đi ra (đỉnh nguồn). – Tồn tại 1 đỉnh t chỉ có cung đi vào (đỉnh đích). – Với mỗi cung (u,v) thuộc E, tồn tại một số thực không âm c(u,v) (gọi là khả năng thông của cung (u,v)). Thì G được gọi là một mạng. Và kí hiệu là G(V,E,s,t).
3. Mạng là gì? (tt) ⚫ Đồ thị trên là một mạng, với: – Nguồn s = 1 – Đích t = 5
4. Luồng trên mạng ⚫ Giả sử G(V,E,s,t) là một mạng. Khi đó: ⚫ Mỗi ánh xạ f: E→ R (,)(,)u v→ f u v R ⚫ Thỏa mãn đồng thời các điều kiện sau: – Giới hạn luồng trên cung: 0 f ( u , v ) c ( u , v ) – Cân bằng luồng: f( u , v )−= f ( v , w) 0 u Vw V ⚫ Được gọi là một luồng trên mạng G. ⚫ Đặt Val( f )== f ( s , v ) f (w, t ) v Vw V ⚫ Và gọi là giá trị của luồng f.
5. Luồng trên mạng (tt) Mạng G và luồng f với val(f) = 4
6. Bài toán luồng cực đại ⚫ Cho mạng G(V,E,s,t). Hãy tìm luồng f trên G sao cho val( f )→ m ax ⚫ Khi đó f được gọi là luồng cực đại.
7. Giải bài toán luồng cực đại ⚫ Cho mạng G(V,E,s,t). Khi đó ta định nghĩa các khái niệm sau: 1. Lát cắt: Đặt X V:, s X t X XVX'\= Thì (X,X’) được gọi là một lát cắt trên G, và:  c(,) u v uX vX ' Được gọi là khả năng thông qua của lát cắt (X,X’).
8. Giải bài toán luồng cực đại (tt) ⚫ Định lý: giá trị của luồng bất kỳ không vượt qua khả năng thông qua của lát cắt bất kỳ Val( f )  c ( u , v )  f ,  ( X , X ') uX vX '
9. Giải bài toán luồng cực đại (tt) ⚫ 2. Đồ thị tăng luồng: Cho mạng G(V,E,s,t) với luồng f. Khi đó đồ thị tăng luồng Gf là một đồ thị có hướng, với trọng số của các cung trên Ef được xác định như sau: – Nếu f(u,v)=0 thì (,)u v = Ef, TS (,) u v c (,) u v – Nếu f(u,v)=c(u,v) thì (,)v u = Ef, TS (,) v u f (,) u v – Nếu 0<f(u,v)<c(u,v) thì (,)u v Ef, TS (,) u v = c (,) u v − f (,) u v
10. Giải bài toán luồng cực đại (tt) ⚫ Ví dụ: G và f Gf Ví dụ về đồ thị tăng luồng
11. Giải bài toán luồng cực đại (tt) ⚫ 3. Đường tăng luồng: – Giả sử Gf là đồ thị tăng luồng của mạng G với luồng f. Khi đó: – Mỗi đường đi Pf từ đỉnh nguồn s đến đỉnh đích t trên Gf là một đường tăng luồng. – Và ta đặt d= min{ d ( u , v ) : ( u , v ) Pf }
12. Giải bài toán luồng cực đại (tt) ⚫ Ví dụ: với Gf sau đây, ta tìm được: Pf :1,3,4 d = 3 Ví dụ về đường tăng luồng
13. Giải bài toán luồng cực đại (tt) ⚫ 4. Cung thuận/nghịch: ⚫ Giả sử Pf là đường tăng luồng trên Gf. Khi đó: ⚫ Các cung trên G cùng chiều với các cung của Pf sẽ được gọi là cung thuận, ngược lại là cung nghịch. ⚫ Ví dụ: với Gf và G sau, ta xét Pf có dạng: 1,3,2,4 thì: – Các cung: (1,3), (2,4) là cung thuận – Cung: (2,3) là cung nghịch
14. Giải bài toán luồng cực đại (tt) ⚫ 5. Tăng luồng: – Giả sử Pf là đường tăng luồng với trọng số nhỏ nhất là d. Khi đó, ta đặt: f( u , v ), ( u , v ) Pf f'( u , v )=+ f ( u , v ) d Nếu (u,v) là cung thuận f(,) u v− d Nếu (u,v) là cung nghịch Thì f’ là một luồng mới trên G với: Val(f’) = Val(f) + d
15. Giải bài toán luồng cực đại (tt) ⚫ Định lý Fulkerson: – Giả sử G(V,E,s,t) là một mạng và f là một luồng trên G. Khi đó các phát biểu sau là tương đương với nhau: ⚫ i. f là luồng cực đại. ⚫ ii. Không tồn tại bất kỳ đường tăng luồng nào trên Gf. ⚫ iii. Tồn tại lát cắt (X,X’) sao cho c( X , X ')= Val ( f )
16. Giải thuật Fulkerson tìm luồng cực đại ⚫ Bước 1: Khởi tạo từ luồng xuất phát (thường là luồng 0) f( u , v )= 0,  ( u , v ) E ⚫ Bước 2: – Tìm đồ thị tăng luồng Gf. – Tìm đường tăng luồng Pf trên Gf. ⚫ Nếu không tồn tại Pf, dừng. ⚫ Nếu tồn tại Pf, tìm trọng số nhỏ nhất d. ⚫ Tăng luồng theo d. ⚫ Quay về Bước 2.
17. Ví dụ (Theo dõi trên bảng!!!)