Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 3: Luồng cực đại

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 3: Luồng cực đạiTRƯỜNG ĐẠI HỌC CẦN THƠKHOA CNTT & TRUYỀN THÔNGBỘ MÔN KHOA HỌC MÁY TÍNH1TOÁN RỜI RẠC(DISCRETE MATHEMATICS)08/2013GV: Trần Nguyễn Minh Thư (tnmthu@ctu.edu.vn)2Luồng cực đại8/3/2015Khá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 đivà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 đira, 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ăngthông qua của cung đó được qui ước là bằng không.Khái niệm mạngMạng G=(X,E):Ánh xạ f từ E vào R+ được gọi là một luồng trongmạ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ủacung: 0  f(e)  c(e)Khái niệm mạngMạng G=(X,E):Ánh xạ f từ E vào R+ được gọi là một luồng trongmạ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à đỉnhphát (is và it) thì tổng luồng trên các cung đi vào ibằng tổng luồng trên các cung từ i đi ra f ( j, i)   f (i, k)( j,i )( i , k )