Discrete mathematics with graph theory

3rd ed.
  • 4.0 (1 rating)
  • 36 Want to read
  • 1 Currently reading
  • 1 Have read

My Reading Lists:

Create a new list

  • 4.0 (1 rating)
  • 36 Want to read
  • 1 Currently reading
  • 1 Have read

Buy this book

Last edited by ImportBot
August 19, 2020 | History

Discrete mathematics with graph theory

3rd ed.
  • 4.0 (1 rating)
  • 36 Want to read
  • 1 Currently reading
  • 1 Have read

This work doesn't have a description yet. Can you add one?

Publish Date
Language
English
Pages
592

Buy this book

Previews available in: English

Edition Availability
Cover of: Discrete mathematics with graph theory
Discrete mathematics with graph theory
2006, Pearson Prentice Hall
in English - 3rd ed.
Cover of: Discrete mathematics with graph theory
Discrete mathematics with graph theory
2002, Prentice Hall
in English - 2nd ed.
Cover of: Discrete mathematics with graph theory
Discrete mathematics with graph theory
1998, Prentice Hall
in English

Add another edition?

Book Details


Table of Contents

Preface
Page xi
To the Student
Page xv
Suggested Lecture Schedule
Page xix
0. Yes, There Are Proofs!
Page 1
0.1. Compound Statements
Page 2
0.2. Proofs in Mathematics
Page 10
Review Exercises
Page 17
1. Logic
Page 19
1.1. Truth Tables
Page 19
1.2. The Algebra of Propositions
Page 23
1.3. Logical Arguments
Page 30
Review Exercises
Page 36
2. Sets and Relations
Page 38
2.1. Sets
Page 38
2.2. Operations on Sets
Page 43
2.3. Binary Relations
Page 51
2.4. Equivalence Relations
Page 57
2.5. Partial Orders
Page 64
Review Exercises
Page 70
3. Functions
Page 72
3.1. Basic Terminology
Page 72
3.2. Inverses and Composition
Page 80
3.3. One-to-One Correspondence and the Cardinality of a Set
Page 88
Review Exercises
Page 96
4. The Integers
Page 98
4.1. The Division Algorithm
Page 98
4.2. Divisibility and the Euclidean Algorithm
Page 105
4.3. Prime Numbers
Page 114
4.4. Congruence
Page 125
4.5. Applications of Congruence
Page 135
Review Exercises
Page 145
5. Induction and Recursion
Page 147
5.1. Mathematical Induction
Page 147
5.2. Recursively Defined Sequences
Page 160
5.3. Solving Recurrence Relations; The Characteristic Polynomial
Page 170
5.4. Solving Recurrence Relations; Generating Functions
Page 176
Review Exercises
Page 182
6. Principles of Counting
Page 184
6.1. The Principle of Inclusion-Exclusion
Page 184
6.2. The Addition and Multiplication Rules
Page 192
6.3. The Pigeonhole Principle
Page 199
Review Exercises
Page 204
7. Permutations and Combinations
Page 205
7.1. Permutations
Page 205
7.2. Combinations
Page 210
7.3. Elementary Probability
Page 216
7.4. Probability Theory
Page 224
7.5. Repetitions
Page 231
7.6. Derangements
Page 236
7.7. The Binomial Theorem
Page 239
Review Exercises
Page 245
8. Algorithms
Page 247
8.1. What Is an Algorithm?
Page 247
8.2. Complexity
Page 253
8.3. Searching and Sorting
Page 265
8.4. Enumeration of Permutations and Combinations
Page 276
Review Exercises
Page 280
9. Graphs
Page 281
9.1. A Gentle Introduction
Page 281
9.2. Definitions and Basic Properties
Page 288
9.3. Isomorphism
Page 296
Review Exercises
Page 301
10. Paths and Circuits
Page 304
10.1. Eulerian Circuits
Page 304
10.2. Hamiltonian Cycles
Page 311
10.3. The Adjacency Matrix
Page 319
10.4. Shortest Path Algorithms
Page 326
Review Exercises
Page 336
11. Applications of Paths and Circuits
Page 339
11.1. The Chinese Postman Problem
Page 339
11.2. Digraphs
Page 344
11.3. RNA Chains
Page 352
11.4. Tournaments
Page 356
11.5. Scheduling Problems
Page 361
Review Exercises
Page 367
12. Trees
Page 370
12.1. Trees and Their Properties
Page 370
12.2. Spanning Trees
Page 379
12.3. Minimum Spanning Tree Algorithms
Page 384
12.4. Acyclic Digraphs and Bellman's Algorithm
Page 393
12.5. Depth-First Search
Page 398
12.6. The One-Way Street Problem
Page 403
Review Exercises
Page 409
13. Planar Graphs and Colorings
Page 411
13.1. Planar Graphs
Page 411
13.2. Coloring Graphs
Page 419
13.3. Circuit Testing and Facilities Design
Page 427
Review Exercises
Page 435
14. The Max Flow-Min Cut Theorem
Page 438
14.1. Flows and Cuts
Page 438
14.2. Constructing Maximal Flows
Page 445
14.3. Applications
Page 450
14.4. Matchings
Page 454
Review Exercises
Page 460
Appendix
Page A-1
Solutions to True/False Questions and Selected Exercises
Page S-1
Glossary
Page G-1
Index
Page I-1

Edition Notes

Published in
Upper Saddle River, N.J
Genre
Textbooks.

Classifications

Dewey Decimal Class
510
Library of Congress
QA39.3 .G66 2006, QA39.3.G66 2006

The Physical Object

Pagination
p. cm.
Number of pages
592

Edition Identifiers

Open Library
OL3425410M
ISBN 10
0131679953
LCCN
2005048789
OCLC/WorldCat
60312096
LibraryThing
1002060
Goodreads
388054

Work Identifiers

Work ID
OL2682030W

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Download catalog record: RDF / JSON