BAMU · Final Year B.E. Artificial Intelligence and Machine Learning · CBCGS
Graph Theory
AIM491 · Elective II · Semester VIII · 4 credits · CT 20 + theory 80
One of the Elective II options.
Unit 1: Fundamentals of Graph Theory
10 hoursDefinitions, subgraphs and isomorphic graphs; matrix representations; vertex degree; directed walks, paths and cycles; special graphs and complements; union, sum, Cartesian product and composition of graphs.
Examined in the 80-mark end-semester paper
- Graphs, subgraphs and degree
- Matrix representations of graphs
- Graph isomorphism and planar graphs
- Graph operations: union, sum and products
Unit 2: Eulerian and Hamiltonian Graphs; Graphic Sequences
10 hoursEulerian and Hamiltonian digraphs and graphs; graphic sequences, the Havel–Hakimi criterion and realising a graphic sequence; a graph model of the LAN problem.
Examined in the 80-mark end-semester paper
- Euler and Hamiltonian paths
- Graphic sequences and the Havel–Hakimi criterion
Unit 3: Connectivity and Shortest Paths
10 hoursWalks, trails, paths and cycles; connectivity and distance; cut-vertices, cut-edges and blocks; weighted graphs; Dijkstra's and Floyd–Warshall shortest-path algorithms.
Examined in the 80-mark end-semester paper
- Connectivity, cut-vertices and blocks
- Shortest paths: Dijkstra and Floyd–Warshall
Unit 4: Trees and Spanning Trees
10 hoursCharacterising and counting trees; minimum spanning trees with Kruskal's and Prim's algorithms; bipartite, line and chordal graphs.
Examined in the 80-mark end-semester paper
- Trees and their properties
- Spanning trees and minimal spanning trees
- Special graphs and bipartite graphs
Unit 5: Eulerian and Hamiltonian Properties; the Postman Problem
10 hoursEulerian graphs and Fleury's algorithm; the Chinese postman problem; Hamiltonian graphs and conditions for Hamiltonicity.
Examined in the 80-mark end-semester paper
- Fleury's algorithm and the Chinese postman problem
- Conditions for Hamiltonian graphs
Unit 6: Colouring, Matching and Applications
10 hoursIndependent sets and coverings; matchings in bipartite graphs, Hall's theorem and perfect matchings; vertex colouring, cliques and chromatic number, greedy colouring and Brooks' theorem; edge colouring, Vizing's theorem and scheduling.
Examined in the 80-mark end-semester paper
- Graph colouring and matching
- Hall's theorem and perfect matchings
- Chromatic number and Brooks' theorem
- Edge colouring and Vizing's theorem
Unit contents are summarised from the official BAMU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Marathwada University (BAMU).