Bài viết Thuật toán đẩy luồng trước tìm luồng cực đại trên mạng hỗn hợp mở rộng giới thiệu mô hình mạng hỗn hợp mở rộng để có thể áp dụng mô hình hóa các bài toán thực tế chính xác, hiệu quả hơn và định lý luồng cực đại lát cắt cực tiểu tương ứng trên mạng hỗn hợp mở rộng. | ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG SỐ 11 84 .2014 QUYỂN 1 87 THUẬT TOÁN ĐẨY LUỒNG TRƯỚC TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG HỖN HỢP MỞ RỘNG PUSH-PREFLOW MAXFLOW ALGORITHM ON EXTENDED MIXED NETWORKS Trần Quốc Chiến1 Trần Ngọc Việt2 Nguyễn Đình Lầu2 Trường Đại học Sư phạm Đại học Đà Nẵng Email tqchien@ 1 2 Trường Cao đẳng Giao thông Vận tải II Email trviet01@ launhi@ Tóm tắt - Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều Abstract - Graph is a powerful mathematical tool applied in many lĩnh vực như giao thông truyền thông công nghệ thông tin kinh fields as transportation communication informatics economy In tế . Cho đến nay trong đồ thị mới chỉ xét đến trọng số của các an ordinary graph the weights of edges and vertexes are cạnh các đỉnh một cách độc lập trong đó độ dài đường đi là tổng considered independently where the length of a path is the sum of trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên trong weights of the edges and the vertexes on this path. However in thực tế trọng số tại một đỉnh không giống nhau với mọi đường đi many practical problems weights at a vertex are not the same for qua đỉnh đó mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi all paths passing this vertex but depend on coming and leaving đỉnh đó. Bài viết giới thiệu mô hình mạng hỗn hợp mở rộng để có edges. The paper introduces a model of mixed extended network thể áp dụng mô hình hóa các bài toán thực tế chính xác hiệu quả that can be applied to modelizing many practical problems more hơnvà định lý luồng cực đại lát cắt cực tiểu tương ứng trên mạng exactly and effectively and the Maxflow-Mincut theorem on hỗn hợp mở rộng 10 11 . Kết quả chính của bài viết là thuật toán extended mixed networks. The main contribution of this paper is đẩy luồng trước tìm luồng cực đại. the Push-Preflow maxflow algorithm. Từ khóa - đồ thị mạng luồng luồng cực đại thuật toán. Key words - graph network flow maximal flow algorithm Giả thiết G có
