M Tech (Computer Science and Applications):Graph Theory and Applications

Semester I


Advanced Data Structures
Data Communication and Computer Networks
Computer Organization and Operating Systems
Computational Algorithms in Optimization
Statistical Methods and Algorithms
Database Management and Administration


Semester II

Object Oriented Analysis and Design
Software Engineering
Logic and its applications
Computer Graphics and Multimedia Technologies
Web Technologies and E-Governance


Semester III

Seminar
Thesis (starts)


Semester IV

Thesis (contd.)


Graph Theory and Applications

Introduction: Graphs, Sub-graphs, Regular graph, Adjacency and incidence matrices, Finite and infinite graph, Incidence and degree, Isolated vertex, Pendent vertex and null graph, Turan’s theorem.
Paths and Circuits: Isomorphism, Walk, Cycle, Paths and circuits, Simple and proper circuit, Connected and disconnected graph, Euler graphs, Operations on graphs, Hamiltonian paths and circuits, Bipartite graph, Berge theorem, Hall’s theorem, Edge connectivity, Blocks, Menger’s theorem.
Trees and Fundamental Circuits: Trees, Properties of tree, Pendant vertices in a tree, Distance and centers in a tree, Spanning tree, Cayley’s Formula, Minimal spanning tree, Prim and Kruskal’s algorithm, Matrix Tree theorem, Dijkstra's Shortest Path Algorithm, Floyd-Warshall algorithm, Huffman's Coding Algorithm, Depth-first and breath first algorithm.
Cuts sets and cut-vertices: Cut sets, Properties of cutset, All cut sets in a graph, 1-isomorphism, 2-isomorphism.
Planar graph and dual graphs: Planar graphs, Homeomorphic graph, Kuratowski’s Two Graphs, Different representation of a planar graph, Tutte’s f-factor theorem, Detection of planarity, Geometric dual, Combinatorial dual.
Coloring, Covering and Partitioning: Chromatic number, Chromatic Partitioning, Chromatic Polynomial, Covering, Four colour conjucture, Five-colour theorem, Dirac Theorem, Brooks theorem, Vizing theroem.
Directed Graphs: Directed graph, Diagraph and binary relations, Directed Paths, Euler diagraphs, Acyclic digraphs,Topological sorting, Warshall’s algorithm, Bellman-Ford algorithm, Ramsey theorems.
Application of Graphs: Study of Konigsberg bridge problem, Travelling-salesman problem, Utilities problem, Electrical network problem, Seating problem, Use of graph in sequential switching networks, Graphs in coding theory, Graphs in computer programming, Flowgraph notation , Test case generation using graphs, Job sequencing problem, Graph coloring in scheduling of examinations.
Laboratory work: The laboratory work shall be based upon the implementation of graph theory algorithms like paths, circuits, minimal spanning tree, Huffman’s coding, coloring of graphs, Warshall’s and Bellman-Ford algorithm for directed graphs through a suitable language such as C/C++.