{"id":9613,"date":"2018-08-31T18:34:00","date_gmt":"2018-08-31T18:34:00","guid":{"rendered":"https:\/\/www.inspirenignite.com\/jntuh\/?p=9613"},"modified":"2026-05-24T10:53:30","modified_gmt":"2026-05-24T05:23:30","slug":"jntuh-m-tech-2017-2018-r17-detailed-syllabus-graph-theory","status":"publish","type":"post","link":"https:\/\/www.inspirenignite.com\/jntuh\/jntuh-m-tech-2017-2018-r17-detailed-syllabus-graph-theory\/","title":{"rendered":"JNTUH M.Tech 2017-2018 (R17) Detailed Syllabus Graph Theory"},"content":{"rendered":"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.\r\n\r\nThe detailed syllabus for Graph Theory M.Tech 2017-2018 (R17) first year first sem is as follows.\r\n\r\nM.Tech. I Year I Sem.\r\n\r\n<strong>Unit &#8211; 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.\r\n\r\n<strong>Unit &#8211; II: : Connected graphs and shortest paths &#8211;<\/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.\r\n\r\n<strong>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.\r\n\r\n<strong>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.\r\n\r\n<strong>Unit &#8211; 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.\r\n\r\n<strong>TEXTBOOKS:<\/strong>\r\n<ul>\r\n \t<li>J. A. Bondy and U. S. R. Murty. Graph Theory, volume 244 of Graduate Texts in Mathematics. Springer, 1st edition, 2008.<\/li>\r\n \t<li>J. A. Bondy and U. S. R. Murty. Graph Theory with Applications\r\nhttps:\/\/www.iro.umontreal.ca\/~hahn\/IFT3545\/GTWA.pdf<\/li>\r\n<\/ul>\r\n<strong>REFERENCES:<\/strong>\r\n<ul>\r\n \t<li>Lecture Videos: http:\/\/nptel.ac.in\/courses\/111106050\/13<\/li>\r\n<\/ul>\r\nFor all other M.Tech 1st Year 1st Sem syllabus go to <a href=\"https:\/\/www.inspirenignite.com\/jntuh\/jntuh-first-year-first-sem-computer-science-and-engineering-for-m-tech-2017-2018-r17-batch\/\">JNTUH M.Tech Computer Science and Engineering 1st Year 1st Sem Course Structure for (R17) Batch.<\/a>\r\n\r\nAll 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.\r\n\r\nDo share with friends and in case of questions please feel free drop a comment.\n\n<h2>Download iStudy App (Android &amp; iOS)<\/h2>\n<div style=\"width: 100%;text-align: center;background: #f0f7ff;border: 1px solid #d9e8ff;border-radius: 10px;padding: 12px 10px;margin: 8px 0 12px 0\">\n<p style=\"margin: 0 0 8px 0\">Get instant JNTUH updates, timetables, results, and notices on mobile.<\/p>\n<div style=\"justify-content: center;align-items: flex-start;gap: 24px;flex-wrap: wrap\">\n<div style=\"flex-direction: column;align-items: center;gap: 2px\"><img decoding=\"async\" style=\"height: 54px;width: auto\" src=\"https:\/\/play.google.com\/intl\/en_us\/badges\/static\/images\/badges\/en_badge_web_generic.png\" alt=\"Get it on Google Play\" \/>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0<img decoding=\"async\" style=\"height: 80px;width: 80px\" src=\"https:\/\/api.qrserver.com\/v1\/create-qr-code\/?size=120x120&amp;data=https:\/\/play.google.com\/store\/apps\/details?id=ini.istudy\" alt=\"Android app QR code\" \/><\/div>\n<div>\u00a0<\/div>\n<div style=\"flex-direction: column;align-items: center;gap: 2px\"><a href=\"https:\/\/play.google.com\/store\/apps\/details?id=ini.istudy\" target=\"_blank\" rel=\"noopener\">Android App<\/a><\/div>\n<div>\u00a0<\/div>\n<div style=\"flex-direction: column;align-items: center;gap: 2px\"><img decoding=\"async\" style=\"height: 40px;width: auto\" src=\"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/3\/3c\/Download_on_the_App_Store_Badge.svg\" alt=\"Download on the App Store\" \/>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0<img decoding=\"async\" style=\"height: 80px;width: 80px\" src=\"https:\/\/api.qrserver.com\/v1\/create-qr-code\/?size=120x120&amp;data=https:\/\/apps.apple.com\/us\/app\/istudy-app-syllabus-papers\/id6478500231\" alt=\"iOS app QR code\" \/><\/div>\n<div>\u00a0<\/div>\n<div style=\"flex-direction: column;align-items: center;gap: 2px\"><a href=\"https:\/\/apps.apple.com\/us\/app\/istudy-app-syllabus-papers\/id6478500231\" target=\"_blank\" rel=\"noopener\">iOS App <\/a><\/div>\n<\/div>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 [&hellip;]<\/p>\n","protected":false},"author":2259,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_bbp_topic_count":0,"_bbp_reply_count":0,"_bbp_total_topic_count":0,"_bbp_total_reply_count":0,"_bbp_voice_count":0,"_bbp_anonymous_reply_count":0,"_bbp_topic_count_hidden":0,"_bbp_reply_count_hidden":0,"_bbp_forum_subforum_count":0,"footnotes":""},"categories":[73,62],"tags":[],"class_list":["post-9613","post","type-post","status-publish","format-standard","hentry","category-m-tech","category-syllabus"],"_links":{"self":[{"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/posts\/9613","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/users\/2259"}],"replies":[{"embeddable":true,"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/comments?post=9613"}],"version-history":[{"count":3,"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/posts\/9613\/revisions"}],"predecessor-version":[{"id":40453,"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/posts\/9613\/revisions\/40453"}],"wp:attachment":[{"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/media?parent=9613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/categories?post=9613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.inspirenignite.com\/jntuh\/wp-json\/wp\/v2\/tags?post=9613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}