2
$\begingroup$

I was wondering. May the source and sink have in-out going edges in a flow-network, and if so - does Ford-Fulkerson and the max-flow min-cut theorem apply ?

Flow-networks are always pictures with no edges entering source, and no edges leaving sink.

I've tried to search the web for an answer, but did not come across an answer i fully understand. Also, I've yet to see a flow network pictured with these edges from source/sink.

Could I transform an undirected graph into a flow-network ? This network will have edges going into source and edges leaving sink ?? This hypothesis is the reason for my question.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Have you looked in a textbook and checked the requirements stated there? Try to think about what the existence of such edges would mean for an optimal flow. $\endgroup$
    – Raphael ♦
    May 19, 2013 at 15:04
  • $\begingroup$ It would mean nothing right ? I mean the optimal flow would be the same ? The equality at every node means that there cannot go more in than out. $\endgroup$
    – Shuzheng
    May 20, 2013 at 8:00
  • $\begingroup$ The equality at every node is usually not enforced for source and sink. Why do you want to turn an undirected graph to a flow network? For most applications its useful to add new vertices as sink and source. $\endgroup$
    – frafl
    May 23, 2013 at 13:51
  • $\begingroup$ These types of problems exist when we have multiple resources and destinations. To compute a max flow, we simply append a super source with out edges to all initial source nodes and a super sink with in edges from all initial sink nodes. $\endgroup$
    – koverman47
    Jul 23, 2018 at 18:41

3 Answers 3

Reset to default
2
$\begingroup$

Yes, it's possible.

My source is 'Graph Theory and its Applications', 2nd ed, by Gross & Yellen, page 540, question 13.1.8:

Some authors define an s-t network such that the source s must have indegree 0 and t must have outdegree 0. Describe how a network whose source and sink do not satisfy these additional requirements can be transformed by graphical operations into one whose source and sink do meet such requirements.

However, it doesn't give the construction, I can only think that it would be by adding a supersource and a supersink, as you'd usually do with multiple (though standard) sources and sinks, to 'soak up the leakage'. I am not sure though.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 Super source and super sink are the key here. Typically problems (as described by the OP) have these two new nodes, with necessary edges, integrated into the original graph $G$, to make a new graph $G'$ with only 1 source (with no in-flow) and 1 sink (with no out-flow). $\endgroup$
    – koverman47
    Jul 23, 2018 at 18:37
2
$\begingroup$

Whether you consider edges in- and out- edges to and from the source and sink, resp. will not change the solution. One usually ignores them, because you do not need to consider those edges (in the Ford-Fulkerson algorithm, for example).

Consider one of several edges emergent from the source. If after choosing a path from source to sink it turns out that you would have an arc in the residual graph to the source, it means that you still have some capacity left. But you will never consider a path going into the source. The goal is to find how much flow can go through the graph from the source to the sink. You just subtract the flow going through the path just analysed, and move on to the next one until no more flow can go though the graph.

You may take a look at Jeff Erikson's notes. I find them great.

Is your question motivated by the GraphCut problem in machine vision?

In that case you do not need to transform the graph, just to decide where to start clamp your source and your sink (usually at opposing corners of the image).

Improve this answer
$\endgroup$
1
$\begingroup$
  1. Depends on the definition (so there are definitions which are compatible)
  2. Do you really want to turn existing vertices of your undirected graph to sink and source?
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.