BAMU Final Year AI & ML syllabus

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.

All notes for this subject
  1. Unit 1: Fundamentals of Graph Theory

    10 hours

    Definitions, 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
  2. Unit 2: Eulerian and Hamiltonian Graphs; Graphic Sequences

    10 hours

    Eulerian 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
  3. Unit 3: Connectivity and Shortest Paths

    10 hours

    Walks, 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
  4. Unit 4: Trees and Spanning Trees

    10 hours

    Characterising 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

  5. Unit 5: Eulerian and Hamiltonian Properties; the Postman Problem

    10 hours

    Eulerian 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
  6. Unit 6: Colouring, Matching and Applications

    10 hours

    Independent 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).