# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

Search                 Browse                 Forum               Coach                 Links                 Editor                 Help                 Tell-a-Friend                 Encyclopedia                 Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Max flow min cut theorem

(Redirected from Maximum flow problem)

The max flow min cut theorem is a statement in optimization theory about optimal flows in networks.

Suppose G is a finite directed graph and every edge e has a capacity w(e), a non-negative real number. Further assume two vertices s and t have been distinguished. Think of G as a network of pipes; we want to pump as much stuff as possible from the source s to the sink t, never exceeding any edge's capacity.

A flow f on G from s to t assigns to each edge e a real number f(e) with 0 ≤ f(e) ≤ w(e) such that for every vertex x of G different from s and t, we have

$\sum_{e \; \in \; I(x)} f(e) = \sum_{e \; \in \; O(x)} f(e)$

where I(x) is the set of all incoming edges of x and O(x) is the set of all outgoing edges of x ("whatever goes in must come out"). For such a flow, we automatically have

$\sum_{e \; \in \; O(s)} f(e) \; - \sum_{e \; \in \; I(s)} f(e) \quad = \quad \sum_{e \; \in \; I(t)} f(e) \; - \sum_{e \; \in \; O(t)} f(e)$

this number is called the amount of the flow. Intuitively, it is the net total amount of stuff we are pumping from s to t. We are interested in flows with maximal amount.

A cut C on G between s and t is a set of edges such that every directed path from s to t passes through at least one edge in C. The capacity of the cut C is the sum of all its edge capacities.

The statement of the theorem is:

The maximal amount of a flow is equal to the capacity of a minimal cut.

Note that there may be several flows which attain the maximum amount, and there may be several cuts which attain the minimal weight.

There is a partial correspondence between maximal flows and minimal cuts: if C is a minimal capacity cut, then there exists at least one maximal value flow f such that f(e) = w(e) for all e in C. Conversely, if f is a maximal flow, then there is a minimal cut C such that f(e) = w(e) for all e in C.

The theorem was proved by A. Feinstein and C.E. Shannon in 1956, and independently also by L.R. Ford, Jr. and D.R. Fulkerson in the same year. Determining maximum flows is a special kind of linear programming problem, and the max flow min cut theorem can be seen as a special case of the duality theorem for linear programming.

Maximum flows can be computed with the Ford-Fulkerson method, which is most commonly implemented according to the Edmonds-Karp algorithm. This implies that the maximum flow of a graph with integer capacities has an integer value as well. Another way to prove this is to notice that one of the linear programming formulations of the max flow problem has a totally unimodular constraint matrix, and so has integer solutions.

## External link

A review of current literature on computing maximum flows

03-10-2013 05:06:04
Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines.

Start by looking for your science kit review or science toy review. Compare prices but remember, Price \$ is not everything. Quality does matter.

Science Fair Coach 						            What do science fair judges look out for?
ScienceHound 						            Science  						            Fair Projects for students of all ages

All Science Fair Projects.com Site  		      All Science Fair Projects Homepage
Search  		    | Browse  		    | Links  		    | From-our-Editor 		    | Books  		    | Help  		    | Contact  		    | Privacy 		    | Disclaimer 		    | Copyright Notice
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 2, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9329429268836975, "perplexity_flag": "middle"}