THUẬT TOÁN TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG GIAO THÔNG MỞ RỘNG

Abstract

Bài toán luồng cực đại trên mạng là một trong số những bài toán tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vị trong các ngành như giao thông, truyền thông, công nghệ thông tin… 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 chỉ đơn thuần là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong bài toán thực tế, trọng số tại mỗi đỉ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 tại đỉnh đó. Chẳng hạn thời gian đi qua ngã tư trên mạng giao thông phụ thuộc vào hướng di chuyển của hàng hóa lưu thông: dòng rẽ phải, đi thẳng hay dòng rẽ trái và thậm chí có hướng bị cấm. Kết quả chính của bài báo là chúng tôi định nghĩa mô hình mạng giao thông mở rộng và xây dựng thuật toán tìm luồng cực đại trên mạng giao thông mở rộng.