Discrete Mathematics and Graph Theory

a
Course
Postgraduate
Semester
Electives
Subject Code
MA869
Subject Title
Discrete Mathematics and Graph Theory

Syllabus

Basic counting principle: Pigeonhole principle, inclusion - exclusion principle, recurrence relations, generating functions. Fundamentals of logic, set theory, language, and finite state machines.

Undirected and direct graphs, modelling with graphs, trial and cycle- Eulerian trial and Hamilton cycle, connectivity and trees. Graph algorithms: BFS, DFS, shortest path, optimal spanning trees, matching, job assignment problem, optimal transportation through flows in networks

 

Text Books

Same as Reference

References

  1. Liu, C. L., Elements of Discrete Mathematics, 2nd Ed., Tata McGraw-Hill (2000).
  2. Grivaldi, R. P. and Ramana, B. V., Discrete and Combinatorial mathematics, Pearson (2008).
  3. Graham, R. L., Knuth, D. E., and Patashnik, O., Concrete Mathematics, 2nd Ed., Addison- Wesley (1994).
  4. Rosen, K. H., Discrete Mathematics and its Applications, 6th Ed., Tata McGraw-Hill (2007).

Course Outcomes (COs):
CO1: Familiarize with counting principles

CO2: Learn concepts like, pegion hole principle, exclusion inclusion principle, recursive equations

CO3: Apply these concepts to specific problems

CO4: Familiarize with various of types graphical models, concepts of walk, trail, path, cycles. Then to learn, connected graph, tree, spanning tree, Eulerian trail, Hamiltonian path.

CO5: Learn various algorithms related to spanning tree, shortest path, Halls marriage theorem. Also, learn about their applications for optimization problems in real-life.