Lý thuyết đồ thị: Tách đồ thị

Question

Tôi gặp sự cố này. Tôi có một đồ thị của n nút mà tôi muốn chia thành hai subgraphs của các nút x và n-x tùy thuộc vào ràng buộc rằng số cạnh còn lại được tối đa hóa (hoặc giảm thiểu số cạnh được cắt).

Không chắc liệu điều đó có hợp lý hay không. Không phải là một người lý thuyết đồ thị nhưng đây là phiên bản trừu tượng của vấn đề của tôi. Tôi nên xem xét thuật toán nào có thể giúp tôi?

Đây KHÔNG phải là vấn đề về bài tập về nhà. Vấn đề thú vị mặc dù tôi nghĩ!

tôi có kế hoạch thực hiện trong C.

Answer 1

Trường hợp đặc biệt trong đó x = n - x được gọi là vấn đề chia nhỏ nhất và là NP-hard. Điều này làm cho vấn đề của bạn NP-cứng là tốt. Có một số chẩn đoán được mô tả trong bài viết trên graph partitioning trên Wikipedia, bao gồm tìm kiếm cục bộ (ví dụ, bắt đầu với một phép cắt ngẫu nhiên và lặp lại các cặp đỉnh làm giảm kích thước cắt) và phương pháp phổ (ví dụ: tính toán và ngưỡng đối tượng thứ hai) . Nếu n là nhỏ, lập trình số nguyên cũng là một khả năng.

Answer 2

Có lẽ một tìm kiếm đầu tiên chiều sâu trên các nút. Chúng tôi chỉ định từng nút một và đếm số lần cắt cho đến giờ. Nếu con số đó vượt quá số của giải pháp tốt nhất, thì chúng tôi sẽ hủy bỏ số này và quay lại.

1. Với tập hợp đầy đủ các nút S, chúng ta hãy P và P' được setsuts các nút, ban đầu trống rỗng, và K bằng số cạnh cắt, ban đầu 0.
2. Hãy S *, K * là giải pháp nổi tiếng nhất và số lượng cạnh cắt của nó, với K * ban đầu vô cùng.
3. Chọn một nút N để bắt đầu với và gán nó vào S.
4. Đối với mỗi nút M unassigned:
   1. Gán M để S', và thêm số cạnh từ M đến các hạch trong S để K.
   2. Nếu K> K *, thì không có giải pháp nào dựa trên điều này sẽ đánh bại tốt nhất, vì vậy hãy chỉ định M cho S.
   3. Nếu | S | > X, thì tập hợp đã phát triển quá lớn; quay lại.
   4. Nếu không, recurse từ 4.
5. Nếu tất cả các nút được giao và K < K *, sau đó cho phép S * = S và K * = K.

Tôi đã tưởng tượng này như một thuật toán kiểu Prolog, nhưng làm nó trong C không quá khó. Backtracking chỉ có nghĩa là bỏ gán nút được gán cuối cùng.

Answer 3

về cơ bản bạn đang xem xét phiên bản sửa đổi của sự cố cắt nhỏ.

Một cách để sửa đổi karger's algorythm Trong bản đồ của Karger, bạn hợp đồng các đỉnh dọc theo các cạnh ngẫu nhiên cho đến khi bạn kết thúc với chỉ hai đỉnh, các cạnh còn lại thể hiện vết cắt. Vì nó là ngẫu nhiên bạn chỉ cần làm điều này nhiều lần và giữ cho các giải pháp với các cạnh ít nhất trong cắt.

Trong phiên bản sửa đổi khi một đỉnh đã được thu gọn x lần bạn có thể ngừng thu gọn và đếm các cạnh đi (đây sẽ là vết cắt trong trường hợp của bạn), hãy thực hiện một lượng thời gian phù hợp và bạn có giải pháp. Phần khó khăn là tìm ra số lần lặp lại các phép tính để tăng độ tin cậy lên một giới hạn thỏa đáng