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).
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 hoursIntroduction 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 hoursMatchings 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 hoursConnectivity 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 hoursPlanar 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)
| Attendance | 5 |
| Project | 30 |
| 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.