Discrete Mathematics with Graph Theory

Preface
Acknowledgments
Contents
0 Preliminaries
	0.1 Numbers
	0.2 Euclid’s Algorithm
	0.3 Fundamental Theorem of Arithmetic
	0.4 Euclid’s Theorem
	0.5 Congruence Modulo m
	0.6 Chinese Remainder Theorem
	0.7 Fermat’s and Euler Theorems
	0.8 Exponents and Logarithms
	0.9 Sums
	0.10 Mapping
	Suggested Readings
1
The Language of Sets
	1.1 Introduction
	1.2 Elements and Notations of Sets
	1.3 Construction of Sets
	1.4 Types of Sets
	1.5 Set Operations
		1.5.1 Intersection of Sets
		1.5.2 Union of Sets
		1.5.3 Disjoint Set (Mutually Exclusive)
		1.5.4 Ordinary Difference of Sets (A – B)
		1.5.5 Complementation of Sets
		1.5.6 Universal Set and its Complement
		1.5.7 Symmetric Difference (Boolean Sum)
	1.6 Venn Diagrams
	1.7 Some Basic Results
	1.8 Properties of Set Operations
		1.8.1 Properties of Intersection on Sets
		1.8.2 Properties of Union on Sets
		1.8.3 Number of Elements in a Union of Two or more Sets
	1.9 De-Morgan’s Laws
	1.10 General form of Principle of Inclusion and Exclusion
	Summary
	Suggested Readings
2
Basic Combinatorics
	2.1 Introduction
	2.2 Basic Counting Principles
		2.2.1 The Principle of Disjunctive Counting (Sum Rule)
		2.2.2 The Principle of Sequential Counting (Product Rule)
	2.3 Factorial
	2.4 Permutation and Combination
		2.4.1 Cyclic Permutation
		2.4.2 Pascal’s Identity
		2.4.3 Vandermonde’s Identity
		2.4.4 Pigeonhole Principle
		2.4.5 Inclusion–Exclusion Principle
	2.5 The Binomial Theorem
	2.6 nth Catalan Number
	2.7 Principle of Mathematical Induction (P.M.I)
	2.8 Recurrence Relations
	Summary
	Suggested Readings
3
Mathematical Logic
	3.1 Introduction
	3.2 Propositions (Statements)
	3.3 Connectives
		3.3.1 Negation
		3.3.2 Conjunction
		3.3.3 Disjunction
		3.3.4 Conditional
		3.3.5 Biconditional
	3.4 Equivalence of Formulae
	3.5 Well-Formed Formulae (WFF)
	3.6 Tautologies
	3.7 Principle of Duality
	3.8 Two State Devices
	3.9 The Relay-Switching Devices
	3.10 Logic Gates and Modules
		3.10.1 OR, AND and NOT Gates
		3.10.2 Two-Level Networks
		3.10.3 NOR and NAND Gates
	3.11 Normal Forms (Decision Problems)
		3.11.1 Disjunctive Normal Form (DNF)
		3.11.2 Conjunctive Normal Form (CNF)
		3.11.3 Principal Disjunctive Normal Form (PDNF)
		3.11.4 Principal Conjuctive Normal Forms (PCNF)
	3.12 Rules of Inference
	3.13 Automatic Proving System (Theorems)
	3.14 The Predicate Calculus
		3.14.1 Statement Functions, Variables and Quantifiers
		3.14.2 Free and Bound Variables
		3.14.3 Special Valid Formulae using Quantifiers
		3.14.4 Theory of Inference for the Predicate Calculus
		3.14.5 Formulae Involving More than One Quantifier
	Summary
	Suggested Readings
4
Relations
	4.1 Introduction
	4.2 Product Sets
	4.3 Partitions
	4.4 Relations
	4.5 Binary Relations in a Set
	4.6 Domain and Range of a Relation
		4.6.1 Number of Distinct Relation From set A to B
		4.6.2 Solution sets and Graph of Relations
		4.6.3 Relation as Sets of Ordered Pairs
	4.7 The Matrix of a Relation and Digraphs
	4.8 Paths in Relations and Digraphs
	4.9 Boolean Matrices
		4.9.1 Boolean Operations AND and OR
		4.9.2 Joint and Meet
		4.9.3 Boolean Product
		4.9.4 Boolean Power of a Boolean Matrix
	4.10 Adjacency Matrix of a Relation
	4.11 Gray Code
	4.12 Properties of Relations
		4.12.1 Reflexive and Irreflexive Relations
		4.12.2 Symmetric, Asymmetric and Antisymmetric Relations
		4.12.3 Transitive Relation
	4.13 Equivalence Relations
	4.14 Closure of Relations
	4.15 Manipulation and Composition of Relations
	4.16 Warshall's Algorithm
	4.17 Partial Order Relation
		4.17.1 Totally Ordered Set
		4.17.2 Lexicographic Order
		4.17.3 Hasse Diagrams
	Summary
	Suggested Readings
5
Functions
	5.1 Introduction
		5.1.1 Sum and Product of Functions
	5.2 Special Types of Functions
		5.2.1 Polynomial Function
		5.2.2 Exponential and Logarithmic Function
		5.2.3 Floor and Ceiling Functions
		5.2.4 Transcedental Function
		5.2.5 Identity Function
		5.2.6 Integer Value and Absolute Value Functions
		5.2.7 Remainder Function
	5.3 Composition of Functions
	5.4 Inverse of a Function
	5.5 HASHING FUNCTIONS
	5.6 Countable and Uncountable Sets
	5.7 Characteristic Function of A Set
	5.8 Permutation Function
	5.9 Growth of Functions
	5.10 The Relation Θ
	Summary
	Suggested Readings
6
Lattice Theory
	6.1 Introduction
	6.2 Partial Ordered Sets
		6.2.1 Some Important Terms
		6.2.2 Diagramatical Representation of a Poset (Hasse Diagram)
		6.2.3 Isomorphism
		6.2.4 Duality
		6.2.5 Product of two Posets
	6.3 Lattices as Posets
		6.3.1 Some Properties of Lattices
		6.3.2 Lattices as Algebraic Systems
		6.3.3 Complete Lattice
		6.3.4 Bounded Lattice
		6.3.5 Sublattices
		6.3.6 Ideals of Lattices
	6.4 Modular and Distributive Lattices
	Summary
	Suggested Readings
7
Boolean Algebras and Applications
	7.1 Introduction
	7.2 Boolean Algebra (Analytic Approach)
		7.2.1 Sub-Boolean Algebra
		7.2.2 Boolean Homomorphism
	7.3 Boolean Functions
		7.3.1 Equality of Boolean Expressions
		7.3.2 Minterms and Maxterms
		7.3.3 Functional Completeness
		7.3.4 NAND and NOR
	7.4 Combinatorial Circuits (Synthesis of Circuits)
		7.4.1 Half-Adder and Full-Adder
		7.4.2 Equivalent Combinatorial Circuits
	7.5 Karnaugh Map
		7.5.1 Don’t Care Conditions
		7.5.2 Minimization Process
	7.6 Finite State Machines
	Summary
	Suggested Readings
8
Fuzzy Algebra
	8.1 Introduction
	8.2 Crisp Sets and Fuzzy Sets
	8.3 Some Useful Definitions
	8.4 Operations of Fuzzy Sets
	8.5 Interval-Valued Fuzzy Sets (I-V Fuzzy Sets)
		8.5.1 Union and Intersection of two I–V Fuzzy Sets
	8.6 Fuzzy Relations
	8.6 Fuzzy Measures
		8.7.1 Belief and Plausibility Measures
		8.7.2 Probability Measure
		8.7.3 Uncertainty and Measures of Fuzziness
		8.7.4 Uncertainty and Information
	8.8 Applications of Fuzzy Algebras
		8.8.1 Natural, Life and Social Sciences
		8.8.2 Engineering
		8.8.3 Medical Sciences
		8.8.4 Management Sciences and Decision Making Process
		8.8.5 Computer Science
	8.9 Uniqueness of Uncertainty Measures
		8.9.1 Shannon’s Entropy
		8.9.2 U-uncertainty
		8.9.3 Uniqueness of the U-uncertainty for Two-Value Possibility Distributions
	Summary
	Suggested Readings
9 Formal Languages and Automata Theory
	9.1 Introduction
	9.2 Formal Languages
		9.2.1 Equality of Words
		9.2.2 Concatenation of Languages
		9.2.3 Kleene Closure
	9.3 Grammars
		9.3.1 Phase-structure Grammar
		9.3.2 Derivations of Grammar
		9.3.3 Backus-Normal Form (BNF) or Backus Naur Form
		9.3.4 Chomsky Grammar
		9.3.5 Ambiguous Grammar
	9.4 Finite-State Automation (FSA)
		9.4.1 Counting to Five
		9.4.2 Process of Getting up in the Morning (Alarm)
		9.4.3 Traffic Light
		9.4.4 Vending Machine
	9.5 Finite-State Machine (FSM)
	9.6 Finite-State Automata
		9.6.1 Deterministic Finite-State Automata (DFSA)
		9.6.2 Nondeterministic Finite-State Automata
		9.6.3 Equivalent Nondeterministic Finite State Automata
	Summary
	Suggested Readings
10
The Basics of Graph Theory
	10.1 Introduction
	10.2 Graph! What is it?
		10.2.1 Simple Graph
		10.2.2 Graph
		10.2.3 Loops
		10.2.4 Degree of Vertices
		10.2.5 Equivalence Relation
		10.2.6 Random Graph Model
		10.2.7 Isolated Vertex, Pendent Vertex and Null Graph
	10.3 Digraphs
	10.4 Path, Trail, Walk and Vertex Sequence
	10.5 Subgraph
	10.6 Circuit and Cycle
	10.7 Cycles and Multiple Paths
	10.8 Connected Graph
	10.9 Spanning Subgraph and Induced Subgraph
	10.10 Eulerian Graph (Eulerian Trail and Circuit)
	10.11 Hamiltonian Graph
	10.12 Biconnected Graph
	10.13 Algebraic terms and operations used in Graph Theory
		10.13.1 Graphs Isomorphism
		10.13.2 Union of two Graphs
		10.13.3 Intersection of two Graphs
		10.13.4 Addition of two Graphs
		10.13.5 Direct Sum or Ring Sum of two Graphs
		10.13.6 Product of two Graphs
		10.13.7 Composition of two Graphs
		10.13.8 Complement of a Graph
		10.13.9 Fusion of a Graph
		10.13.10 Rank and Nullity
		10.13.11 Adjacency Matrix
		10.13.12 Some Important Theorems
	10.14 Some Popular Problems in Graph Theory
		10.14.1 Tournament Ranking Problem
		10.14.2 The Königsberg Bridge Problem
		10.14.3 Four Colour Problem
		10.14.4 Three Utilities Problem
		10.14.5 Traveling - Salesman Problem
		10.14.6 MTNL’S Networking Problem
		10.14.7 Electrical Network Problems
		10.14.8 Satellite Channel Problem
	10.15 Applications of Graphs
	Summary
	Suggested Readings
11
Trees
	11.1 Introduction
	11.2 Definitions of a Tree
	11.3 Forest
	11.4 Rooted Graph
	11.5 Parent, Child, Sibling and Leaf
	11.6 Rooted Plane Tree
	11.7 Binary Trees
	11.8 Spanning Trees
	11.9 Breadth – First Search and Depth – First Search (BFS and DFS)
	11.10 Minimal Spanning Trees
		11.10.1 Kruskal’s Algorithm (for Finding a Minimal Spanning Tree)
		11.10.2 Prim’s Algorithm
	11.11 Directed Trees
	Summary
	Suggested Readings
12
Planar Graphs
	12.1 Introduction
	12.2 Geometrical Representation of Graphs
	12.3 Bipertite Graph
	12.4 Homeomorphic Graph
	12.5 Kuratowski’s Graphs
	12.6 Dual Graphs
	12.7 Euler’s Formula
	12.8 Outerplanar Graphs
		12.8.1 k-outerplanar Graphs
	Summary
	Suggested Readings
13
Directed Graphs
	13.1 Introduction
	13.2 Directed Paths
	13.3 Tournament
	13.4 Directed Cycles
	13.5 Acyclic Graph
	13.6 Di-Orientable Graph
	13.7 Applications of Directed Graphs
		13.7.1 Job Sequencing Problem
		13.7.2 To Design an Efficient Computer Drum
		13.7.3 Ranking of the Participants in a Tournament
	13.8 Network Flows
	13.9 Improvable Flows
	13.10 Max-Flow Min-Cut Theorem
	13.11 k-flow
	13.12 Tutte’s Problem
	Summary
	Suggested Readings
14
Matching and Covering
	14.1 Introduction
	14.2 Matching and Covering in Bipertite Graphs
		14.2.1 Covering
	14.3 Perfect Matching
	14.4 Factor-critical Graph
	14.5 Complete Matching
	14.6 Matrix Method to Find Matching of a Bipertite Graph
	14.7 Path Covers
	14.8 Applications
		14.8.1 The Personnel Assignment Problem
		14.8.2 The Optimal Assignment Problem
		14.8.3 Covering to Switching Functions
	Summary
	Suggested Readings
15
Colouring of Graphs
	15.1 Introduction
	15.2 Vertex Colouring
	15.3 Chromatic Polynomial
		15.3.1 Bounds of the Chromatic Number
	15.4 Exams Scheduling Problem
	15.5 Edge Colouring
	15.6 List Colouring
	15.7 Greedy Colouring
	15.8 Applications
		15.8.1 The Time Table Problem
		15.8.2 Scheduling of Jobs
		15.8.3 Ramsey Theory
		15.8.4 Storage Problem
	Summary
	Suggested Readings
References
Index