mạng Modeling theo chỉ dẫn graph

Question

Tôi có một mạng có thể trông như thế này:

Về cơ bản, tôi muốn biết số lượng tối thiểu của các vòng tròn màu xanh lá cây có thể ngắt kết nối nguồn và ráo nước nếu loại bỏ/vô hiệu hóa. (trong trường hợp này là 1)
Tôi đã triển khai thành công trình giải thuật Edmonds-Karp, nhưng tôi không biết cách lập mô hình mạng với các cạnh được chỉ dẫn, vì vậy tôi nhận được kết quả mong muốn.
Nếu tôi chỉ thay thế mỗi kết nối giữa các nút với hai cạnh hướng đối diện với dung lượng 1, tôi nhận được luồng tối đa là 2 với EdmondsKarp, nhưng tôi chỉ cần xóa 1 vòng tròn màu xanh lá cây để ngắt mạng.
Làm cách nào để tạo mô hình mạng của mình dưới dạng các nút và được chỉ dẫn bằng lưỡi?

Answer 1

Bạn có thể giảm vấn đề này xuống vấn đề cắt không tiêu chuẩn trong biểu đồ được chỉ dẫn, sau đó có thể giải quyết được ví dụ: bằng thuật toán Edmonds – Karp. Đối với mỗi v đỉnh, tạo hai đỉnh v_in và v_out và cạnh chỉ đạo (v_in, v_out) và cho mỗi cạnh {v, w}, thêm hai cạnh được hướng (v_out, w_in) và (w_out, v_in). Sau đó không khó để thấy rằng luồng cực đại từ s_in đến t_out tương ứng với một đỉnh cắt tối thiểu giữa s và t.

Answer 2

Bạn đã xác định luồng tối đa được xác định chính xác - đó là 2 cho mạng của bạn.

Từ định nghĩa của flow network

Một dòng chảy phải đáp ứng các hạn chế rằng lượng dòng chảy vào một nút bằng với lượng dòng chảy ra khỏi nó, trừ khi nó là một nguồn, trong đó có dòng chảy hoặc bồn rửa lớn hơn, có lưu lượng đến khác

Vì vậy, đối với nút giữa bạn có 2 dòng tối đa (vào và ra). Vì vậy, chỉ biết luồng tối đa sẽ không cung cấp cho bạn câu trả lời cho việc cắt giảm tối thiểu.

Định lý

max-flow min-cắt bang lý rằng trong một luồng trên mạng, số tiền tối đa dòng chảy đi từ nguồn đến bồn rửa là tương đương với công suất tối thiểu mà khi loại bỏ một cách cụ thể từ mạng gây ra tình hình rằng không có dòng chảy có thể vượt qua từ nguồn vào sink

như vậy, có bạn biết số lượng dòng chảy bạn cần phải loại bỏ, nhưng bạn không biết theo cách nào để loại bỏ nó. Tôi nghĩ rằng đây không phải là tầm thường và bạn sẽ cần phải tìm kiếm cụ thể để cắt giảm.