NETWORK MODELS

 

  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?