Discrete Mathematics and Graph Theory: A Concise Study Companion and Guide (Undergraduate Topics in Computer Science)

Description

This textbook can serve as a comprehensive manual of discrete mathematics and graph theory for non-Computer Science majors; as a reference and study aid for professionals and researchers who have not taken any discrete math course before. It can also be used as a reference book for a course on Discrete Mathematics in Computer Science or Mathematics curricula. The study of discrete mathematics is one of the first courses on curricula in various disciplines such as Computer Science, Mathematics and Engineering education practices. Graphs are key data structures used to represent networks, chemical structures, games etc. and are increasingly used more in various applications such as bioinformatics and the Internet. Graph theory has gone through an unprecedented growth in the last few decades both in terms of theory and implementations; hence it deserves a thorough treatment which is not adequately found in any other contemporary books on discrete mathematics, whereas about 40% of this textbook is devoted to graph theory. The text follows an algorithmic approach for discrete mathematics and graph problems where applicable, to reinforce learning and to show how to implement the concepts in real-world applications. Preface Contents Part I Fundamentals of Discrete Mathematics 1 Logic 1.1 Propositional Logic 1.1.1 Compound Propositions 1.1.2 Conditional Statements 1.1.3 Biconditional Statements 1.1.4 Tautologies and Contradictions 1.1.5 Equivalences 1.1.6 Laws of Logic 1.2 Predicate Logic 1.2.1 Quantifiers 1.2.2 Propositional Functions with Two Variables 1.2.3 Negation 1.2.4 The Universal Conditional Statement 1.2.5 The Existential Conditional Statements 1.3 Review Questions 1.4 Chapter Notes 2 Proofs 2.1 Arguments 2.1.1 Rules of Inference 2.1.2 Definitions 2.2 Direct Proof 2.3 Contrapositive 2.4 Proof by Contradiction 2.5 Proving Biconditional Propositions 2.6 Proofs Using Quantifiers 2.6.1 Proving Universal Statements 2.6.2 Proving Existential Statements 2.7 Proof by Cases 2.8 Review Questions 2.9 Chapter Notes 3 Algorithms 3.1 Basics 3.1.1 Pseudocode Convention 3.1.2 Assignment and Types of Variables 3.1.3 Decision 3.1.4 Loops 3.1.5 Functions and Parameter Passing 3.2 Basic Data Structures 3.3 Sorting 3.3.1 Bubble Sort 3.3.2 Exchange Sort 3.4 Analysis 3.5 Design Methods 3.5.1 Divide and Conquer 3.5.2 Greedy Method 3.5.3 Dynamic Programming 3.6 Difficult Problems 3.7 Review Questions 3.8 Chapter Notes 4 Set Theory 4.1 Definitions 4.1.1 Equality of Sets 4.1.2 Cardinality of a Set 4.2 Subsets 4.3 Venn Diagrams 4.4 Set Operations 4.4.1 Cartesian Product 4.4.2 Set Partition 4.4.3 Operation Precedence 4.5 Laws of Set Theory 4.6 Proving Set Equations 4.6.1 The Element Method 4.6.2 The Tabular Method 4.6.3 The Algebraic Method 4.7 Review Questions 4.8 Chapter Notes 5 Relations and Functions 5.1 Relations 5.1.1 Representations 5.1.2 Inverse of a Relation 5.1.3 Union and Intersection of Relations 5.1.4 Properties of Relations 5.1.5 Equivalence Relations and Partitions 5.1.6 Order 5.1.7 Composite Relation 5.1.8 n-Ary Relations 5.1.9 Transitive Closure 5.1.10 Database Applications 5.2 Functions 5.2.1 Composite Functions 5.2.2 Injection, Surjection and Bijection 5.2.3 Inverse of a Function 5.2.4 Some Special Functions 5.3 Review Questions 5.4 Chapter Notes 6 Sequences, Induction and Recursion 6.1 Sequences 6.1.1 Summation 6.1.2 Arithmetic Sequence and Series 6.1.3 Geometric Sequence 6.1.4 Product Notation 6.1.5 Big Operators 6.2 Induction 6.2.1 Proving Inequalities 6.3 Strong Induction 6.4 Recursion 6.4.1 Recurrence Relations 6.4.2 Recursively Defined Functions 6.4.3 Recursive Algorithms 6.4.4 Recursively Defined Sets 6.5 Structural Induction 6.6 Review Questions 6.7 Chapter Notes 7 Introduction to Number Theory 7.1 Basics 7.2 Division 7.3 Greatest Common Divisor 7.3.1 Euclid's Algorithm 7.3.2 Least Common Multiple 7.4 Prime Numbers 7.4.1 Primality Test 7.4.2 The Sieve of Eratosthenes 7.5 Congruence 7.6 Representation of Integers 7.6.1 Binary System 7.6.2 Hexadecimal System 7.7 Introduction to Cryptography 7.7.1 Diffie-Hellman Protocol 7.7.2 RSA Protocol 7.8 Review Questions 7.9 Chapter Notes 8 Counting and Probability 8.1 Basic Counting Methods 8.1.1 Principle of Inclusion-Exclusion 8.1.2 Additive Counting Principle 8.1.3 Multiplicative Counting Principle 8.1.4 The Pigeonhole Principle 8.1.5 Permutations 8.1.6 Combinations 8.2 Discrete Probability 8.2.1 Probability Measures 8.2.2 Independent Events 8.2.3 Conditional Probability 8.2.4 Tree Diagrams 8.2.5 Random Variables 8.2.6 Stochastic Processes 8.3 Review Questions 8.4 Chapter Notes 9 Boolean Algebras and Combinational Circuits 9.1 Boolean Algebras 9.1.1 Principle of Duality 9.1.2 Boolean Functions 9.1.3 Sum-of-Products Form 9.1.4 Product-of-Sums Form 9.1.5 Conversions 9.1.6 Minimization 9.2 Combinational Circuits 9.2.1 Gates 9.2.2 Designing Combinational Circuits 9.2.3 Arithmetic Circuits 9.3 Review Questions 9.4 Chapter Notes 10 Introduction to the Theory of Computation 10.1 Languages 10.2 Finite State Machines 10.3 Finite State Automata 10.3.1 Analysis 10.3.2 Designing Finite State Automata 10.4 The Relationship Between Languages and Automata 10.5 Nondeterministic Finite State Automata 10.6 Regular Expressions 10.7 Turing Machines 10.8 Complexity Theory 10.8.1 Reductions 10.8.2 NP-Completeness 10.8.3 Coping with NP-Completeness 10.9 Review Questions 10.10 Chapter Notes Part II Graph Theory 11 Introduction to Graphs 11.1 Terminology 11.2 Vertex Degree 11.2.1 Degree Sequence 11.3 Directed Graph 11.4 Representation of a Graph 11.4.1 Adjacency List 11.4.2 Adjacency Matrix 11.4.3 Incidence Matrix 11.5 Subgraphs 11.6 Types of Graphs 11.6.1 Complete Graph 11.6.2 Weighted Graphs 11.6.3 Bipartite Graphs 11.6.4 Regular Graphs 11.6.5 Line Graphs 11.7 Graph Operations 11.7.1 Graph Union 11.7.2 Graph Intersection 11.7.3 Graph Join 11.7.4 Cartesian Product 11.8 Connectivity 11.8.1 Definitions 11.8.2 Connectedness 11.9 Graph Isomorphism 11.10 Review Questions 11.11 Chapter Notes 12 Trees and Traversals 12.1 Definitions and Properties 12.2 Traversal Algorithms 12.2.1 Preorder Traversal 12.2.2 Postorder Traversal 12.3 Binary Trees 12.4 Binary Search Trees 12.5 Depth-First-Search 12.6 Breadth-First Search 12.7 Spanning Trees 12.7.1 Unweighted Spanning Trees 12.7.2 Minimum Spanning Trees 12.8 Review Questions 12.9 Chapter Notes 13 Subgraphs 13.1 Cliques 13.2 Matching 13.2.1 Unweighted Matching 13.2.2 Weighted Matching 13.2.3 Bipartite Graph Matching 13.3 Independent Sets 13.3.1 Algorithm 13.4 Dominating Sets 13.4.1 Algorithm 13.5 Coloring 13.5.1 Vertex Coloring 13.5.2 Edge Coloring 13.6 Vertex Cover 13.6.1 Unweighted Vertex Cover 13.6.2 Weighted Vertex Cover 13.7 Review Questions 13.8 Chapter Notes 14 Connectivity, Network Flows and Shortest Paths 14.1 Basics 14.1.1 Menger's Theorems 14.2 Connectivity Test 14.3 Digraph Connectivity 14.3.1 Strong Connectivity Check 14.3.2 Finding Strongly Connected Components 14.4 Network Flows 14.4.1 A Greedy Algorithm 14.4.2 Residual Graphs 14.4.3 Ford–Fulkerson Algorithm 14.4.4 Bipartite Graph Matching 14.5 Algebraic Connectivity 14.5.1 The Laplacian Matrix 14.5.2 Normalized Laplacian 14.5.3 Eigenvalues 14.6 Shortest Paths 14.7 Chapter Notes 15 Graph Applications 15.1 Analysis of Large Graphs 15.1.1 Degree Distribution 15.1.2 Clustering 15.1.3 Matching Index 15.1.4 Centrality 15.1.5 Network Models 15.2 The Web 15.2.1 The Web Graph 15.2.2 Page Rank Algorithm 15.3 Ad hoc Wireless Networks 15.3.1 Routing in ad hoc Networks 15.3.2 Clustering and Spanning Tree Construction in a WSN 15.4 Biological Networks 15.4.1 Network Motifs 15.4.2 Network Alignment 15.5 Social Networks 15.5.1 Relationships 15.5.2 Structural Balance 15.6 Review Questions 15.7 Chapter Notes A Pseudocode Conventions A.1 Introduction A.2 Data Structures A.3 Control Structures Index