Cắt tối thiểu qua các đỉnh/nút - không phải cạnh

Question

tất cả chúng ta đều biết và yêu thích các thuật toán cắt tối thiểu, nhưng tất cả đều cắt qua các cạnh trong biểu đồ. Có bất kỳ biến thể nào cắt qua các nút không?

Answer 1

Vì vậy, để sử dụng thuật toán cắt tối thiểu s-t, bạn cần chuyển biểu đồ của mình thành một mạng luồng. Điều này đưa ra một đồ thị ngầm định hướng (hướng của luồng chuyển tiếp của một cạnh). Bạn có thể sử dụng biểu diễn trực tiếp này để biến biểu đồ thành thứ gì đó sẽ giải quyết vấn đề này. Về cơ bản bạn biến đổi mọi đỉnh, V, (không bao gồm nguồn và bồn rửa) thành hai đỉnh, gọi chúng là A và B. A nhận tất cả các cạnh của V, B lấy tất cả các cạnh ngoài của V. Sau đó bạn tạo cạnh A -> B với công suất cực đại vô hạn.

Tôi nghĩ rằng nếu bạn chạy thuật toán cắt tối thiểu s-t thông thường, nó sẽ chỉ chọn các cạnh bạn tạo. Sự thay đổi duy nhất tôi có thể nghĩ rằng điều đó là cần thiết trong trường hợp mức độ A là một, nó có thể chọn cạnh đó để cắt, nhưng chỉ cần chọn A làm đỉnh sau đó. (Điều này phụ thuộc vào việc triển khai thuật toán s-t)

Tôi hy vọng điều đó có ý nghĩa. Tôi không chắc chắn liệu điều đó có hiệu quả hay không (tức là tôi không cảm thấy muốn nghĩ ra một bằng chứng thích hợp), nhưng nó có ý nghĩa trực quan là nó sẽ thành công. Ý tưởng trực quan mà tôi có là nếu bạn cắt cạnh "không có đỉnh", bạn cũng có thể cắt cạnh "đỉnh" vì nó có tác dụng tương tự w.r.t để ngắt kết nối biểu đồ.