Направленность mincut в потоковой сети

Question

Я не уверен, что у меня есть недоразумение в mincut, но я написал алгоритм mincut с использованием edmond-karps, за которым следует BFS в потоковой сети.

Если я скажу ему, чтобы сделать mincut от A до B, он работает, поскольку остаточный поток A-> B = 0, поэтому он производит множество {A} с разрезом A-> B (1).

Однако, если я скажу ему, чтобы сделать mincut от B до A, он не может увеличивать любые ребра (поскольку на C нет ребер), поэтому результирующий набор {C}, с разрезом B-> C (2).

Как я вижу это, я мог бы неправильно понять это одним из 2 способов. Во-первых, mincut от B до A может быть правильным, так как будут учитываться только края из набора B, а не ребра (что означает, что mincut задает вопрос «что такое минимум, чтобы B не мог подключиться к A», что является минимумом для разбиения графика на 2 раздела).

Или, если вас попросят найти минимальную линию в сети потока (общий мини-разрез, где я в настоящее время использую «выбор произвольного источника», попробовать все другие узлы»метод), она должна требовать равного потока в обоих направлениях на любом крае.

Answer 1

„правильный“мин-срез для„источника = B, раковина = А“= 0, так как нет ребра B-> A (эквивалентно, c (B, A) = 0), он выглядит как ваш imp lementation может отвечать на другой вопрос. Вы проверяете каждый возможный самый короткий путь на этапе BFS, чтобы убедиться, что он заканчивается на раковине?

(то есть mincut просит «что является минимальным, чтобы не допустить B к подключиться к», а не «, что является минимальным, чтобы разделить граф на 2 группы).

Да, первый: мы заботимся только об узких местах от источника до раковины (теорема о минимальном разрезе макс-потока). Min-cut делает «разделяет» график на две части, но есть дополнительное требование, чтобы источник и раковина находятся в отдельных наборах.

(общий мин крой, где я в настоящее время с помощью «выбрать произвольный источник, попробуйте все другие узлы») метод

Если вы говорите, «лечить все другие узлы в качестве поглотителей,» это является простым вычислением степени на внешних краях источника.

Редактировать: это не точно расчет степени, так как края взвешены, но это просто сложение веса края, поиск не требуется.

он должен требовать равного расхода в обоих направлениях на любом ребре.

Не существует такого требования (потоковые сети являются ориентированными графами - любые неориентированные ребра сопоставляются с двумя антипараллельными ребрами, а для конкретной задачи потока используется только один из ребер).