B.Sc. (Data Science) Graph Theory Syllabus - Mumbai University
This is the FY BSc Data Science syllabus under NEP 2020, in force from the academic year 2024-25. The University still sets the earlier Choice Based papers alongside it for ATKT candidates, so check which scheme your exam form names before you revise.
Loading syllabus...
Syllabus for Graph Theory
Module I
- 1. GRAPHS AND DIGRAPHS: Introduction, Graph Isomorphism, Subgraphs, 1Degrees, Indegrees, and Outdegrees, Adjacency Matrices and Incidence Matrices, Degree Vectors of Simple Graphs 2. Connectivity: Paths. Circuits, and Cycles, Connected Graphs and Digraphs, Trees and Spanning Trees, Strong Orientations of Graphs 3. Eulerian and Hamiltonian Graphs: Eulerian Graphs and Digraphs, Hamiltonian Graphs and Digraphs, Tournaments. 4. Optimization Involving Trees: Minimum Weight Spanning Trees, Maximum Weight Branching’s, Minimum Weight arborescence’s, Matroids and the Greedy Algorithm 5. Shortest Path Problems: Two Shortest Path Algorithms, The Steiner Network Problem, Facility Location Problems
Module II
- 1. Flow and Connectivity and Combinatorics: Flows in Networks and Menger’s Theorem, More on Connectivity, Some Applications to Combinatorics 2. Matchings and Factors: More on Matchings, The Optimal Assignment Problem, The Traveling Salesperson Problem (TSP), Factors, Factorizations, and the Petersen Graph, 3. Graph Embeddings: Planar Graphs and Duality, Hamiltonian Plane Graphs, Maximum Flow in Planar Networks, Graphs on Surfaces (An Informal Treatment) Colourings of Graphs: Vertex Colouring of Graphs, Edge Colouring of Graphs, Colouring of Planar Graphs 10, 11 Reference Books 1. Schaum's Outline of Graph Theory: Including Hundreds of Solved Problems, by V. K. Balakrishnan, McGraw-Hill Education, 1997 2. A Textbook of Graph Theory, R. Balakrishnan, K. Ranganathan, Springer, 2 nd Edition, 2012 3. Introduction to Graph Theory, by Richard J. Trudeau, Dover, 1 st Edition, 2013 4. Introduction to Graph Theory, by Douglas Brent West, Prentice Hall, 1 st Edition, 2010 5. Graph Theory, by Frank Harary, Addison-Wesley, 1 st Edition, 2010 6. Basic Graph Theory, by Md. Saidur Rahman, Springer, 1 st Edition, 2017 12 Internal Continuous Semester End Examination: 60% Assessment: 40% 13 Continuous Evaluation Format of Question Paper: External through: Examination (30 Marks)– 1 hr duration Class test of 1 of 15 marks Class test of 2 of 15 marks Average of the two: 15 marks Quizzes/ Presentations/ Assignments: 5 marks Total: 20 marks 14 Format of Question Paper: (Semester End Examination : 30 Marks. Duration:1 hour) Q1: Attempt any two (out of four) from Module 1 (15 marks) Q2: Attempt any two (out of four) from Module 2 (15 marks)
Reproduced from the University of Mumbai syllabus for B.Sc. (Data Science) under NEP 2020, in force from the academic year 2024-25. Wording is as printed in that syllabus. Module numbering is as printed there too.
The complete syllabus
This subject is cut from the University circular for its year. Open a document here if you want the whole thing rather than a single subject.