Discrete Mathematical Structures and Graph Theory

Details of the course ↓

Unit No.

CONTENT

1

Matrices ⇗:

  • Notation and Definition, Types of Matrices, Algebra of Matrices, Transpose of a Matrix, Solution of linear Equations by Matrix method, Rank of matrix, Eigen values and Eigen vectors, Cayley Hamilton theorem.

2

Boolean algebra ⇗:

  • Basic operations, Boolean functions, Boolean expression, De-Morgan’s theorem, Logic gates, SOP and POS forms, Normal forms, Simplification of Boolean expression, Logic and switching networks, Karnaugh map method for simplification of Boolean expression

3

Graph Theory ⇗:

  • Definition and application of graphs, Konigsberg bridge problem, Simple graph, multi graph and pseudo graph, directed and undirected graphs, degree of a vertex, handshaking theorem, Types of graphs, sub graphs and isomorphic graphs, bipartite graphs, operations of graphs, representation of graphs.

4

Graph Theory 2 ⇗:

  • Paths, Cycles ,cut vertex, cut set and bridge, Connectedness in directed and undirected graphs, Connectivity, Eulerian graph, Hamiltonian graph, Dijkstra’s algorithm for shortest path, planar graphs, Euler’s formula, Graph coloring, Wetch Powell algorithm, Chromatic polynomial, Decomposition theorem.

5

Tree ⇗:

  • Trees and their properties, Rooted tree, Spanning tree, minimal spanning tree, fundamental circuits, rank and nullity, Kruskal’s algorithm, Binary tree.