Graph Theory BCS405B

Module 1 Overview

Introduction to Graphs: Introduction- Basic definition - Application of graphs - finite, infinite and bipartite graphs - Incidence and Degree - Isolated vertex, pendant vertex and Null graph. Paths and circuits - Isomorphism, sub-graphs, walks, paths and circuits, connected graphs, disconnected graphs and components.

(RBT Levels: L1, L2 and L3)

Teaching-Learning Process: Chalk and talk method / PowerPoint Presentation

Module 2 Overview

Eulerian and Hamiltonian graphs: Euler graphs, Operations on graphs, Hamiltonian paths and circuits, Travelling salesman problem. Directed graphs - types of digraphs, Digraphs and binary relation.

(RBT Levels: L1, L2 and L3)

Teaching-Learning Process: Chalk and talk method / PowerPoint Presentation

Module 3 Overview

Trees: properties, pendant vertex, Distance and centres in a tree - Rooted and binary trees, counting trees, spanning trees.

Connectivity Graphs: Vertex Connectivity, Edge Connectivity, Cut set and Cut Vertices, Fundamental circuits.

(RBT Levels: L1, L2 and L3)

Teaching-Learning Process: Chalk and talk method / PowerPoint Presentation

Module 4 Overview

Planar Graphs: Planar graphs, Kuratowski's theorem (proof not required), Different representations of planar graphs, Euler's theorem, Geometric dual.

Graph Representations: Matrix representation of graphs-Adjacency matrix, Incidence Matrix, Circuit Matrix, Path Matrix.

(RBT Levels: L1, L2 and L3)

Teaching-Learning Process: Chalk and talk method / PowerPoint Presentation

Module 5 Overview

Graph Colouring: Colouring- Chromatic number, Chromatic polynomial, Matchings, Coverings, Four colour problem and Five colour problem. Greedy colouring algorithm.

(RBT Levels: L1, L2 and L3)

Teaching-Learning Process: Chalk and talk method / PowerPoint Presentation