Graph Theory
Teacher
Dr. Bhairaba Kumar Majhi
Category
Core Courses
Course Attendees
Still no participant
Course Reviews
Still no reviews
Course Name : Graph theory
Code(Credit) : CUTM-1531(3-1-0)
Course Objectives
-
To introduce the students to graphs, their properties and their applications as models of networks.
-
To represent almost any physical situation involving discrete objects and a relationship among them.
-
To introduce the students to generating functions and their applications.
Course Outcomes
| COs | Course outcomes | Mapping Cos with POs (High-3, Medium-2, Low-1) |
| CO1 | Know the basic definitions and concepts of graph theory and Write in a coherent and technically accurate manner.
|
PO1(3), PO2(2) |
| CO2 | Learn about how to develop graph theoretical algorithm and Know about many different coloring problems for graphs.
|
PO2(2), PO9(2) |
Course Syllabus
Module-I
Introduction to Graphs and Definition of graphs;Basic terminologies and types of graphs;Degree of a vertex,Isolated and Pendent vertices;Sub graphs and graph Isomorphism.
Practice 1: Determine if two graphs are isomorphic and identify the isomorphism
Module-II
Directed Graphs and Types of Digraphs;Out-degree, In-degree, Connectivity and Orientation;Digraphs and Binary relations , Directed paths and contentedness;Euler Digraphs, De-Brujin sequences;Tournaments.
Practice 2: Ways to Represent Graphs using Python
Module-III
Basic concepts of Planar Graphs; Kuratowski’s Two graphs ;Representation of Planar Graphs ; Detection of planarity ;Euler’s formula for planar graphs;
Practice 3: A look in to Planar Graphs and Euler's Relationship
Module-IV
Distance, cut-vertices, cut-edges, blocks;weighted graphs, connectivity;Dijkstra’s shortest path algorithm;Floyd-War shall Shortest path algorithm;
Module-V
Proper Coloring of graphs;Chromatic numbers of a graph;Chromatic polynomial;Chromatic Partitioning;Four Colour theorem.
Practice 4: Finding Chromatic number using python-networks.
Module-VI
Definition and properties of trees;Rooted and Binary trees; Counting trees, Spanning trees;
Practice 5: Applications of graphs with Euler and Hamiltonian path and circuits(Chinese postman Problem)
Module-VII
Minimum spanning trees;Fundamental Circuit;Cut set and Separability;
Practice 6: Application of Minimum spanning tree in a Net work model
Text Book:
Deo, N., “Graph Theory with Applications to Engineering and Computer Science”, Prentice Hall India 2004
Chapters: 1(1.1,1.2,1.3,1.4,1.5) ,2 (2.1,2.2,2.4,2.4,2.6,2.9), 3(3.1,3.2,3.5,3.7,3.8,3.9,3.10), 4(4.1,4.4,4.5), 5(5.2,5.3,5.4,5.5), 7(7.1,7.2), 8(8.1,8.2,8.3,8.6),9(9.1,9.2,9.3,9.4,9.5)
Reference Books:
West, D. B., "Introduction to Graph Theory ", Prentice Hall India (2nd Edition 2009)
Aldous, J. M., Wilson, R. J. and Best S., “Graphs and Applications: An Introductory Approach”, Springer2003.
Deistel, R., “Graph Theory”, Springer (4th Edition) 2010.
Chartrand, G. and Zhang, P., "Introduction to Graph Theory", Tata McGraw Hill2007.
Bondy, J. A. and Murty, U. S. R., “Graph Theory”, Springer 2011
Session Plan
Session 1:
Introduction to Graphs and Definition of graphs.
Session 2:
Session 3:
Degree of a vertex,Isolated and Pendent vertices
Session (5 & 6):
practice 1:
An Introduction to Graph Neural Networks: Models and Applications
Session 8:
Out-degree, In-degree, Connectivity and Orientation
Session (12 & 13):
practice 2:
Session (20 & 21):
practice 3:
A look in to Planar Graphs and Euler's Relationship
Session 22:
Distance, cut-vertices, cut-edges, blocks
Session (26 & 27):
practice 4:
Chromatic number using python-networkx|Graph Theory|Chromatic number of a graph
Session 32:
Session (33 & 34):
practice 5:
Applications of graphs with Euler and Hamiltonian path and circuits(Chinese postman Problem)
Session 41 &42:
practice 6:
Application of Minimum spanning tree in a Net work model
https://www.youtube.com/watch?v=b1btzVsKp8E
Counting Spanning Trees using python-networkx| Graph Theory|Kirchoff's Matrix Tree Theorem
practice 7:
Binary Tree , basic introduction and Code implementation to create tree in Python
practice 8:
Binary Trees in Python: Level-order Traversal
Case Studies
Case Studies
Our Main Teachers
My Self Dr.Bhairaba Kumar Majhi,M,Sc,B.Ed,M.Tech(CSE),Ph.D(Mathematics ) ,Asst.Professor And HOD Department of Mathematics School Of Applied Sciences,Presently working at CUTM,Bolangir Campus.I have 16 Years of Experience in Teaching at Different Levels Of UG,PG & Engineering Mathematics.