APPLICATION OF GRAPH THEORY

Graph theory is being used in many fields now.In computer science and  in other fields many concepts are based on the graph theory.below is one link which will take you to the applications of graph theory at a glance.                                 

                                                 Applications of graph theory

                     Famous problem solved using graph theory

7 bridges of konnisberg is a famous celebrated problem which is solved using the graph theory.WATCH THIS VIDEO.THIS WILL GIVE AN IDEA ABOUT WHAT IS THE POWER OF GRAPH THEORY.

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.

Trees

                                             TREES 

Trees is a special type of graph,which is acyclic and connected or a connected acyclic  graph is called a tree.

                             eg;paths and stars.

This is a tree.It is also called as connected cycle free graph.

A graph is said to be a tree ,if and only if there exists a unique path between every pair of vertices.

                                                       Coloring of graphs

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Vertex coloring is the starting point of the subject, and other coloring problems can be transformed into a vertex version. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as is. That is partly for perspective, and partly because some problems are best studied in non-vertex form, as for instance is edge coloring.

The convention of using colors originates from coloring the countries of a map, where each face is literally colored. This was generalized to coloring the faces of a graph embedded in the plane. By planar duality it became coloring the vertices, and in this form it generalizes to all graphs. In mathematical and computer representations, it is typical to use the first few positive or non negative integers as the "colors". In general, one can use any finite set as the "color set". The nature of the coloring problem depends on the number of colors but not on what they are.

Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of research.

This is an example of  vertex coloring.This graph is having proper coloring,because no two adjacent vertices are having same color.The minimum color used is 3.So 3 is the chromatic number of the graph.Chromatic number of the graph is the minimum number of colors needed to have a proper coloring of the graph.

Applications

                    

                                                                                        This is the typical application of coloring of the graph.Here in the map no two adjacent states are having same color.So this technique is used effectively in map creation.

                                                      Rooted trees

A tree with a vertex designated as root and drawn in such a way that every other vertex is coming out of it is called a rooted tree.

In a rooted tree every vertex other than the root with degree 1 is called a leaf.In a rooted tree every vertex other than a half is called an internal vertex.

                                            If m+1 is the maximum degree among all the degree of internal vertices ,then the tree is called an m-ary tree.If every internal vertex has got exactly one degree then that tree is called full m-ary tree.

                                              Minimal spanning tree

Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.
Here the parrt drawn in dark lines denotes the minimum spanning tree of the graph

Hamiltonian cycles

                                                              HAMILTONIAN CYCLE

It is a cycle in a graph where every vertex is used once and only once.

                                                   Here 123451 is a cycle in which every vertex is used once and only once.so this graph is a Hamiltonian graph.

                                                             HAMILTONIAN PATH

It is a path in a graph where vertex is used once and only once

                                                        Here 1425631 is a Hamiltonian path.


                                             Theorems associated with Hamiltonian cycle 

• Ove's Theorem          

                                 If a graph with n vertices has every verex of degree >=n/2,then it has a Hamiltonian cycle. 

• Dirac's Theorem

                               If in a graph with n vertices for every pair of non-adjacent vertices u,v if d(u)+d(v)>=n,then it is a Hamiltonian cycle

                                        Connected graphs

A network is said to be connected if between every pair of vertices there exists atleast one path.

                                                       

                           A graph which is not connected is called a disconnected graph.

                                                                     Subgraph of a graph

                                          A subgraph of a graph is a graph with either less number of vertices or edges than that of the given graph.
                                           A spanning sub graph of a graph is a sub graph which retains all the vertices of the original graphs.


                                                                       Component

Given any graph G,a component of G,say G1 is a maximal connected sub graph of G.(ie.G1 should not be a proper sub graph of another connected sub graph of G. If G itself is connected then it has only one component. ie .G itself.

walks

                                          Walks

Walk is a continuous sequence of vertices and edges starting with a vertex and ending with another vertex with the possible repetition of edges or vertices or both.

An example for a walk 

:: 

                            In a walk if neither vertices nor edges are repeated,it is called a path.


                                                        Here no vertices or edges are repeated .so this is a path.

y-w-u-v-w-x::::this is not a path,it is a walk.
length of a walk or path:-Number of edges in a path or a walk is called the length of the path or the walk.

CIRCUIT

Circuit is a continous sequence of vertices and edges starting and ending at the same vertex,with the possible repetition of edges or vertices.because neither the vertices or nor the edges are repeated the circuit becomes cycle.

  

                                                            EULER GRAPH

In a circuit in a graph were all the edges of the graph are used once and only once.In such cases the graph is called as Euler graph.Every cycle is a Euler circuit.All cycles are circuits but all circuits are not cycles. A graph is said to be an Euiler graph if and only if every vertex is of even degree.

                                                                   EULER WALK
s

                               It is a walk in a graph were all the edges of the graph are used once and only once.A graph is said to have an Euler path if and only if it has exactly 2 vertices of odd degree.
                               A graph is said to have an euler path if and only if it has got exactly 2 vertices of odd degree.


NOTE      Who is Euler?

Leonhard Euler(born, local  15 April 1707 – 18 September 1783) was a pioneering Swissmathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion of a mathematical function. He is also renowned for his work inmechanics, fluid dynamics, optics, and astronomy. Euler spent most of his adult life in St. Petersburg, Russia, and in Berlin, Prussia. He is considered to be the pre-eminent mathematician of the 18th century, and one of the greatest mathematicians ever. He is also one of the most prolific mathematicians ever; his collected works fill 60–80 quarto volumes.A statement attributed to Pierre-Simon Laplace expresses Euler's influence on mathematics: "Read Euler, read Euler, he is the master of us all."

   

degree

                                                               DEGREE OF A GRAPH

                       Number of edges incident with a graph is called degree of a graph.

                                In this graph every vertex is labelled by its degree.An isolated vertex is having degree 0.

                                If the degree of every vertex is same that graph is called regular graph.eg.Kregular graph,Pregular graph.
This is a regular graph because each and every vertex is having degree 3.
                                                            Cycles and complete graphs are always regular graphs.

                                                           HANDSHAKING THEOREM


                                                             Sum of the degrees of all the vertices of a graph is twice the number of edges.This theorem is known as handshaking theorem.
                                                             In the example the sum of edges is 5 and the sum of degrees of the edges is 10.so sum of the degrees of all the vertices of this graph is twice the number of edges.

                                                                DEGREE SEQUENCE

                                                              It is a sequence of non-negative integers which would be the of vertices of some graph.



                                                                     GRAPH INVARIANTS

1. Number of vertices
2. Number of edges.
3. Degree sequence
4. Number of cycles
5.  Number of paths

                                                               COMPLEMENT OF A GRAPH

The complement of a graph with vertex set V denoted by G' is another graph with same vertex set V with the condition that 2 vertices are adjacent in G if and only if they are not adjacent  in G'

                                                The combination of a graph and its complement is a complete graph.