Bài toán về Luồng cực đại trong mạng với khả năng thông qua các cung các đỉnh

Chương 2BÀI TỐN LUỒNG CỰC ĐẠI VỚI KHẢ NĂNG THÔNG QUA CÁC CUNG – CÁC ĐỈNHBài tốn luồng cực đại trong mạng là một trong số những bài tốn tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vị trong lý thuyết tổ hợp.
Nội dung trích xuất từ tài liệu:
Bài toán về Luồng cực đại trong mạng với khả năng thông qua các cung các đỉnh Chương 2BÀI TỐN LUỒNG CỰC ĐẠI VỚI KHẢ NĂNG THÔNG QUA CÁC CUNG – CÁC ĐỈNH Bài tốn luồng cực đại trong mạng là một trong số những bài tốn tối ưu trên đồthị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vịtrong lý thuyết tổ hợp. Bài tốn được đề xuất vào đầu những năm 1950, và gắn liềnvới tên tuổi của hai nhà bác học Mỹ là Ford và Fulkerson. Bài tốn luồng cực đạitrong mạng có nhiều ứng dụng trong thực tế như: Bài tốn xác định cường độ dònglớn nhất của dòng vận tải giữa hai nút của một bản đồ giao thông, bài tốn tìm luồngdầu lớn nhất có thể bơm từ tàu chở dầu vào bể chứa của một hệ thống đường ống dẫndầu…Ngồi ra, ứng dụng của bài tốn còn để giải các bài tốn như: Bài tốn đám cướivùng quê, bài tốn về hệ thống đại diện chung, bài tốn phân nhóm sinh hoạt, bài tốnlập lịch cho hội nghị …Trong phạm vi đề tài này tôi sẽ trình bày “bài tốn luồng cựcđại trong mạng với khả năng thông qua các cung các đỉnh” và phải nhờ thuật tốn củaFord và Fulkerson để giải bài tốn đặt ra và nêu một số ứng dụng của bài tốn.I. PHÁT BIỂU BÀI TỐN1.Bài tốn Giả xử trong đồ thị G = (V,E), ngồi khả năng thông qua của các cung c(u,v), ởmỗi đỉnh v  V còn có khả năng thông qua của đỉnh là d(v), và đòi hỏi tổng luồng đivào đỉnh v không còn vượt quá d(v), tức là  f ( w, v )  d ( v ) w VCần phải tìm luồng cực đại giữa s và t trong mạng như vậy. Xây dựng một mạng G’ sao cho: mỗi đỉnh v của G tương ứng với hai đỉnh v+,v trong G’, mỗi cung (u,v) trong G ứng với cung (u,v+) trong G’, mỗi cung (v,w) -trong G ứng với cung (v-,w+) trong G’. Ngồi ra, mỗi cung (v+,v-) trong G’ có khảnăng thông qua là d(v), tức là bằng khả năng thông qua của đỉnh v trong G.2. Giải quyết bài tốn Từ mạng G = (V,E) khả năng thông qua các cung và các đỉnh. Ta sẽ giải quyếttheo hai bước sau: 10 Xác định mạng G’. 20 Tìm luồng cực đại trong mạng G’. Bắt đầu từ luồng zero với khả năngthông qua cung. 1 Thí dụ 1. Hình 1a cho ví dụ mạng G với khả năng thông qua ở cung và đỉnh.Hình 1b là mạng G’ tương ứng chỉ có khả năng thông qua ở các cung. u du (a) C[u,t] C[s,u] s t dt C[u,v] ds C[s,v] C[v,t] v dv u+ u- du (b) C[s,u] C[u,t] t+ t- dt s+ ds s- C[u,v] C[v,t] C[s,v] v+ v- dv Hình 1 Do luồng đi vào đỉnh v phải đi qua cung (v+,v-) với khả năng thông qua d(v), +nên luồng cực đại trong G’ sẽ bằng luồng cực đại trong G với khả năng thông quacủa các cung và đỉnh.Hai bước trên ta có thể biểu diễn dưới dạng sơ đồ thuật tốn sau: 2 Begin Mạng G Mạng G’ Luồng cực đại trên G’ End3. Ma trận biểu diễn đồ thị của bài tốn luồng cực đại.3.1 Biểu diễn mạng G với khả năng thông qua các cung - đỉnh Giả sử mạng G = (V,E), |V| = n. Ta có thể biểu diễn bởi ma trận trọng số A cấpn x n như sau: ,nếu i = j di A = ( aij ) = c[i,j] ,nếu [i,j]  E ,nếu [i,j]  E 0Trong đó: di là khả năng thông qua đỉnh i; C[i,j] khả năng thông qua cung [i,j].3.2 Biểu diễn mạng G’ tương ứng với mạng G Mạng tương ứng với G = (V,E), |V | = n là mạng G’ = (V’,E’), |V’| = 2 |V |,|E’| = 2 |E | - 1. Được biểu diễn thông qua ma trận A’ cấp (2n x 2n) như sau: nếu i = j 0 A’ = ( a’ij ) = c[i,j] nếu [i,j]  E’ 3 Thí dụ 2. Như thí dụ trên có mạng G như sau: u[6] 5 4 s[7] t[6] 1 2 3 v[8]Ta có ma trận biểu diễn mạng G : s u v t s 7 5 2 0 ...