I recently got interested in graph theory. I came across the s-t cut for a directed graph. I learned online that the min-cut is equal to the max flow and there are standard algorithms out there that can solve the s-t min cut for a directed graph.
But I can't seem to find much material about the s-t cut for undirected graph, I see people mentioning that I could just replace an undirected edge with two directed edges in opposite directions to convert the undirected graph into a directed graph. However when I find the max flow or the min cut of the new directed graph, why does it have anything to do with the original undirected graph? I imagine the min-cut for the new directed graph normally should only contain one of the uv
and vu
edges but not both.
I just don't see how the converted directed graph has anything to do with the original undirected graph.
In a max-flow/min-cut problem, you can not have the idea of undirected graph actually. The graph may not have directions along with the edges. However, you need to get a flow from
s
tot
anyway, and when you will find it, you will end up with a directed graph right (the flow paths/augmenting paths from s -> t)?I hope you already know the idea of solving max-flow problems using the Ford-Fulkerson algorithm. Even if you have an undirected graph, you can still find a path from
s -> t
and make a flow along in that path. Whenever you are adding some flow in a path, you need to add the backward edges having the same flow in the updated residual graph.I strongly recommend watching the video that I have linked above, if you do not understand the Ford-Fulkerson algorithm. This is really interesting.
If you find the max-flow from
s
tot
in a graph, then you can find the min-cut easily. Min-cut does not take the backward edges. Hence if you have bothuv
andvu
edges in the residual graph, onlyuv
will be considered in the min-cut (assuminguv
is in the direction ofs-t
).Hope that helps!