Giáo trình Đồ thị và các thuật toán - Chương 7: Mạng vận tải

1. Giả sử rằng mỗi cung cứa đồ thị không chỉ được gắn với khả năng qij cho biết cận trên của luồng trên cung (vi,Vj) mà còn “khả năng” cho cận dưới của luồng trên cung này. Trong trường hợp như vậy, không phải lúc nào một tập chấp nhận được các giá trị của luồng cũng thoả mãn cùng lúc hai ràng buộc này. Tuy nhiên-nói chung-nhiều luồng thoả điều kiện này, và nếu ngoài các khả năng còn có các chi phí Cịj tương ứng một đơn vị luồng dọc theo các cung, thì bài toán trở thành tìm luồng chấp nhận đuọc với chi phí nhỏ nhất từ s đến t.

2. Xét trường hợp đòi hỏi luồng lớn nhất giữa mọi cặp đĩnh. Mặc dù bài toán này có thể giải bằng n(n — l)/2 lần lặp các bài toán luồng lớn nhất từ s đến t nhưng cách làm này quá thô! Tương tự với tìm tất cả các đường đi ngắn nhất, ở đây cũng cần