Để tìm lưu lượng tối đa trong biểu đồ, tại sao nó không đủ để làm bão hòa tất cả các đường tăng thêm với khả năng cạnh tối thiểu trong đường dẫn đó mà không xem xét các cạnh sau? Ý tôi là, điểm nào gọi nó là một lợi thế nếu chúng ta giả định dòng chảy từ nó?Tại sao các cạnh sau được yêu cầu trong thuật toán Ford-Fulkerson?
Cạnh sau là cần thiết khi thực hiện thuật toán Ford-Fulkerson trong trường hợp đường dẫn bạn chọn kết thúc không phải là một phần của luồng tổng thể.
Như một ví dụ nơi lại cạnh là cần thiết, hãy xem xét luồng trên mạng này:
s
/\
a b
\/\
c d
\/
t
Giả định rằng tất cả các cạnh chỉ xuống và rằng tất cả các cạnh có công suất 1 và bạn muốn tìm một dòng chảy từ s đến t . Giả sử trên lần lặp đầu tiên của Ford-Fulkerson bạn lấy đường dẫn s -> b -> c -> t. Tại thời điểm này, bạn đã đẩy một đơn vị lưu lượng từ s đến t. Nếu bạn không thêm vào bất kỳ cạnh nào, bạn còn lại với điều này:
s
/
a b
\ \
c d
/
t
Không có thêm đường dẫn s-t, nhưng điều đó không có nghĩa là bạn có luồng tối đa. Bạn có thể đẩy hai đơn vị của dòng chảy từ s đến t bằng cách gửi một dọc theo đường dẫn s -> a -> c -> t và đường khác dọc theo đường dẫn s -> b -> d -> t. Nếu không có bất kỳ cạnh sau nào trong mạng lưu lượng dư, bạn sẽ không bao giờ khám phá ra con đường khác này.
Hy vọng điều này sẽ hữu ích!
Bạn có thể vui lòng xem chi tiết hơn về những gì sẽ tạo nên các bản sao lưu trong trường hợp cụ thể của bạn không? Cảm ơn bạn! – bluejamesbond
@bluejamesbond Ở đây, các cạnh sau sẽ trỏ từ b đến s, từ c sang b, và từ t đến c (đó là đảo ngược các cạnh dọc theo đường đi). Các cạnh đó tạo ra một đường tăng từ s đến t cho thấy luồng không phải là cực đại. – templatetypedef
Tuy nhiên, khi nào nó sẽ đi theo những đường dẫn đó? – bluejamesbond