Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo nghiên cứu khoa học: " PHƯƠNG PHÁP KÉO LUỒNG SAU TÌM LUỒNG CỰC ĐẠI"

Bài toán tìm luồng cực đại trên mạng là một bài toán quan trọng có nhiều ứng dụng trong thực tế. Nhiều thuật toán tìm luồng cực đại trên mạng đã được nghiên cứu và phát triển (xem [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12]). Công trình này nghiên cứu một cách tiếp cận khác giải bài toán tìm luồng cực đại trên mạng. Kết quả chính của bài báo là phương pháp kéo luồng sau tìm luồng cực đại. Ý tưởng của phương pháp này là cân bằng hóa luồng vào và luồng. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG - SỐ 5 40 .2010 PHƯƠNG PHÁP KÉO LUỒNG SAU TÌM LUỒNG CỰC ĐẠI POSTFLOW-PULL METHODS TO FIND MAXIMAL FLOW Trần Quốc Chiến Trường Đại học Sư phạm Đại học Đà Nang TÓM TẮT Bài toán tìm luồng cực đại trên mạng là một bài toán quan trọng có nhiều ứng dụng trong thực tế. Nhiều thuật toán tìm luồng cực đại trên mạng đã được nghiên cứu và phát triển xem 1 2 3 4 5 6 7 8 9 10 11 12 . CÔng trình này nghiên cứu một cách tiếp cận khác giải bài toán tìm luồng cực đại trên mạng. Kết quả chính của bài báo là phương pháp kéo luồng sau tìm luồng cực đại. Ý tưởng của phương pháp này là cân bằng hóa luồng vào và luồng ra tại các đỉnh lệch bằng cách luồng dư được đẩy xuôi theo các cung vào hoặc đẩy ngược trên các cung ra. Quá trình cân bằng hóa đỉnh lệch được lặp lại cho đến khi không còn đỉnh lệch thì ta nhận được luồng cực đại. ABSTRACT The maximal flow problem is an important probem having many practical applications. Many algorithms for solving the maximal flow problem have been studied and developed see 1 2 3 4 5 6 7 8 9 10 11 i2 . This paper deals with a new approach to the solution of the maximal flow problem. The main result of this work is the postflow-pull method. The idea of the method is to balance the input and output flow of unbalanced vertex by pulling the residual flow. The maximal flow is obtained by repeating the balancing process until there is no unbalanced vertex. Key word graph network flow 1. Các khái niệm cơ bản Luồng sau post-flow Cho mạng G V E c với đỉnh nguồn a và đỉnh đích z. Luồng sau là tập hợp các luồng trên cung f f i j i j e G thỏa mãn i 0 í ì. ì c i j V i j GE ii Với mọi đỉnh k không phải nguồn hoặc đích luồng ra không nhỏ hơn luồng vào tức là LT ỵ.fkj i k eG k j eG Những đỉnh có luồng ra lớn hơn luồng vào gọi là đỉnh lệch unbalanced . Hiệu luồng vào và luồng ra tại các đỉnh lệch gọi là độ lệch luồng excess . Mạng thặng dư Gf. Cho luồng sau f trên mạng G. Mạng thặng dư Gf V Ef cf với tập cung Ef và khả năng .