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

Thapar University
In Patiala

Price on request
You can also call the Study Centre
17523... More

## Important information

 Typology Master Start Patiala
• Master
• Patiala
Description

Venues

Where and when

Starts Location
On request
Patiala
Thapar University P.O Box 32, 147004, Punjab, India
See map
 Starts On request Location PatialaThapar University P.O Box 32, 147004, Punjab, India See map

## Frequent Asked Questions

· Requirements

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.

## Course programme

Semester I

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++.

Students that were interested in this course also looked at...
See all