M Tech (Computer Science and Applications):Graph Theory and ApplicationsThapar University
Price on request
Frequent Asked Questions
Admission to M. Tech. (Computer Science and Applications) will be open to a candidate who obtains at least 50% marks in aggregate in the qualifying examination from a recognized university.
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
Object Oriented Analysis and Design
Logic and its applications
Computer Graphics and Multimedia Technologies
Web Technologies and E-Governance
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++.