Java - Biểu đồ liên kết quan trọng

Question

Tôi có một biểu đồ trong đó tôi có hai nút (0 và 6) và tôi phải cắt các cạnh ít nhất có thể để chúng không được kết nối. Ví dụ trong đồ thị này

Là các nút 0 và 6 cạnh nhất mà tôi phải cắt giảm là 2-7 và 3-7. Ý tưởng của tôi là tìm ra con đường ngắn nhất giữa cả hai sử dụng bfs, tôi tìm thấy một (0-2-7-6) nhưng sau đó tôi không biết làm thế nào để tìm khác (0-3-7-6). Thậm chí sau đó tôi không có ý tưởng làm thế nào lựa chọn các cạnh để cắt.

Sẽ rất tuyệt nếu ai đó có thể cho tôi một số gợi ý về vấn đề này.

Answer 1

Vấn đề này có vẻ rất giống với việc tìm các nút khớp trong biểu đồ. Định nghĩa kỹ thuật của một điểm khớp nối, hoặc một thành phần hai thành phần là một nút có loại bỏ sẽ làm cho một đồ thị được chia thành hai.

Việc phát hiện ra các nút khớp nối từ một đồ thị là một vấn đề chủ yếu là giải quyết và bạn có thể tìm thêm thông tin chi tiết về nó ở đây: http://en.wikipedia.org/wiki/Biconnected_component

Dường như với tôi rằng cách bạn muốn tiếp cận một vấn đề như thế này nói chung sẽ một cái gì đó dọc theo những dòng:

1. Find all articulation points 
2. Do a bfs from each node and determine articulation points along the path 
3. Split graph at the articulation point, choosing the side with minimal edges 
4. Continue until the two nodes are not connected 

Trong ví dụ trên, 7 là điểm khớp chỉ và do đó bạn sẽ snip các cạnh giữa 7, 2 và 3 kể từ khi chỉ có hai mép giữa 7 và 0-4 biểu đồ và 3 cạnh giữa 7 và đồ thị 5,6,8.

Có một thuật toán được thiết lập để thực hiện việc này (đọc: một thuật toán mà tôi không đưa ra) được gọi là thuật toán của Karger có thể giải quyết được vấn đề của bạn, mặc dù trong thời gian n^2.

Thuật toán đó hoạt động bằng cách nối các nút lân cận với nhau một cách hiệu quả cho đến khi chỉ có hai nút và sau đó đếm số cạnh trái giữa hai nút. Số lượng cạnh là số lượng cắt giảm tối thiểu cần thiết để chia biểu đồ.

Cách bạn thực hiện thuật toán của Karger trong vấn đề của bạn sẽ chỉ cần báo trước rằng bạn nên luôn luôn tham gia các nút với hai nút bạn muốn tách. Ngoài ra, để có thể quay trở lại các cạnh ban đầu bạn cần cắt, bạn nên giữ một tham chiếu đến các nút mà các cạnh ban đầu thuộc về.

Có một hình dung vĩ đại của thuật toán karger đây: http://en.wikipedia.org/wiki/Karger%27s_algorithm

Answer 2

gì bạn muốn là một vết cắt phút s-t. Cách thông thường để tìm một trong một đồ thị chung là chạy một thuật toán như push relabel với nguồn 0 và sink 6, tính toán một sự cắt giảm s-t min như một sản phẩm phụ của việc tính toán một luồng tối đa.

Thuật toán của Kargo tìm thấy một cắt nhỏ, tức là, nó giảm thiểu trên s và t cũng như cắt giảm. Kể từ khi s và t được cố định cho bạn, Karger là không thích hợp. Một khớp nối là một đỉnh mà loại bỏ của nó ngắt kết nối đồ thị. Bạn đang quan tâm đến việc loại bỏ các cạnh, không phải đỉnh.