# Graph Theory

Teacher

Category

### Course Attendees

Still no participant

Still no reviews

# Code(Credit) : CUTM-1531(3-1-0)

## 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 1:

Introduction to Graphs and Definition of graphs.

## Session 2:

Basic terminologies  of graph and types of graphs.

## Session 4:

Sub graphs and graph Isomorphism

## practice 1:

An Introduction to Graph Neural Networks: Models and Applications

## Session 7:

Directed Graphs and Types of Digraphs

## Session 10:

Directed paths and connectedness,

## Session 11:

Euler Digraphs, De-Brujin sequences,

## practice 2:

Ways to Represent GRAPHS using Python

## Session 15:

Basic concepts of Planar Graphs,

## Session 19:

Euler’s formula for planar graphs

## practice 3:

A look in to Planar Graphs and Euler's Relationship

## Session 22:

Distance, cut-vertices, cut-edges, blocks

## Session 23:

weighted graphs, connectivity

## practice 4:

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

## Session 29:

Chromatic numbers of a graph.

## practice 5:

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

## Session 35:

Definition and properties of trees

## Session 37:

Counting trees, Spanning trees.

## practice 6:

Application of Minimum spanning tree in  a Net work model

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

### Dr. Bhairaba Kumar Majhi

##### Asst.Professor
VIEW PROFILE

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.