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.

https://www.youtube.com/watch?v=ZHqQDA3be-k

Session 2:

Basic terminologies  of graph and types of graphs.

https://www.youtube.com/watch?v=MqKcu-FxAqU

 

Session 3:

Session 4:

Sub graphs and graph Isomorphism

https://www.youtube.com/watch?v=z-GfKbzvtBA

Session (5 & 6):

practice 1:

An Introduction to Graph Neural Networks: Models and Applications

https://www.youtube.com/watch?v=zCEYiCxrL_0

Session 7:

Directed Graphs and Types of Digraphs

https://www.youtube.com/watch?v=R3f04LRYf5w

Session 8:

Session 10:

Directed paths and connectedness,

https://www.youtube.com/watch?v=by1zmpTxXIk

Session 11:

Euler Digraphs, De-Brujin sequences,

https://www.youtube.com/watch?v=TNYZZKrjCSk

Session (12 & 13):

practice 2:

Ways to Represent GRAPHS using Python

https://www.youtube.com/watch?v=HDUzBEG1GlA

 

Session 15:

Basic concepts of Planar Graphs,

https://www.youtube.com/watch?v=UkjJE3bmPV0

Session 19:

Euler’s formula for planar graphs

https://www.youtube.com/watch?v=5ywif1Zpeo4&t=137s

Session (20 & 21):

practice 3:

A look in to Planar Graphs and Euler's Relationship

https://www.youtube.com/watch?v=x6zPviKyykM

Session 22:

Distance, cut-vertices, cut-edges, blocks

https://www.youtube.com/watch?v=pzHbR51_qOg&t=8s

Session 23:

weighted graphs, connectivity

https://www.youtube.com/watch?v=qrgzwd2E6n8

Session (26 & 27):

practice 4:

Chromatic number using python-networkx|Graph Theory|Chromatic number of a graph

https://www.youtube.com/watch?v=sd2ziRkoxqo

Session 28:

Session 29:

Chromatic numbers of a graph.

https://www.youtube.com/watch?v=DZlloPtqf9U

Session 30:

Session 31:

Session (33 & 34):

practice 5:

Applications of graphs with Euler and Hamiltonian path and circuits(Chinese postman Problem)

https://www.youtube.com/watch?v=8z9tBHm1dbA

 

Session 35:

Definition and properties of trees

https://www.youtube.com/watch?v=zEQZpTizgLo

Session 37:

Counting trees, Spanning trees.

https://www.youtube.com/watch?v=TzLswrllE7E

Session 39:

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

https://www.youtube.com/watch?v=8vzgColwS_4

practice 7:

Binary Tree , basic introduction and Code implementation to create tree in Python

https://www.youtube.com/watch?v=IU4YvAt12z4

practice 8:

Binary Trees in Python: Level-order Traversal

https://www.youtube.com/watch?v=aM-oswPn19o

 

 

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.