GRAPH THEORY

Unit-I

What is a Graphs, application of Graphs, finite & infinite Graphs, incidence and degree, isolated vertex, pendant vertex & null Graphs, isomorphism , subgraphs, walks, paths and circuits connected graphs , connected graphs, disconnected Graphs  Components,Euler graphs,Operations  on graphs , Hamiltonian paths and circuits , The traveling salesman problems.  

Unit-II

Trees , properties of trees, Pendant vertices , Distance and center in a tree , Rooted and binary trees , Spanning trees , Fundamentals circuits , finding all Spanning trees in a graph, Cut sets, Connectivity and separability, Network flows , 1-isomorphism, 1-isomorphism.  

Unit-III

Combinatorial  Vs geometric graphs, Planar graphs, Kuratowski ‘s two graphs , Different representations of a planner graph, sets with one operation, sets with two operation, Modular arithmetic & Galois fields, Vectors & vector spaces , Vector spaces associated with a graph .

Unit-IV

Incidence matrix , sub matrices of A(G) , circuit matrix, fundamental circuit matrix and rank of B, an application to switching  switching network, cut-set matrix , path matrix, adjacency matrix, directed graph, Types of digraphs , digraphs and binary relations ,  directed paths and connectedness , Euler digraphs , Trees with directed .  

Unit-V

Fundamental circuits in digraphs, matrix  associated of a digraph , Paired comparisons  and tournaments , Enumeration of graph : Types of enumeration, Counting labeled trees , counting unlabelled trees , Polya’s counting theorem , Some basic algorithms : Algorithms for connectedness    and components. Algorithms  for finding spanning tree , Algorithms to find fundamental circuits , Shortest path algorithms.

Books

•   Graph theory with application to Engineering and Computer Science by N.Deo (Prentice hall India)

•  Graph theory by Frank Harary ( Narosa publishing house)