Graph Theory for Undergraduates
The importance of graph theory can never be exaggerated considering the wide range of its applications, from social sciences to electrical engineering and computer science to management. The rigorous foundation of the subject is thus desirable. The objective of the course is, in addition to logical foundations, theoretical developments and development of the basic skills to tackle problems in Graph theory. It also aimed at understanding how various problems arising from real life or sciences as well as recreational puzzles can be converted to graph theoretic problems like shortest paths, network flows, chromatic numbers, connectivity etc.
What you’ll learn
- A depth knowledge of graph theory.
- An exposure to graph algorithms.
- Analytical thinking.
- Different approaches for addressing theoretical problems in mathematics.
Course Content
- Introduction to Graphs –> 5 lectures • 1hr 15min.
- Connected Graphs and Graph Isomorphism –> 4 lectures • 1hr 8min.
- Trees and Forests –> 3 lectures • 1hr.
- Spanning Trees –> 4 lectures • 1hr 5min.
- Eulerian and Hamiltonian Graphs –> 5 lectures • 1hr 22min.
- Graph Algorithms –> 2 lectures • 22min.
- Connectivity and Flow –> 8 lectures • 1hr 48min.
- Planar Graphs –> 4 lectures • 1hr 1min.
Requirements
The importance of graph theory can never be exaggerated considering the wide range of its applications, from social sciences to electrical engineering and computer science to management. The rigorous foundation of the subject is thus desirable. The objective of the course is, in addition to logical foundations, theoretical developments and development of the basic skills to tackle problems in Graph theory. It also aimed at understanding how various problems arising from real life or sciences as well as recreational puzzles can be converted to graph theoretic problems like shortest paths, network flows, chromatic numbers, connectivity etc.
This course begins with the basics of Graphs, i.e., it starts with the Simple Graphs and types of Graphs. Then it discusses the Isomorphism in Graphs along with the Euler & Hamiltonian Graphs. After that it talks about Trees and Spanning Trees, Connectivity, Cut Set and Shortest Path, Matrix representation of Graphs, and Maximal Flow in a Network. At the end, it discusses Graph Connectivity, Graph Colouring, Independence number and Chromatic Number.
The course will be taught by Krishnendra Shekhawat, Associate Professor at Department of Mathematics BITS Pilani. He has taught this course several times having a class strength of around 100 students. In total, there would be 10 chapters and there will be a assignment sheet for each Chapter. Each lecture would cover a lot of examples and exercises and main emphasis would be to develop analytical thinking ability to approach graph theoretical problems.