Recently I have been studying the Ford-Fulkerson algorithm for determining max flow. I do not see why it is not allowed to have the source vertex be the same as the sink vertex. From what I have heard, doing this allows infinite flow. However if you take a graph where the source (which equals the sink) has no arcs leading into it shouldn't the max flow be $0$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
In a flow network, the source and sink are "special". The source is defined to have infinite incoming capacity, and the sink is defined to have infinite outgoing capacity -- they are different from all the other networks. For any node with no incoming edges other than the source, it's true that the flow through that node has to be zero -- but the source is different, because it is special.
Why can't the source and sink be the same node? Basically, because then you get a different problem with different characteristics. That other problem is called the circulation problem, and there are algorithms for it. They are a bit different, though, and your teacher probably doesn't want to confuse you by adding unnecessary complications.
$\begingroup$
$\endgroup$
In the Maximum Flow problem at first step you assume that source has $\infty$ capacity, if it had limited capacity you would denote that by auxiliary arc to node.
Then you cut it to comply with constraints - weighted edges gives capacity. Since there are no arcs with weights -> there are no limits, what you put in source is immediately in the sink.
Otherwise if source had $0$ capacity then there would be no flow at all.
