Page 76 - CatalogNEP-PS

Graphs and their representation, Pseudographs, Subgraphs, Degree sequence, Euler‘s theorem,
Isomorphism of graphs, Paths and circuits, Connected graphs, Euler trails and circuits,
Hamiltonian paths and cycles, Adjacency matrix, Weighted graphs, Travelling salesman problem,
Dijkstra‘s algorithm.

UNIT-II: Directed Graphs and Applications, Trees (18 Hours)

The Chinese postman problem; Digraphs, Bellman-Ford algorithm, Tournaments, Directed
network, Scheduling problem; Trees and their properties, Spanning trees, Kruskal‘s algorithm,
Prim‘s algorithm, Acyclic digraphs and Bellman‘s algorithm.
UNIT-III: Planar Graphs, Graph Coloring and Network Flows (15 Hours)

Planar graphs, Euler‘s formula, Kuratowski theorem, Graph coloring, Applications of graph
coloring, Circuit testing and facilities design, Flows and cuts, Max flow-min cut theorem,
Matchings, Hall‘s theorem.

*TUTORIAL (15 Hours (1 Hour per week))

SUGGESTED READINGS:

1. Goodaire, Edgar G., & Parmenter, Michael M. (2011). Discrete Mathematics with
GraphTheory (3rd ed.). Pearson Education Pvt. Ltd. Indian Reprint.
2. Bondy, J. A. & Murty, U.S.R. (2008), Graph Theory with Applications. Springer.
3. Chartrand, Gary, & Zhang, P. (2012). A First Course in Graph Theory. Dover
Publications.
4. Diestel, R. (1997). Graph Theory (Graduate Texts in Mathematics). Springer Verlag.
5. West, Douglas B. (2001). Introduction to graph theory (2nd ed.). Pearson India.

Math.223 Elements of Discrete Mathematics 3+1*

LEARNING OBJECTIVES:

Students are introducing to:
 Order (or partial order) and related properties.
 Notion of a lattice which is also a step towards abstract algebra.
 Concept of Boolean algebra and its applications to minimizing a Boolean polynomial
and switching circuits, which has further applications in computer science.

LEARNING OUTCOMES:

This course will enable the students to:
 Understand the basic concepts of sets, relations, functions, and induction.
 Understand mathematical logic and logical operations to various fields.
 Understand the notion of order and maps between partially ordered sets.
 Minimize a Boolean polynomial and apply Boolean algebra techniquesto decode switching
circuits.

THEORY (45 Hours)

UNIT-I: Sets, Relations, and Functions (18 Hours)

Sets, Propositions and logical operations, Conditional statements, Mathematical induction,
Relations and equivalence relation, Equivalence classes, Partial order relation, Partially
ordered set, Hasse diagrams, Chain, Maximal and minimal elements, least and greatest
elements, Least upper bound, Greatest lower bound, Zorn‘s lemma, Functions and bijective

61