Mời các bạn tham khảo Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 3: Luồng cực đại sau đây để nắm bắt được những kiến thức về khái niệm mạng, tìm luồng cực đại trong mạng, thuật toán Ford-Fulkerson. | TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CNTT & TRUYỀN THÔNG BỘ MÔN KHOA HỌC MÁY TÍNH 1 TOÁN RỜI RẠC (DISCRETE MATHEMATICS) 08/2013 GV: Trần Nguyễn Minh Thư (tnmthu@) 2 Luồng cực đại 8/3/2015 Khái niệm mạng Đồ thị có hướng G=(X,E) được gọi là mạng khi: Tồn tại duy nhất một đỉnh s X mà tại s không có cung đi vào, chỉ có cung đi ra. Gọi s là điểm phát. Tồn tại duy nhất một đỉnh t X mà tại t không có cung đi ra, chỉ có cung đi vào. Gọi t là điểm thu. Mỗi cung e=(i,j) đều được gán một giá trị không âm c(e) hay c(i,j), gọi là khả năng thông qua của cung. Nếu không tồn tại cung từ đỉnh i đến đỉnh j thì khả năng thông qua của cung đó được qui ước là bằng không. Khái niệm mạng Mạng G=(X,E): Ánh xạ f từ E vào R+ được gọi là một luồng trong mạng, cần thỏa các điều kiện: 1) Giới hạn của luồng Với mỗi cung e, gọi f(e) là luồng Luồng trên cung không vượt quá khả năng thông qua của cung: 0 f(e) c(e) Khái niệm mạng Mạng G=(X,E): Ánh xạ f từ E vào R+ được gọi là một luồng trong mạng, cần thỏa các điều kiện: 2) Cân bằng luồng Với mỗi đỉnh i không là đỉnh thu, cũng không là đỉnh phát (i s và i t) thì tổng luồng trên các cung đi vào i bằng tổng luồng trên các cung từ i đi ra f ( j, i) f (i, k) ( j,i ) ( i , k .
