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.<\/p>\n
The detailed syllabus for Graph Theory M.Tech 2017-2018 (R17) first year first sem is as follows.<\/p>\n
M.Tech. I Year I Sem.<\/p>\n
Unit – I: Introduction-<\/strong>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.<\/p>\n Unit – II: : Connected graphs and shortest paths –<\/strong> Walks, trails, paths, cycles, Connected graphs, Distance, Cut-vertices and cut-edges, Blocks, Connectivity, Weighted graphs and shortest paths, Weighted graphs, Dijkstra\u2019s shortest path algorithm, Floyd-Warshall shortest path algorithm.<\/p>\n Unit III: Trees-<\/strong> Definitions and characterizations, Number of trees, Cayley\u2019s formula, Kircho-matrix-tree theorem, Minimum spanning trees, Kruskal\u2019s algorithm, Prim\u2019s algorithm, Special classes of graphs, Bipartite Graphs, Line Graphs, Chordal Graphs, Eulerian Graphs, Fleury\u2019s algorithm, Chinese Postman problem, Hamilton Graphs, Introduction, Necessary conditions and sufficient conditions.<\/p>\n Unit IV: Independent sets coverings and matchings \u2013<\/strong> Introduction, Independent sets and coverings: basic equations, Matchings in bipartite graphs, Hall\u2019s Theorem, K\u00a8onig\u2019s Theorem, Perfect matchings in graphs, Greedy and approximation algorithms.<\/p>\n Unit – V: Vertex Colorings-<\/strong> Basic definitions, Cliques and chromatic number, Mycielski\u2019s 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.<\/p>\n TEXTBOOKS:<\/strong><\/p>\n REFERENCES:<\/strong><\/p>\n\n
\nhttps:\/\/www.iro.umontreal.ca\/~hahn\/IFT3545\/GTWA.pdf<\/li>\n<\/ul>\n