0
$\begingroup$

I have tried a lot on internet, but I am unable to get a good answer on the difference between maximal and maximum flow in case of network flow. Anybody has an idea? with example would be really helpful.

$\endgroup$

2 Answers 2

3
$\begingroup$
  • A maximum flow is a flow that attains the highest flow value possible for the given network.
  • A maximal flow is a flow whose value cannot be increased without decreasing the flow along some arc.

All maximum flows are maximal flows. Not all maximal flows are maximum flows.

Figure 3.9 in the Bang-Jensen and Gutin textbook, first edition illustrates an example of a flow that is maximal but not maximum.

The difference is very much analogous to the difference between a global optimum and a local optimum.

$\endgroup$
-3
$\begingroup$

Both terms refer to the same thing. In the Wikipedia article on the maximum flow problem both terms are used equivalently. There you can also find some references to scientific publications that use both terms.

$\endgroup$

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.