St Cut для неориентированного взвешенного графика

Question

Недавно я заинтересовался этой теорией графов. Я наткнулся на разрез для ориентированного графа. В Интернете я узнал, что минимальное сокращение равно максимальному потоку, и существуют стандартные алгоритмы, которые могут решить минимальное сокращение для ориентированного графа.

Но я не могу найти много материала о срезе для неориентированного графа, я вижу, как люди упоминают, что я мог бы просто заменить неориентированный край двумя направленными ребрами в противоположных направлениях, чтобы преобразовать неориентированный граф в ориентированный граф. Однако, когда я нахожу максимальный поток или минимальный разрез нового ориентированного графа, почему это имеет какое-либо отношение к исходному неориентированному графу? Я предполагаю, что минимальный разрез для нового ориентированного графа обычно должен содержать только одно из краев uv и vu, но не оба.

Я просто не вижу, как преобразованный ориентированный граф имеет какое-либо отношение к исходному неориентированному графу.

Answer 1

В задаче о максимальном потоке / минимальном разрезе вы не можете иметь представление о неориентированном графе. График может не иметь направления вместе с ребрами. Тем не менее, вам нужно получить поток от s в t во всяком случае, и когда вы найдете его, вы получите направленный граф справа (пути потока / пути увеличения от s -> t)?

Я надеюсь, что вы уже знаете идею решения задач с максимальным расходом с помощью алгоритма Форда-Фулкерсона. Даже если у вас есть неориентированный граф, вы все равно можете найти путь от s -> t и плыть по этому пути. Всякий раз, когда вы добавляете некоторый поток в путь, вам нужно добавить обратные ребра, имеющие такой же поток, в обновленном остаточном графе.

Я настоятельно рекомендую посмотреть видео, которое я привел выше, если вы не понимаете алгоритм Форда-Фулкерсона. Это действительно интересно.

Если вы найдете максимальный поток от s в t на графике, вы можете легко найти мин-разрез. Min-cut не принимает задние края. Следовательно, если у вас есть оба uv а также vu ребра в остаточном графе, только uv будет рассмотрено в мин-разрезе (при условии uv в направлении s-t).

Надеюсь, это поможет!