TAILIEUCHUNG - Báo cáo nghiên cứu khoa học: "THUẬT TOÁN ĐÍCH HƯỚNG NGUỒN TÌM LUỒNG CỰC ĐẠI"

Báo cáo nghiên cứu bài toán tìm luồng cực đại trên mạng. Trên cơ sở các kết quả trong công trình [15,16], Thuật toán đích hướng nguồn tìm luồng cực đại được đề xuất. Ý tưởng thuật toán là tìm đường đi tăng luồng từ đỉnh đích đến đỉnh nguồn (thuật toán Ford-Fulkerson tìm đường đi tăng luồng chỉ từ đỉnh nguồn đến đỉnh đích). | THUẬT TOÁN ĐÍCH HƯỚNG NGUỒN TÌM LUỒNG CỰC ĐẠI SINK TOWARD SOURCE ALGORITHM TO FIND MAXIMAL FLOW TRẦN QUỐC CHIẾN Trường Đại học Sư phạm Đại học Đà năng TÓM TẮT Báo cáo nghiên cứu bài toán tìm luồng cực đại trên mạng. Trên cơ sở các kết quả trong công trình 15 16 Thuật toán đích hướng nguồn tìm luồng cực đại được đề xuất. Ý tưởng thuật toán là tìm đường đi tăng luồng từ đỉnh đích đến đỉnh nguồn thuật toán Ford-Fulkerson tìm đường đi tăng luồng chỉ từ đỉnh nguồn đến đỉnh đích . Trong ví dụ minh hoạ kết quả tính toán cho thấy thuật toán đích hướng nguồn thực sự hiệu quả hơn hẳn thuật toán Ford-Fulkerson. ABSTRACT This paper deals with the maximal flow problem. On the basics of results of 15 16 The sink towards source algorithm is proposed. The idea of the algorithm is to find augmented paths from the sink vertex toward the source vertex the Ford-Fulkerson algorithm finds augmented paths only from the source vertex towards the sink vertex . In case of the illustrated example calculus shows that the proposed algorithm is absolutely more effective than the Ford-Fulkerson algorithm. Key word graph network flow Trước tiên ta nhắc lại các khái niệm và kết quả cơ bản về bài toán tìm luồng cực đại. Độc giả có thõ xem chi tiÕt trong 15 16 . Mng 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. i i Có duy nhất một đỉnh gọi là Ých. iii Trang sè Cjj của cung i j là các số không âm và gọi là khi n ng th ng quacna cung. iv â th lian th ng yÕu . Luảng. Cho m1ng G víi khi n ng th ng qua Cjj ij eG. TEp c c gv trl fj I itj eG gọi là luáng tran ming G nÕu thoi m n i 0 fịj Cij V ij eG ii Víi mai 0nh k kh ng phli 0 fj Cij V ij eG Víi mai 0nh k kh ng phli nguân hoíc Ych X fk - X fj fik fkj i k eG k j eG l nh lý sau cho phĐp ta l nh nghiia khj niOm gy trl cna luâng. Pnh lý 1. Cho fij ij eG là luồng trên mạng G với nguồn a và đích z. Khi đó X fz - X f X f - X f X fa - X fa - X fz - X fi a i qG i a eG i z eG z i eG Chong minh xem 15 l nh lý 1. Gp tri cna .

• Báo cáo khoa học
• trình bày báo cáo
• báo cáo ngành 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 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ế
• báo cáo kỹ thuật