2
$\begingroup$

How does flow work ? I don't understand what they did. For example, why in the edged marked by 3, in the solution it's written 1 ? Morover, a maximum flow is the number a flow or the then longest flow ?

enter image description here

$\endgroup$
2
  • $\begingroup$ could the downvoter explain his downvote ? $\endgroup$
    – idm
    Jun 1, 2015 at 14:24
  • $\begingroup$ Other users than the downvoter themself can only speculate what was the reason for the downvote. But if you wish to discuss the reason for the downvote, there is a chatroom explicitly for this purpose. $\endgroup$ Jun 2, 2015 at 7:33

1 Answer 1

1
$\begingroup$

A flow from $s$ to $t$ is an assignment of values to the edges of the graph, but the flow has a value that indicates how much is flowing from $s$ to $t$.

There are algorithms you can run to calculate the flow network, and then see what the value is.

In your example, the top graph shows the capacities of each edge, and the bottom graph shows a max flow. The edge with 3 on it has a capacity of three, but in the given max flow, it can only transmit 1. We could come up with another max flow where it transmits two, but since $t$ only has an incoming capacity of 2, there's no max flow where that edge can transmit 3.

To think about capacities, imagine edges as pipes, with a size defined by their capacity. An edge with a capacity of 3 can transmit three units of stuff from one vertex to another. So if there's only one unit of stuff going through that edge in a max flow, it means that capacity in the network is limited somewhere else.

Wikipedia has decent writeups on flow networks and max flow problems.

$\endgroup$
7
  • $\begingroup$ I'm sure that your answer is great (I will valide and up vote your answer when I'll totally understand every thing. So don't worry about that :-)). Could you tell me intuitively what you call by "capacity" ? I have a definition in my book, but I don't see exactly what it is. Thanks a lot :-) $\endgroup$
    – idm
    Jun 1, 2015 at 19:46
  • $\begingroup$ @idm gave it a shot. If you want we can drop into chat and edit the results into the answer. $\endgroup$
    – dsolimano
    Jun 1, 2015 at 20:09
  • $\begingroup$ It would be a pleasure to me. Tomorrow is fine to you ? It's time to me to sleep. Thanks a lot and sweet dreams :-) $\endgroup$
    – idm
    Jun 1, 2015 at 21:37
  • $\begingroup$ @Idm I'm in chat.stackexchange.com/rooms/24186/why-no-upvotes if you need more clarification. $\endgroup$
    – dsolimano
    Jun 2, 2015 at 16:49
  • $\begingroup$ Just moved to chat.stackexchange.com/rooms/18279/… $\endgroup$
    – dsolimano
    Jun 2, 2015 at 17:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .