A network is a
simple, weighted, directed graph with a designated vertex, called source that
has no incoming edges, a designated vertex, called sink that has no
outgoing edges, and nonnegative weights. Within a network, the flow assigns
each edge a nonnegative number that does not exceed the capacity of the edge
such that for each vertex v, which is neither the source nor the sink,
the flow into v equals the flow out of v. The conservation of a
such flow refers to the equality of the flow into and out of a vertex. Multiple
sources of a network can be tied together into a single vertex called the
supersource. Multiple sinks of a network can be tied together into a single
vertex called the supersink. In a network N, a maximal flow is a
flow with maximum value. Algorithms to find maximal flow can be defined. A cut
in a network consists of a set P of vertices and the complement
~P of P, where the source is
in P and the sink is in ~P. The capacity of any cut is greater than or equal to
the value of any flow. A minimum cut is a cut having minimum capacity. If the
value of a flow equals the capacity of a cut, the flow is maximal and the cut
is minimal. This theorem is known as the Max flow, Min cut Theorem.
A matching M is a set of edges with no vertices in
common. A maximal matching for M is a matching containing the
maximum number of edges. A complete matching for G is a matching E
having the property that if v
Є V, then (v, w) Є E for some w Є
W. Hall’s Marriage Theorem states that there exists a complete matching
in G if and only if |S| ≤ |R(S)| for all S includes in V or
equals to V.
APPLICATIONS
1. Network models can be used in Warehouse to Factory. The vertices are the intersections of roads and the factories and warehouses. The edges are the roads with capacities of how much can be transported between the connected vertices. If there is more than one factory or warehouse, then the source (or sink) is an imaginary vertex that is connected to the factories (or warehouses) be edges with weights of the factories (or warehouses) production (or holding) capacity.
URL: http://www.core.binghamton.edu/~burner/app.html
2. Network models can be used
in Genetic Testing. The aims of the GIRC are to use mathematical modelling to
assess the impact of genetic testing on the insurance industry, policyholders
and care providers from an impartial point of view.
URL: http://www.ma.hw.ac.uk/ams/res/
QUESTIONS
1. Can a randomized Maximum-Flow
algorithm be always correct?
2. What is a residual
network?