2
$\begingroup$

So, there can be different types of edges in a directed graph while solving the max flow problem. There can be reverse edges, multiple edges and self loops.

What is the significance of self loops in it?

How is it related to flow in the graph?

Let there be a graph like this 1->2->3 and 2 has a self loop. So, can I interpret it like this-

1->2a--2b->3 ? where -- denotes an edge from 2a->2b and an edge from 2b->2a.

So, How would I represent this in a graph using adjacency list?

$\endgroup$
  • 2
    $\begingroup$ I don't follow what your actual question is. I recommend you execute a max-flow algorithm on your examples and see what happens. Or mathematically, if you are so inclined, figure out how the flow along a self-loop influences the aggregate flow value. $\endgroup$ – Raphael Apr 3 '18 at 18:04
1
$\begingroup$

for the max flow problem you should remove the self loops and solve it. self loops don't effect on final solution because when there exists a loop on a vertex, it means a flow from the vertex (with an arbitrary capacity) goes on pipe that connect to itself, it means the flow doesn't waste, it just return to the vertex. it's like you connect a water hose from a tank to itself. you don't limit the input flow to the tank or output flow from it. so you can ignore self loops and solve the problem.

$\endgroup$
  • $\begingroup$ Perhaps you can explain in more detail why self loops don't affect the solution? $\endgroup$ – Yuval Filmus Apr 4 '18 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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