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

Question

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

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

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

Answer 1

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

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

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

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

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