Algorithms: Introduction to the Maximum Flow Problem

Problem Definition: The maximum flow problem is a stone-cold classic in the design and analysis of algorithms. Its easy to understand intuitively, so lets do an informal example before giving the formal definition.

Formally, an instance of the maximum flow problem is specified by the following ingredients:

a directed graph G, with vertices V and directed edges E;

a source vertex s ? V ;

a sink vertex t ? V ;

a nonnegative and integral capacity for each edge e ? E

Please provide at least three examples of maximum flow problems. Explain why those three examples are maximum flow problem and use directed graphs and display such graphs and information on the Chegg website. Expand on the formal definition that is to say explain why the formal definition defines maximum flow problems. Why are maximum flow problems compared to shortest path problems?