Weighted graphs

                                                         WEIGHTED GRAPHS

A graph in which every edge is assigned a +ve number is called weighted graph.


  Directed graphs or Di_graphs

                                                                               It is a graph in which every edge is given a direction.


Here in the graph edge between A and b are directed edge.But B to A is not a directed edge.There is no edge as  such from B to A.

                                                         Flows

                                        In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, except when it is a source, which has more outgoing flow, or sink, which has more incoming flow. A network can be used to model traffic in a road system, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.
 Capacity        
                                                                Capacity of a directed edge is the numeric value.Capacity is a function from the set of all edges from natural function .A flow is a function.
   

                                                           Cuts

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.

In an unweighted undirected graph, the size or weight of a cut is the number of edges crossing the cut. In a weighted graph, the same term is defined by the sum of the weights of the edges crossing the cut.

In a flow network, an s-t cut is a cut that requires the source and the sink to be in different subsets, and its cut-set only consists of edges going from the source's side to the sink's side. The capacity of an s-t cut is defined by the sum of capacity of each edge in the cut-set.

The cut of a graph can sometimes refer to its cut-set instead of the partition.

  Definition   

               A cut C=(S,T) is a partition of V of a graph G=(V,E).
An s-t cut C=(S,T) of a network N=(V,E) is a cut of N such that s\in S and t \in T, where s and t are the source and the sink of N respectively.
The cut-set of a cut C=(S,T) is the set \{(u,v)\in E | u\in S, v \in T\}.
The size of a cut C=(S,T) is the number of edges in the cut-set. If the edges are weighted, the value of the cut is the sum of the weights.
     
Minimum cut

A cut is minimum if the size of the cut is not larger than the size of any other cut. The illustration on the right shows a minimum cut: the size of this cut is 2, and there is no cut of size 1 because the graph is bridgeless.

The max-flow min-cut theorem proves that the maximum network flow and the sum of the cut-edge weights of any minimum cut that separates the source and the sink are equal.


Maximum cut
                          A cut is maximum if the size of the cut is not smaller than the size of any other cut. The illustration on the right shows a maximum cut: the size of the cut is equal to 5, and there is no cut of size |E| because the graph is not bipartite (there is an odd cycle).

In general, finding a maximum cut is computationally hard. The max-cut problem is one of Karp's 21 NP-complete problems. The max cut problem is also APX-hard, meaning that there is no polynomial-time approximation scheme for it unless P = NP.

                             Max-flow min-cut theorem

                                                                    In optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the minimum capacity that when removed in a specific way from the network causes the situation that no flow can pass from the source to the sink.