Bài viết 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 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. Mời các bạn tham khảo bài viết để hiểu rõ hơn về nội dung này. | Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 DOI: 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 Trần Ngọc Việt1, Trần Quốc Chiến2, Lê Mạnh Thạnh3 1 Cao đẳng CNTT Hữu nghị Việt-Hàn Đại học Sư phạm-Đại học Đà Nẵng 3 Đại học Huế 2 trviet01@, tqchien@, lmthanh1953@ 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 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. Từ khóa - đồ thị, mạng hỗn hợp mở rộng, luồng, luồng cực đại, thuật toán. I. ĐẶT VẤN ĐỀ Mạng và luồng trên mạng 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 mạng cổ điển mới chỉ xét đến trọng số của các tuyến và các nút 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 nút trên đường đi đó. Tuy nhiên, trong nhiều bài toán thực tế, trọng số tại một nút không giống nhau với mọi đường đi qua nút đó, mà còn phụ thuộc vào tuyến đi đến và tuyến đi khỏi nút đó. Ví dụ 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 phương .
