# MSc (Mathematics and Computing) Programme:Graph Theory and Applications

Thapar UniversityPrice on request

Price on request

Free

£ 359 - (Rs 30,933) £ 341 - (Rs 29,382)

VAT incl.

£ 295 - (Rs 25,418)

+ VAT

## Important information

- Master
- Patiala

Starts | Location |
---|---|

On request |
PatialaThapar University P.O Box 32, 147004, Punjab, India See map |

## Course programme

Semester I

Real Analysis – I

Linear Algebra

Complex Analysis

Fundamentals of Computer Science and C Programming

Discrete Mathematical Structure

Differential Equations

Semester II

Real Analysis –II

Advanced Abstract Algebra

Computer Oriented Numerical Methods

Data Structures

Data Based Management Systems

Operating Systems

Semester III

Topology

Computer Based Optimization Techniques

Computer Networks

Mechanics

Seminar

Semester IV

Functional Analysis

Dissertation

Graph Theory and Applications

Graphs and Subgraphs: Graph and Simple Graphs, Graph Isomorphism, Incidence and adjacency matrix, subgraphs, Vertex, Degrees, Paths and connection, Cycles, directed graphs, directed paths, directed cycles, The shortest path problems, Sperner’s lemma, A job sequencing problems, Designing an efficient computer Drum, Making a Road system One-way, Ranking the participants in a tournament

Trees and Networks: Trees, Cut edges and bonds, Cut vertices, Cayley Formula, Flows, Cuts, The max-Flow Min- Cut theorem, Connectivity, Blocks. The Connector problem, Menger’s theorem, Feasible Flows, Construction of Reliable Communication Networks

Planar Graphs: Plane and planar Graphs, Dual graphs, Euler’s formula, Bridges, Kuratowski’s theorem, The five - colour theorem and the four-colour conjecture, non- Hamiltonian planar Graphs. A planarity Algorithm.

Euler's Tours and Hamilton's Cycls: Euler’s tours, Hamilton cycles, The Chinese postman problem, the traveling salesman problem, Industrial drilling tool problem.

Matching: Matching in Bipartite graphs, perfect matching. The personnel Assignment problems, The optimal assignment problems.

Colorings: Edge chromatic number, Vizing’s theorem, Brook’s theorem, Hajos’s conjecture, Chromatic polynomials, Girith and Chromatic number. The time tabling problems, Storage problem.

Laboratory work: The laboratory work shall be based upon the implementation of graph theory algorithms like paths, circuits, shortest path problems, tree, Euler’s tour,Hamilton cycles, Chinese postman problem, the traveling salesman problem, Matching in Bipartite graphs, coloring of graphs through a suitable language such as C/C++.