Chat with us on WhatsAppCall Learnizo

KTU 2024 Scheme · Semester 5 · Program Core — Artificial Intelligence

Advanced Graph Algorithm (PBCAT504) Syllabus

Official KTU 2024 Scheme syllabus for Advanced Graph Algorithm, Semester 5, Program Core — Artificial Intelligence (Artificial Intelligence).

This page compiles APJ Abdul Kalam Technological University's officially published 2024 Scheme syllabus for Artificial Intelligence, Semester 5, sourced directly from KTU's official website (ktu.edu.in). Learnizo is an independent online tuition platform and is not affiliated with, endorsed by, or officially connected to APJKTU. The university may revise syllabus content after this page was last updated — always cross-check with the official KTU source for the current, authoritative version.

Course Code

PBCAT504

Credits

4

Teaching Hours

3:0:0:1 (L:T:P:R)

CIE Marks

60

ESE Marks

40

Exam Duration

2 Hrs 30 Min

Prerequisites

GAMAT401

Semester

Semester 5

Course Objective

To provide a comprehensive understanding of the fundamental concepts of graphs and trees, to learn matching and covering algorithms, connectivity and paths, and to equip the learner to apply vertex colouring, planar graphs, line graphs and edge colouring effectively.

Module-wise Syllabus

Module 1

12 contact hours

Introduction to graphs and its applications, basics of paths, cycles and trails, connection, bipartite graphs, Eulerian circuits, vertex degrees and counting, degree-sum formula, the Chinese Postman Problem and graphic sequences. Trees and distance — properties of trees, spanning trees and enumeration, matrix-tree computation, Cayley's formula, Prufer code.

Module 2

12 contact hours

Matchings and covers — Hall's condition, Min-Max theorem, independent sets, covers and maximum bipartite matching, augmenting path algorithm, weighted bipartite matching, Hungarian algorithm. Stable matchings and faster bipartite matching, factors and perfect matching in general graphs, matching in general graphs: Edmonds' Blossom algorithm.

Module 3

10 contact hours

Connectivity and paths — cuts and connectivity, k-connected graphs, network flow Ford-Fulkerson labeling algorithm, Max-Flow Min-Cut theorem, Menger's proof using the Max-Flow Min-Cut theorem. Vertex coloring and upper bounds, Brooks' theorem and color-critical graphs, counting proper colorings.

Module 4

10 contact hours

Planar graphs — characterization of planar graphs, Kuratowski's theorem, Wagner's theorem. Line graphs and edge-coloring, Hamiltonian graphs, Traveling Salesman Problem and NP-completeness, dominating sets. Suggested project topics: applications of advanced graph theory in routing, social network analysis, disease spreading models.

Course Outcomes

  • CO1Explain fundamental graph concepts and algorithms to analyse and solve problems involving paths, cycles, trees and network optimization.
  • CO2Illustrate matching and covering problems in graphs using algorithms and theorems, including Hall's condition, the Min-Max theorem and the Hungarian algorithm.
  • CO3Apply connectivity and paths including the network flow Ford-Fulkerson labeling algorithm, Max-Flow Min-Cut theorem and Menger's proof.
  • CO4Illustrate vertex coloring and upper bounds, Brooks' theorem and color-critical graphs, and counting proper colorings.
  • CO5Apply concepts of planar graphs, including Kuratowski's and Wagner's theorems, to analyse graph planarity and edge-coloring, while solving problems related to Hamiltonian graphs, the Traveling Salesman Problem and dominating sets.

Assessment Pattern (CIE: 60 marks, ESE: 40 marks)

Continuous Internal Evaluation (CIE)

Attendance5
Project30
Internal Examination 1 (Written)12.5
Internal Examination 2 (Written)12.5

End Semester Examination (ESE)

Total 40 marks, 2 Hrs 30 Min. See the official KTU syllabus document for the exact Part A / Part B question pattern for this course.

Textbooks & Reference Books

Textbooks

  • Introduction to Graph Theory — D. B. West (Pearson, 2nd edition, 2001)
  • Introduction to Graph Theory — Robin J. Wilson (Longman Group Ltd, 5th edition, 2015)
  • Graph Theory with Applications — J. A. Bondy, U. S. R. Murty (Elsevier Science Publishing Co., Inc, 1st edition, 1982)

Reference Books

  • Graph Theory — R. Diestel (Springer, 4th edition, 2010)
  • Graph Theory and its Applications — Jay Yellen, Jonathan L. Gross, et al. (CRC Press, 3rd edition, 2019)
  • Modern Graph Theory — Bela Bollobas (Springer, 1st edition, 1998)
  • Network Flows: Theory, Algorithms, and Applications — Ravindra Ahuja, Thomas Magnanti, et al. (Prentice-Hall, 1st edition, 1993)

Frequently Asked Questions

How many credits is KTU Advanced Graph Algorithm (PBCAT504)?

4 credits, with 3:0:0:1 (L:T:P:R) teaching hours per week, under the KTU 2024 Scheme.

How many modules are in the PBCAT504 syllabus?

4 modules, 44 total contact hours.

What is the CIE and ESE mark split for this course?

CIE (Continuous Internal Evaluation): 60 marks. ESE (End Semester Examination): 40 marks, 2 Hrs 30 Min. Total: 100 marks.

What are the recommended textbooks for PBCAT504?

Introduction to Graph Theory (D. B. West); Introduction to Graph Theory (Robin J. Wilson); Graph Theory with Applications (J. A. Bondy, U. S. R. Murty).

Is this syllabus specific to one branch, or common to others too?

This Semester 5 course is listed under Program Core — Artificial Intelligence at KTU under the 2024 Scheme — check the course header above for which branches it's common to.

Need help with KTU Advanced Graph Algorithm?

Learnizo offers live, 1-on-1 online tuition for KTU AI subjects — matched to your exact module and semester.