TAILIEUCHUNG - 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 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 .

• Báo cáo khoa học
• trình bày báo cáo
• báo cáo kỹ thuật
• báo cáo sinh học
• báo cáo nông nghiệp
• báo cáo văn học
• CÁCH TRÌNH BÀY BÁO CÁO
• PHƯƠNG PHÁP TRÌNH BÀY BÁO CÁO
• KĨ NĂNG TRÌNH BÀY BÁO CÁO
• MẸO TRÌNH BÁY BÁO CÁO
• TRÌNH BÀY BÁO CÁO KHOA HỌC
• TRÌNH BÀY LUẬN VĂN BÁO CÁO
• Hình thức báo cáo thực tập
• Báo cáo thực tập tốt nghiệp
• Báo cáo thực tập
• Trình bày báo cáo thực tập
• Hướng dẫn trình bày báo cáo
• Hướng dẫn viết báo cáo
• Mẫu báo cáo
• Cách trình bày luận văn
• Cách trình bày khóa luận
• Thể thức của báo cáo
• trình bày luận văn
• tài liệu báo cáo khoa học
• báo cáo y dược
• chăn nuôi lợn
• Kỹ năng trình bày báo cáo
• Kỹ năng thuyết trình
• Thiết kế slide
• Định dạng văn bản
• Nội dung trình bày báo cáo
• Thời gian thuyết trình
• Thực tập chuyên ngành
• Hướng dẫn viết tiểu luận
• Cấu trúc báo cáo
• Cách thể hiện báo cáo
• Nội dung báo cáo
• cách trình bày báo cáo khoa học
• báo cáo khoa học sinh học
• báo cáo khoa học toán học
• tài liệu báo cáo nghiện cứu khoa học
• báo cáo ngành văn học
• báo cáo tiếng anh
• báo cáo khoa học
• thơ lục bát
• chăn nuôi
• báo cáo ngành kỹ thuật
• báo cáo ngành nông nghiệp
• báo cáo ngành ngoại ngữ
• báo cáo kinh tế
• báo cáo ngành tin học
• tài liệu báo cáo nghiên cứu khoa học
• báo cáo ngành y học
• trình bày thông tin tài sản thiếu trong báo cáo tài chính
• trình bày thông tin tài sản
• trình bày thông tin tài sản trong báo cáo tài chính doanh nghiệp
• phân tích tài chính
• tài chính doanh nghiệp
• phân tích tài chính doanh nghiệp
• báo cáo tài chính
• Tài liệu về trình bày đồ án
• Trình bày đồ án tốt nghiệp
• Quy định trình bày báo cáo cáo chuyên đề
• Quy định trình bày bài tập lớn
• Viện Đại học Mở Hà Nội
• mẫu báo cáo thực tập tốt nghiệp
• trình bày luận án
• cách viết báo cáo tốt nghiệp
• báo cáo tốt nghiệp
• Báo cáo phân tích ngành hàng hải
• báo cáo khoa học kinh tế