Lưu lượng tối đa - Phát hiện Nếu một cạnh được tìm thấy trong một số phút cắt

Question

Cho một mạng G = (V, E), dòng tối đa f và cạnh e trong E, tôi cần tìm một thuật toán efficeint để phát hiện xem có một số vết cắt nhỏ có chứa e. Một câu hỏi khác là nếu tôi phát hiện ra e được chứa trong một số min-cut, là nó có thể phát hiện cho dù đó là cạnh nhẹ nhất trên cắt?

Tôi đã nghĩ đến việc chạy thuật toán Ford-Fulkerson và tăng/giảm dung lượng của cạnh đã cho và xem điều gì xảy ra, nhưng tôi chưa nghĩ ra điều gì đó có thể giúp tôi giải quyết vấn đề.

Tôi sẽ rất tuyệt nếu có ai có thể chỉ cho tôi giải pháp, cảm ơn trước.

Answer 1

Đây là giải pháp cho câu hỏi đầu tiên: Giả sử w(e) là trọng số của e, tính giá trị cắt nhỏ cho G, giả sử là C. Sau đó, chúng tôi xóa e từ G để thực hiện G'; một lần nữa chúng tôi tính toán giá trị cắt nhỏ cho G', giả sử là C', nếu C-C'>=w(e), thì điều này kết luận rằng e, tham gia ít nhất một phút cắt (mà bạn đã biết), nếu không e không thuộc bất kỳ min-cut nào .