Graph Theory Detailed Syllabus for Computer Science and Engineering M.Tech first year first sem is covered here. This gives the details about credits, number of hours and other details along with reference books for the course.
The detailed syllabus for Graph Theory M.Tech 2017-2018 (R17) first year first sem is as follows.
M.Tech. I Year I Sem.
Unit – I: Introduction-Discovery of graphs, Definitions, Subgraphs, Isomorphic graphs, Matrix representations of graphs, Degree of a vertex, Directed walks, paths and cycles, Connectivity in digraphs, Eulerian and Hamilton digraphs, Eulerian digraphs, Hamilton digraphs, Special graphs, Complements, Larger graphs from smaller graphs, Union, Sum, Cartesian Product, Composition, Graphic sequences, Graph theoretic model of the LAN problem, Havel-Hakimi criterion, Realization of a graphic sequence.
Unit – II: : Connected graphs and shortest paths – Walks, trails, paths, cycles, Connected graphs, Distance, Cut-vertices and cut-edges, Blocks, Connectivity, Weighted graphs and shortest paths, Weighted graphs, Dijkstra’s shortest path algorithm, Floyd-Warshall shortest path algorithm.
Unit III: Trees- Definitions and characterizations, Number of trees, Cayley’s formula, Kircho-matrix-tree theorem, Minimum spanning trees, Kruskal’s algorithm, Prim’s algorithm, Special classes of graphs, Bipartite Graphs, Line Graphs, Chordal Graphs, Eulerian Graphs, Fleury’s algorithm, Chinese Postman problem, Hamilton Graphs, Introduction, Necessary conditions and sufficient conditions.
Unit IV: Independent sets coverings and matchings – Introduction, Independent sets and coverings: basic equations, Matchings in bipartite graphs, Hall’s Theorem, K¨onig’s Theorem, Perfect matchings in graphs, Greedy and approximation algorithms.
Unit – V: Vertex Colorings- Basic definitions, Cliques and chromatic number, Mycielski’s theorem, Greedy coloring algorithm, Coloring of chordal graphs, Brooks theorem, Edge Colorings, Introduction and Basics, Gupta-Vizing theorem, Class-1 and Class-2 graphs, Edge-coloring of bipartite graphs, Class-2 graphs, Hajos union and Class-2 graphs, A scheduling problem and equitable edge-coloring.
TEXTBOOKS:
- J. A. Bondy and U. S. R. Murty. Graph Theory, volume 244 of Graduate Texts in Mathematics. Springer, 1st edition, 2008.
- J. A. Bondy and U. S. R. Murty. Graph Theory with Applications
https://www.iro.umontreal.ca/~hahn/IFT3545/GTWA.pdf
REFERENCES:
- Lecture Videos: http://nptel.ac.in/courses/111106050/13
For all other M.Tech 1st Year 1st Sem syllabus go to JNTUH M.Tech Computer Science and Engineering 1st Year 1st Sem Course Structure for (R17) Batch.
All details and yearly new syllabus will be updated here time to time. Subscribe, like us on facebook and follow us on google plus for all updates.
Do share with friends and in case of questions please feel free drop a comment.