TAILIEUCHUNG - Báo cáo nghiên cứu khoa học: "THUẬT TOÁN HOÁN CHUYỂN NGUỒN ĐÍCH TÌM LUỒNG CỰC ĐẠI (1)"

Báo cáo đề cập bài toán tìm luồng cực đại trên mạng. Các kết quả cơ bản được hệ thống và chứng minh. Thuật toán nổi tiếng Ford-Fulkerson được trình bày chi tiết kèm ví dụ minh hoạ. Kết quả chính của báo cáo là đề xuất Thuật toán hoán chuyển nguồn đích tìm luồng cực đại. Ý tưởng thuật toán là tìm đường đi tăng luồng đồng thời từ đỉnh nguồn và đỉnh đích (thuật toán Ford-Fulkerson tìm đường đi tăng luồng chỉ từ đỉnh nguồn). Kết quả tính toán qua các ví dụ cho thấy thuật toán hoán. | THUẬT TOÁN HOÁN CHUYÊN NGUỒN ĐÍCH TÌM LUỒNG CỰC ĐẠI 1 SOURCE-SINK ALTERNATIVE ALGORITHM TO FIND THE 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áo cáo đề cập bài toán tìm luồng cực đại trên mạng. Các kết quả cơ bản được hệ thống và chứng minh. Thuật toán nổi tiếng Ford-Fulkerson được trình .bày chi tiết kèm ví dụ minh hoạ. Kết quả chính của báo cáo là đề xuất Thuật toán hoán chuyển nguồn đích tìm luồng cực đại. Ý tưởng thuật toán là tìm đường đi tăng luồng đồng thời từ đỉnh nguồn và đỉnh đích thuật toán Ford-Fulkerson tìm đường đi tăng luồng chỉ từ đỉnh nguồn . Kết quả tính toán qua các ví dụ cho thấy thuật toán hoán chuyển nguồn đích làm giảm đáng kể khối lượng tính toán so với thuật toán Ford-Fulkerson. ABSTRACT This paper deals with the maximal flow problem. The basic results are systematically presented and proved. The known Ford-Fulkerson is thoroughly introduced and illustrated and the main result of this work is the source-sink alternative algorithm. The idea of the algorithm is to find augmented paths simultaneously from the source and the sink vertex the Ford-Fulkerson algorithm finds augmented paths only from the source vertex . Calculus examples show that the proposed algorithm considerably decreases the computational complexity in comparison with the Ford-Fulkerson algorithm. Key word graph network flow 1. Bài toán luồng cực đại M1ng network là đơn trọng đổ có hướng G V E c thoả mãn i Có duy nhất một đỉnh gọi là nguẩn. ii Cã duy nhÊt mét 0nh gai là Ých. iii Trang sè Cjj của cung i j là các số không âm và gọi là khH n ng th ng quacna cung. iv ả thh lian th ng yÕu . Luang. Cho m1ng G víi khH n ng th ng qua Cy íJ gG. TẼp c c gi trh fij I ij eG gọi là luẩng tran ming G nÕu thoH m n i 0 fj Cịj V íJ gG ii Víi mai 0nh k kh ng ph i nguản hoAc Ych E fk z fkj i k eG k j eG Pnh lý 1. Cho fịj ij eG là luổng trên mạng G với nguổn a và đích z. Khi đó Yía - z fa f a i eG i a eG i z eG - Xfzi z i eG Chong minh Gọi V là tập các đỉnh. Với

• Báo cáo khoa học
• trình bày báo cáo
• báo cáo kỹ thuật
• cách trình bày báo cáo
• báo cáo ngành nông nghiệp
• báo cáo ngành tin học
• 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 nông nghiệp
• báo cáo y dược
• báo cáo sinh họ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 ngoại ngữ
• báo cáo kinh tế
• 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ế