THUẬT TOÁN ĐÍCH HƯỚNG NGUỒN TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG HỖN HỢP MỞ RỘNG

Abstract

Đồ 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 hiệu quả hơn. Kết quả chính của bài báo là thuật toán đích hướng nguồn tìm luồng cực đại trên mạng hỗn hợp mở rộng, với ý tưởng chính của thuật toán là tìm đường đi tăng luồng từ đỉnh đích đến đỉnh nguồn trên mạng hỗn hợp mở rộng; bởi lẽ thông thường thuật toán Ford-Fulkerson tìm đường đi tăng luồng chỉ từ đỉnh nguồn đến đỉnh đích.