Syllabus Discrete Mathematics and Graph Theory - (BE04000261) Total Credits Assessment Pattern and Marks Total Marks Theory Tutorial / Practical ESE (E) PA / CA (M) PA / CA (I) PBL (I) ESE (V) 3 70 30 0 30 0 130 Sr. No. Content 1. Propositional logic : Definition, Statements & Notation, Truth Values, Connectives, Statement Formulas & Truth Tables, Well-formed Formulas, Tautologies, Equivalence of Formulas, Duality Law, Tautological Implications, Examples. Predicate logic : Definition of Predicates; Statement functions, Variables, Quantifiers, Predicate Formulas, Free & Bound Variables; The Universe of Discourse, Examples, Valid Formulas & Equivalences, Examples. (Chapters - 1,2) 2. Set Theory : Basic Concepts of Set theory like inclusion, complement, Intersection, Union, Cartesian product, Power Set. Counting and Combinatorics : Basic counting principles, Permutations and combinations, Binomial coefficients and the Binomial theorem, Pigeonhole principle, Inclusion-exclusion principle, Recurrence relations. (Definitions and simple examples only). (Chapters - 3, 4) 3. Functions : Basic concepts of Functions like domain, range, surjective, injective, bijective; Composition of functions, Inverse of function. Algebraic Structures : Algebraic structures with one binary operation - Semigroup, Monoid, Group, Subgroup, normal subgroup, Coset, homomorphic subgroups, Lagrange’s theorem, Congruence relation and quotient structures. Algebraic structures with two binary operation - Ring, Integral domain and field. (Definitions and simple examples only). (Chapters - 5, 6) 4. Relations : Definition, Binary Relation, Representation, Domain, Range, Universal Relation, Void Relation, Union, Intersection, and Complement Operations on Relations, Properties of Binary Relations in a Set : Reflexive, Symmetric, Transitive, Anti-symmetric Relations, Partition and Covering of a Set, Equivalence Relation, Equivalence Classes, Compatibility Relation, Maximum Compatibility Block, Composite Relation, Converse of a Relation, Transitive Closure of a Relation R in Set X. Partial Ordering : Definition, Examples, Simple or Linear Ordering, Totally Ordered Set (Chain), Frequently Used Partially Ordered Relations, Representation of Partially Ordered Sets, Hesse Diagrams, Least & Greatest elements, Minimal & Maximal elements, Least Upper Bound (Supremum), Greatest Lower Bound (infimum), Well-ordered Partially Ordered Sets (Posets). Lattice as Posets, Complete, Distributive, Modular and Complemented lattices, Boolean and pseudo Boolean lattices. (Definitions and simple examples only). (Chapters - 7, 8) 5. Graphs : Introduction, definition, examples; Nodes, edges, adjacent nodes, directed and undirected edge, Directed graph, undirected graph, examples; Initiating and terminating nodes, Loop (sling), Distinct edges, Parallel edges, Multi-graph, simple graph, weighted graphs, examples, Isolated nodes, Null graph; Isomorphic graphs, examples; Degree, Indegree, out-degree, total degree of a node, examples; Subgraphs : definition, examples; Converse (reversal or directional dual) of a digraph, examples; Path : Definition, Paths of a given graph, length of path, examples; Simple path (edge simple), elementary path (node simple), examples; Cycle (circuit), elementary cycle, examples. Reachability : Definition, geodesic, distance, examples; Properties of reachability, the triangle inequality; Reachable set of a given node, examples, Node base, examples Connectedness : Definition, weakly connected, strongly connected, unilaterally connected, examples; Strong, weak, and unilateral components of a graph, examples, Applications to represent Resource allocation status of an operating system, and detection and correction of deadlocks; Matrix representation of graph : Definition, Adjacency matrix, Boolean (or bit) matrix, examples; Determine number of paths of length n through Adjacency matrix, examples; Path (Reachability) matrix of a graph, examples; Warshall’s algorithm to produce Path matrix, Flowchart. Trees : Definition, branch nodes, leaf (terminal) nodes, root, examples; Different representations of a tree, examples; Binary tree, m-ary tree, Full (or complete) binary tree, examples; Converting any m-ary tree to a binary tree, examples; Representation of a binary tree : Linked-list; Tree traversal : Pre-order, in-order, post-order traversal, examples, algorithms; Applications of List structures and graphs. (Chapters - 9, 10)
