Giả sử có 3 nút đích trong biểu đồ.Làm cách nào để tìm tất cả các đường phân tách đỉnh trong biểu đồ?
Đường dẫn phân tách đỉnh có nghĩa là không có bất kỳ nút nào ngoại trừ nút kết thúc trong đường dẫn.
Đối với bất kỳ một nút đơn nào, hãy nói nút i, cách tìm tất cả đường dẫn phân tách đỉnh từ nút i đến ba nút đích?
Bạn có thể giải quyết vấn đề này bằng cách giảm nó thành vấn đề dòng chảy tối đa trong biểu đồ được xây dựng thích hợp. Ý tưởng là như sau:
Ý tưởng đằng sau công trình này là như sau. Mọi đường dẫn luồng từ nút bắt đầu đến nút đích t phải có dung lượng một, vì tất cả các cạnh đều có công suất. Vì tất cả các khả năng là không thể thiếu, có tồn tại một dòng tối đa không thể thiếu. Không có hai đường dẫn lưu lượng có thể đi qua cùng một nút trung gian, bởi vì khi đi qua một nút trong biểu đồ đường dẫn luồng phải vượt qua cạnh từ v trong đến v ra và khả năng ở đây đã bị hạn chế. Ngoài ra, đường dẫn lưu lượng này phải đến t bằng cách kết thúc tại một trong ba nút đặc biệt mà bạn đã xác định, sau đó đi theo cạnh từ nút đó đến t. Do đó, mỗi đường dẫn lưu lượng biểu thị một đường dẫn nút-disjoint từ nút nguồn đến một trong ba nút đích. Theo đó, việc tính toán lưu lượng tối đa ở đây tương ứng với việc tìm số lượng tối đa các đường phân tách nút mà bạn có thể lấy từ s đến bất kỳ đích nào trong ba đích.
Hy vọng điều này sẽ hữu ích!
Có lẽ biểu hiện của tôi abt vertex-disjoint không đủ rõ ràng. Đối với nút s và nút t, có một đường dẫn s-> a-〉 b-> c-> d-> t, cũng có một đường dẫn khác bắt đầu từ s như s-> e-> f-> g-> h -> t. Trong trường hợp này, đây là một đường phân tách đỉnh. Nhưng nếu có một đường dẫn là s-> e-> f-> g-> d-> t, thì đây không phải là điểm phân tách đỉnh. – datcn
@templatetypedef Đó là một lời giải thích rất tốt. Cảm ơn ! – ggauravr
Điều gì sẽ là thời gian chạy của giải pháp này? O (nm)? – razshan
Để được rõ ràng, bạn có nghĩa là một con đường bắt đầu tại 'i', đi qua mỗi một trong ba nút đích, và sau đó trở về' i' mà không lặp lại ngoại trừ hai đầu là như nhau? Ngoài ra, bạn có muốn tìm tất cả các đường dẫn như vậy (như bạn nói) hoặc đường dẫn ngắn nhất như vậy (như được gắn thẻ) không? – Dougal
Trong mục đích của tôi, tôi muốn tìm một con đường bắt đầu với nút i và kết thúc tại nút đích, nói nút z. Nếu có nhiều hơn một đường dẫn, sẽ không có các nút giống nhau trong các đường dẫn này ngoại trừ các nút i và nút z. Tôi hy vọng sẽ tìm thấy tất cả những con đường này từ i đến z. – datcn
Ồ, đó là rất khác với những gì tôi (và templatetypedef) hiểu. Vì vậy, bạn muốn tìm một tập hợp các đường dẫn từ 'i' sang' z' sao cho các đường dẫn rời rạc? Có khả năng nhiều bộ như vậy (tùy thuộc vào đường dẫn bạn có thể chọn). Vì vậy, có lẽ những gì bạn muốn làm là tìm tất cả các đường dẫn từ 'i' đến' z' (thông qua tìm kiếm bề rộng đầu tiên) và sau đó xử lý chúng để tìm một tập hợp rời rạc. Một cách dễ dàng để làm điều đó, mà sẽ không tìm thấy tập hợp lớn nhất như vậy hoặc bất cứ điều gì: chọn một đường dẫn từ tập hợp, loại bỏ tất cả các đường dẫn khác giao nhau đường dẫn đó, lặp lại. – Dougal