Bài viết Thuật toán tìm luồng cực đại trên mạng mở rộng xây dựng mô hình mạng 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 và hiệu quả hơn. Kết quả chính của bài báo là thuật toán Ford-Fulkerson cải biên tìm luồng cực đại trên mạng mở rộng. | Trần Quốc Chiến Trần Ngọc Việt Nguyễn Đình Lầu THUẬT TOÁN TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG MỞ RỘNG ALGORITHM FINDING MAXIMAL FLOWS ON EXTENDED TRAFFIC NETWORKS Trần Quốc Chiến1 Trần Ngọc Việt2 Nguyễn Đình Lầu2 1 Trường Đại học Sư phạm Đại học Đà Nẵng Email tqchien@ 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 A 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 tế. fields such as transportation communication informatics economy. Cho đến nay trong đồ thị mới chỉ xét đến trọng số của các cạnh In an ordinary graph the weights of edges and vertexes are consid- các đỉnh một cách độc lập trong đó độ dài đường đi là tổng trọng ered independently where the length of a path is the sum of weights số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên trong thực tế of the edges and the vertexes on this path. However in many prac- trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh tical problems weights at a vertex are not the same for all paths đó mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh đó. Bài passing this vertex but depend on coming and leaving edges. The viết xây dựng mô hình mạng mở rộng để có thể áp dụng mô hình paper develops a model of extended network that can be applied hóa các bài toán thực tế chính xác và hiệu quả hơn. Kết quả chính to modelling many practical problems more exactly and effectively. của bài báo là thuật toán Ford-Fulkerson cải biên tìm luồng cực đại The main contribution of this paper is the revised Ford-Fulkerson trên mạng mở rộng. algorithm finding maximal flows on extended networks. 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. 1. Đặt vấn đề Hàm chi phí nút bV V Ev Ev R với bV u e e0 là chi phí phải trả để chuyển một đơn vị phương tiện từ tuyến Mạng và luồng trên mạng là công cụ toán .
