X
X
X

X
Courses » Graph Theory

Graph Theory

ABOUT THE COURSE 
Graph theory began in 1736 when the Swiss mathematician Euler solved Konigsberg seven-bridge problem. It has been two hundred and eighty years till now. Graph theory is the core content of Discrete Mathematics, and Discrete Mathematics is the theoretical basis of computer science and network information science. This course introduces in an elementary way some basic knowledge and the primary methods in Graph Theory.

INTENDED AUDIENCE

B.Sc, M.Sc, B.Tech, M.Tech

PRE-REQUISITES: 
None

CORE/ELECTIVE: 
Elective

UG/PG:
 Both

INDUSTRIES THAT WILL RECOGNIZE THIS COURSE
It will be recognized by several industries & academic institutes

3484 students have enrolled already!!

COURSE INSTRUCTOR 

Soumen Maity is an Associate Professor of Mathematics at Indian Institute of ScienceEducation and Research (IISER) Pune. He received a PhD from the Theoretical Statistics & Mathematics Unit at Indian Statistical Institute (ISI) Kolkata, India in 2002. He has postdoctoral experience from Lund University, Sweden; Indian Institute of Management (IIM) Kolkata, India; and University of Ottawa,Canada. Prior to joining IISER Pune in 2009, he worked as Assistant Professor at IIT Guwahati and IITKharagpur.

 COURSE LAYOUT
 Week 1: Paths, Cycles, Trails, Eulerian Graphs, Hamiltonian Graphs
 Week 2: Bipartite graphs, Trees, Minimum Spanning Tree Algorithms
 Week 3: Matching and covers
 Week 4: Maximum matching in Bipartite Graphs
 Week 5: Cuts and Connectivity
 Week 6: 2-connected graphs
 Week 7: Network flow problems, Ford-Fulkerson algorithm
 Week 8
: Planar graphs; Coloring of graphs


 SUGGESTED READING

 1. Introduction to Graph Theory: D.B. West (2001) Prentice Hall. 2. Graph Theory: F.Harary (1969) Addison-Wesley. 3. Graph Theory: R. Diestel  (2006) Springer .and network information science. This course introduces in an elementary way some basic knowledge and the primary methods  in Graph Theory


CERTIFICATION EXAM 

  • The exam is optional for a fee. Exams will be on  31 March 2019.
  • Time: Shift 1: 9am-12 noon; Shift 2: 2pm-5pm
  • Any one shift can be chosen to write the exam for a course.
  • Registration URL: Announcements will be made when the registration form is open for registrations.
  • The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the   exam registration form is published

  CERTIFICATE
  • Final score will be calculated as : 25% assignment score + 75% final exam score
  • 25% assignment score is calculated as 25% of average of best 6 out of 8 assignments.
  • E-Certificate will be given to those who register and write the exam and score greater than or equal to 40% final score.  Certificate will have your name, photograph and the score in the final exam with the breakup. It will have the logos of NPTEL  and IIT Madras. It will be e-verifiable at nptel.ac.in/noc