Tìm cắt giảm tối thiểu trong biểu đồ sao cho đỉnh được ngắt bị ngắt

Question

Một số thời gian trước đây tôi đã đọc về thuật toán cắt chung mininum lấy làm đầu vào biểu đồ và loại bỏ phút. số cạnh như vậy mà hai thành phần bị ngắt kết nối vẫn còn.

Tôi hiện đang làm việc trên một đồ thị vô hướng với 10k + nút và 500k + cạnh (không có nhiều cạnh giữa hai đỉnh). Để gán các tương tác giữa các nút, tôi nghĩ về việc tính toán cắt giảm tối thiểu ngắt kết nối hai đỉnh cho trước (hoặc các biện pháp liên quan đến dòng chảy).

Có thuật toán hiệu quả nào để đưa ra một giá trị (cardinality của bộ cắt tối thiểu) cho mỗi cặp đỉnh trong biểu đồ không? Khá mới mẻ với chủ đề này, tôi sẽ rất biết ơn nếu có ai có thể cung cấp liên kết tới các bài báo hoặc các tài nguyên khác phác thảo các thuật toán hoạt động ở độ phức tạp thời gian chạy hợp lý.

Cảm ơn!

Answer 1

Có một số thuật toán (xem Wiki để được giới thiệu) tìm thấy luồng tối đa trong mạng. Những người tôi biết (Ford-Fulkerson, Dinic, Karp-Edmond) nên hoạt động tốt cho công suất đơn vị (= dung lượng nguyên bằng 1 trên tất cả các cạnh) (khả năng biến tăng độ phức tạp và nhiều vấn đề phát sinh với dung lượng không nguyên)

Đối với bất kỳ cặp đỉnh nào, bạn tạo một mạng từ biểu đồ bằng cách đặt nguồn/bồn rửa cho cặp này. Bạn nhận được luồng tối đa bằng một trong các thuật toán mà bạn sử dụng để cắt giảm như sau:

• Chọn bất kỳ cạnh nào được sử dụng bởi luồng. Cạnh này sẽ thuộc về phần cắt.
• Lặp lại, nhưng bây giờ thực hiện tìm kiếm dòng chảy trên một đồ thị mà không cạnh được lựa chọn (s) cho đến khi dòng chảy là 0

Cuối cùng, bạn phải cắt giảm tối thiểu, kích thước của dòng chảy tối đa.

Nếu bạn thực sự muốn nhấn vào hiệu suất, bạn có thể muốn xem bài báo này: Flows in Undirected Unit Capacity Networks (1997) bởi Andrew V. Goldberg, Satish Rao, nhưng tôi có thể gắn bó với những thứ đơn giản hơn.