Thuật toán đường đi tăng luồng tìm luồng cực đại trên mạng hỗn hợp mở rộng

Augmenting-Path MaxFlow Algorithm on extended mixed networks
Nơi đăng: Tạp Chí Khoa học và Công nghệĐại Học ĐN, Số: , Trang: 89, Năm: 2014, Loại bài viết: Bài báo, Quốc gia: Việt Nam.

Tóm tắt:

Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh đó. Bài viết xây dựng 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 và hiệu quả hơn. Kết quả chính của bài viết là thuật toán đường đi tăng luồng tìm luồng cực đại 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.

Từ khóa: đồ thị; mạng; luồng; luồng cực đại; thuật toán

Abstract:

Graph is a powerful mathematical tool applied in many fields as transportation, communication, informatics, economy, … In ordinary graph the weights of edges and vertexes are considered indepently where the length of a path is the sum of weights of the edges and the vertexes on this path. However, in many practical problems, weights at a vertex are not the same for all paths passing this vertex, but depend on coming and leaving edges. The paper develops a model of mixed extended network that can be applied to modelize many practical problems more exact and effective. The main contribution of this paper is the augmenting-path maxflow algorithm and the Maxflow-Mincut theorem on extended mixed networks.

Keywords: graph; network; flow; maximal flow; algorithm.