Discrete Mathematics With Graph Theory 3ed

✍ Scribed by Edward G. Goodaire, Michael M. Parmenter

• Year: 2005
• Tongue: English
• Leaves: 579
• Edition: 3
• Category: Library

✦ Table of Contents

I5CRETE АТПЕМАТ1С5
Preface
New in the Third Edition
Thank You
To the Student
From a Student
EXERCISES
Suggested
Lecture Schedule
Yes, There are Proofs!
Logic
Contents
Yes, There Are Proofs!
1 Logic
2 Sets and Relations
3 Functions
4 The Integers
1
19
38
72
98
7 Permutations and Combinations 205
о
Yes, There Are Proofs!
0.1 Compound Statements
“And” and “Or”
Implication
The Converse of an Implication
Double Implication
Negation
The Contrapositive
Quantifiers
What May I Assume?
True/False Questions
Exercises
0.2 Proofs in Mathematics
Direct Proof
Proof by Cases
Prove the Contrapositive
True/False Questions
Exercises
Review Exercises for Chapter О
Logic
1.1 Truth Tables
True/False Questions
Exercises
1.2 The Algebra of Propositions
Some Basic Logical Equivalences
EXAMPLE 10
EXAMPLE 11
Application: Three-Way Switches
True/False Questions
Exercises
1.3 Logical Arguments
Rules of Inference
a
True/False Questions
Exercises
2
Sets and Relations
2.1 Sets
True/False Questions
Exercises
2.2 Operations on Sets
Union and Intersection
True/False Questions
Exercises
2.3 Binary Relations
EXAMPLE 16
EXAMPLE 18
Higher-Order Relations
True/False Questions
Exercises
2.4 Equivalence Relations
EXAMPLE 32
True/FaIse Questions
Exercises
2.5 Partial Orders
True/False Questions
Exercises
Key Terms & Ideas
Review Exercises for Chapter 2
3.1
3
Functions
Baste Terminology
The Identity Function
The Ins and Outs of Functions
True/False Questions
Exercises
3.2 Inverses and Composition
EXAMPLE 19
Composition of Functions
True/False Questions
Exercises
3.3 One-to-One Correspondence and the Cardinality of a Set
Key Terms & Ideas
Review Exercises for Chapter 3
The Integers
4.1 The Division Algorithm
•e
Representing Natural Numbers in Various Bases
True/False Questions
Exercises
4.2 Divisibility and the Euclidean Algorithm
Solution. We have
The Lattice of Divisors of a Natural Number
True/False Questions
Exercises
4.3 Prime Numbers
Mersenne Primes
Fermat Primes
How Many Primes Are There?
More Open Problems
True/False Questions
Exercises
True/False Questions
Exercises
4.5 Applications of Congruence
International Standard Book Numbers
Universal Product Codes
The Chinese Remainder Theorem
Determining Numbers by Their Remainders
Cryptography
True/False Questions
Exercises
Key Terms & Ideas
Review Exercises for Chapter 4
5
Induction and Recursion
5.1 Mathematical Induction
Mathematical Induction and Well Ordering
True/False Questions
Exercises
5.2 Recursively Defined Sequences
Some Special Sequences
an = a + (n — l)d.
<7> $ = ^[2a + (n-lW],
= |(2 ■ 3"-1 + 3"-1 - 1) = 1(3 ■ 3й-’ - 1) = |(3" - 1)
Application: Pseudorandom Numbers
True/False Questions
Exercises
5.3 Solving Recurrence Relations; The Characteristic Polynomial
True/False Questions
Exercises
5.4 Solving Recurrence Relations; Generating Functions
Key Terms & Ideas
Review Exercises for Chapter 5
6
Principles of Counting
6.1 The Principle of Inclusion-Exclusion
True/False Questions
Exercises
6.2 The Addition and Multiplication Rules
True/False Questions
Exercises
6.3
Pause 9
True/False Questions
Exercises
Review Exercises for Chapter 6
Permutations and Combinations
7.1 Permutations
Л? = Л(Д-1)(Л-2)..(3)(2)(1)
True/False Questions
Exercises
7.2 Combinations
Pin. r) ”71
True/False Questions
Exercises
7.3 Elementary Probability
Solution.
Solution.
11.
True/False Questions
Exercises
7.4 Probability Theory
14.
17.
True/False Questions
Exercises
75 Repetitions
P(n,r)
True/Fafse Questions
Exercises
7.6 Derangements
True/False Questions
Exercises
7.7 The Binomial Theorem
Solution.
Solution.
True/False Questions
Exercises
Key Terms & Ideas
Review Exercises for Chapter 7
8
Algorithms
8.1 What Is an Algorithm?
= a0 + (aL + (a2 + j- (an_, + a„x)x) ■ • • )•
True/False Questions
Exercises
8.2 Complexity
EXAMPLE 8
EXAMPLE 9
True/False Questions
Exercises
8.3 Searching and Sorting
EXAMPLE 23 For the input list
True/False Questions
Exercises
8.4 Enumeration of Permutations and Combinations
True/False Questions
Exercises
Key Terms & Ideas
Review Exercises for Chapter 8
Graphs
9.1 A Gentle Introduction
True/False Questions
Exercises
9.2 Definitions and Basic Properties
True/False Questions
Exercises
9.3 Isomorphism
True/False Questions
Exercises
Key Terms & Ideas
Review Exercises for Chapter 9
10
Paths and Circuits
10.1 Eulerian Circuits
True/False Questions
Exercises
10.2 Hamiltonian Cycles
Application: Gray Codes6
True/False Questions
Exercises
10.3 The Adjacency Matrix
EXAMPLE 8
True/False Questions
Exercises
10.4 Shortest Path Algorithms
The Traveling Salesman's Problem
True/False Questions
Exercises
Key Terms & Ideas
Review Exercises for Chapter 1O
11
Applications of Paths and Circuits
11.1 The Chinese Postman Problem
Figure 11.1
True/False Questions
Exercises
11.2 Digraphs
True/False Questions
Exercises
11.3 RNA Chains
I
True/False Questions
Exercises
*11.4 Tournaments
True/False Questions
Exercises
11.5 Scheduling Problems
Figure 11.26
Figure 11.27
Exercises
Key Terms & Ideas
Review Exercises for Chapter 11
12
Trees
12.1 Trees and their Properties
Figure 12 .8
Figure 12.12
True/False Questions
Exercises
12.2 Spanning Trees
True/False Questions
Exercises
12-3 Minimum Spanning Tree Algorithms
A Bound for a Minimum Hamiltonian Cycle
True/False Questions
Exercises
12. 4 Acyclic Digraphs and Bellman's Algorithm
True/False Questions
Figure 12,22
Exercises
12.5 Depth-First Search
True/False Questions
Exercises
Figure 12.26
12.6 The One-Way Street Problem
Exercises
Key Terms & Ideas
Review Exercises for Chapter 12
13
Planar Graphs and Colorings
13.1 Planar Graphs
All
V - E + F = 2,
True/False Questions
Exercises
13.2 Coloring Graphs
True/False Questions
Exercises
Child Doesn't get along with
13.3 Circuit Testing and Facilities Design
Circuit Testing
Figure 13.19
Facilities Design
Figure 13. 22
8. №№№).№.№).
True/False Questions
Exercises
Figure 13.24
Key Terms & Ideas
Review Exercises for Chapter 13
The Max Flow-Min Cut Theorem
14.1 Flows and Cuts
The Construction of Flows
True/False Questions
Exercises
14.2 Constructing Maximal Flows
val(^) = £2 ~
= £2 “ °) = X2 Cuv ~ caP^’ T>>-
Rational Weights
True/False Questions
Exercises
14.3 Applications
Multiple Sources and/or Sinks
Supply and Demand Problems
Undirected Edges
Edge-Disjoint Paths
Job Assignments
True/False Questions
Exercises
14.4 Matchings
True/False Questions
Exercises
Key Terms & Ideas
Review Exercises for Chapter 14
Bettor Teams
Matrices and Determinants
Determinants
Evaluating a Determinant with Elementary
Row Operations
EXAMPLE 5
Solutions to True/False Questions and Selected Exercises
Exercises 0,1
Section 0.2 True/False
Exercises 0.2
Section 1.1 True/False
Exercises 1.1
Exercises 1.2
Exercises 1.3
Section 2.1 True/False
Exercises 2.1
Section 2.2 True/False
Exercises 2.2
Exercises 2.3
Section 2.4 True/False
Exercises 2.4
Section 2.5 True/False
Exercises 2.5
Section 3.1 True/False
Exercises 3.1
Section 3.2 True/False
Exercises 3.2
Section 3.3 True/False
Exercises 3.3
Section 4.1 True/False
Exercises 4.1
Section 4.2 True/False
Exercises 4.2
Section 4.3 True/False
Exercises 4.3
Section 4.4 True/False
Exercises 4.4
Section 4.5 True/False
Exercises 4.5
Section 5.1 True/False
Exercises 5.1
Section 5.2 True/False
Exercises 5.2
Section 5.3 True/False
Exercises 5.3
Section 5.4 True/False
Exercises 5.4
Section 6.1 True/False
Exercises 6.1
Section 6.2 True/False
Exercises 6.2
Section 6.3 True/False
Exercises 6.3
Section 7.1 True/False
Exercises 7.1
Section 7.2 True/False
Exercises 7.2
Section 7.3 True/False
Exercises 7.3
Section 7.4 True/False
Exercises 7.4
Section 7.5 True/False
Exercises 7.5
Section 7.6 True/False
Exercises 7.6
Section 7.7 True/False
Exercises 7.7
Section 8.1 True/False
Exercises 8.1
Section 8.2 True/False
Exercises 8.2
Section 8.3 True/False
Exercises 8.3
Section 8.4 True/False
Section 9.1 True/False
Exercises 9.1
Section 9.2 True/False
Exercises 9.2
Section 9.3 True/False
Exercises 9.3
Section 10.1 True/False
Section 10.2 True/False
Exercises 10.2
Section 10.3 True/False
Exercises 10.3
Section 10.4 True/False
Exercises 10.4
Section 11.1 True/False
Section 11.2 True/False
Exercises 11.2
Section 11.3 True/False
Exercises 11.3
Section 11.4 True/False
Exercises 11.4
Section 11.5 True/False
Exercises 11.5
Section 12.1 True/False
Exercises 12.1
Section 12.3 True/False
Exercises 12.3
Section 12.4 True/False
Exercises 12.4
Section 12.5 True/False
Exercises 12.5
Exercises 12.6
Exercises 13.1
Section 13.2 True/False
Exercises 13.2
Section 13.3 True/False
Exercises 13.3
Section 14,1 True/False
Exercises 14.1
Section 14.2 True/False
Exercises 14.2
Section 14.3 True/False
Exercises 14.3
Section 14.4 True/False
Exercises 14.4
Glossary
c
Index
I5CRETE ATHEMATIC5