Handbook of Discrete and Combinatorial Mathematics

by Rosen; Kenneth H.

• ISBN13: 9780849301490
• ISBN10: 0849301491
• Edition: 1st
• Format: Hardcover
• Copyright: 1999-09-28
• Publisher: Chapman & Hall

Summary

The importance of discrete mathematics has increased dramatically within the last few years but until now, it has been difficult-if not impossible-to find a single reference book that effectively covers the subject. To fill that void, The Handbook of Discrete and Combinatorial Mathematics presents a comprehensive collection of ready reference material for all of the important areas of discrete mathematics, including those essential to its applications in computer science and engineering. Its topics include:· Logic and foundations· Counting· Number theory· Abstract and linear algebra· Probability· Graph theory· Networks and optimization· Cryptography and coding· Combinatorial designsThe author presents the material in a simple, uniform way, and emphasizes what is useful and practical. For easy reference, he incorporates into the text:· Many glossaries of important terms· Lists of important theorems and formulas· Numerous examples that illustrate terms and concepts· Helpful descriptions of algorithms· Summary tables· Citations of Web pages that supplement the textIf you have ever had to find information from discrete mathematics in your work-or just out of curiosity-you probably had to search through a variety of books to find it. Never again. The Handbook of Discrete Mathematics is now available and has virtually everything you need-everything important to both theory and practice.

Table of Contents

Foundations	1	(80)
Propositional and Predicate Logic	12	(9)
Jerrold W. Grossman
Set Theory	21	(10)
Jerrold W. Grossman
Functions	31	(9)
Jerrold W. Grossman
Relations	40	(10)
John G. Michaels
Proof Techniques	50	(11)
Susanna S. Epp
Axiomatic Program Verification	61	(6)
David Riley
Logic-Based Computer Programming Paradigms	67	(14)
Mukesh Dalal
Counting Methods	81	(54)
Summary of Counting Problems	84	(6)
John G. Michaels
Basic Counting Techniques	90	(6)
Jay Yellen
Permutations and Combinations	96	(11)
Edward W. Packel
Inclusion/Exclusion	107	(6)
Robert G. Rieper
Partitions	113	(7)
George E. Andrews
Burnside/Polya Counting Formula	120	(7)
Alan C. Tucker
Mobius Inversion Counting	127	(2)
Edward A. Bender
Young Tableaux	129	(6)
Bruce E. Sagan
Sequences	135	(78)
Special Sequences	138	(33)
Thomas A. Dowling
Douglas R. Shier
Generating Functions	171	(7)
Ralph P. Grimaldi
Recurrence Relations	178	(11)
Ralph P. Grimaldi
Finite Differences	189	(6)
Jay Yellen
Finite Sums and Summation	195	(6)
Victor S. Miller
Asymptotics of Sequences	201	(3)
Edward A. Bender
Mechanical Summation Procedures	204	(9)
Kenneth H. Rosen
Number Theory	213	(86)
Basic Concepts	219	(7)
Kenneth H. Rosen
Greatest Common Divisors	226	(5)
Kenneth H. Rosen
Congruences	231	(5)
Kenneth H. Rosen
Prime Numbers	236	(19)
Jon F. Grantham
Carl Pomerance
Factorization	255	(4)
Jon F. Grantham
Carl Pomerance
Arithmetic Functions	259	(9)
Kenneth H. Rosen
Primitive Roots and Quadratic Residues	268	(13)
Kenneth H. Rosen
Diophantine Equations	281	(8)
Bart E. Goddard
Diophantine Approximation	289	(6)
Jeff Shalit
Quadratic Fields	295	(4)
Kenneth H. Rosen
Algebraic Structures	299	(56)
John G. Michaels
Algebraic Models	305	(2)
Groups	307	(12)
Permutation Groups	319	(4)
Rings	323	(6)
Polynomial Rings	329	(2)
Fields	331	(10)
Lattices	341	(3)
Boolean Algebras	344	(11)
Linear Systems	355	(72)
Vector Spaces	361	(10)
Joel V. Brawley
Linear Transformations	371	(6)
Joel V. Brawley
Matrix Algebra	377	(15)
Peter R. Turner
Linear Systems	392	(13)
Barry Peyton
Esmond Ng
Eigenanalysis	405	(12)
R. B. Bapat
Combinatorial Matrix Theory	417	(10)
R. B. Bapat
Discrete Probability	427	(68)
Fundamental Concepts	432	(3)
Joseph R. Barr
Independence and Dependence	435	(6)
Joseph R. Barr
Random Variables	441	(7)
Joseph R. Barr
Discrete Probability Computations	448	(4)
Peter R. Turner
Random Walks	452	(7)
Patric Jaillet
System Reliability	459	(9)
Douglas R. Shier
Discrete-Time Markov Chains	468	(9)
Vidyadhar G. Kulkarni
Queueing Theory	477	(7)
Vidyadhar G. Kulkarni
Simulation	484	(11)
Lawrence M. Leemis
Graph Theory	495	(108)
Introduction to Graphs	509	(16)
Lowell W. Beineke
Graph Models	525	(1)
Jonathan L. Gross
Directed Graphs	526	(13)
Stephen B. Maurer
Distance, Connectivity, Traversability	539	(10)
Edward R. Scheinerman
Graph Invariants and Isomorphism Types	549	(8)
Bennet Manvel
Graph and Map Coloring	557	(10)
Arthur T. White
Planar Drawings	567	(7)
Jonathan L. Gross
Topological Graph Theory	574	(6)
Jonathan L. Gross
Enumerating Graphs	580	(6)
Paul K. Stockmeyer
Algebraic Graph Theory	586	(4)
Michael Doob
Analytic Graph Theory	590	(5)
Stefan A. Burr
Hypergraphs	595	(8)
Andreas Gyarfas
Trees	603	(26)
Characterizations and Types of Trees	607	(9)
Lisa Carbone
Spanning Trees	616	(6)
Uri Peled
Enumerating Trees	622	(7)
Paul Stockmeyer
Networks and Flows	629	(88)
Minimum Spanning Trees	633	(8)
J. B. Orlin
Ravindra K. Ahuja
Matchings	641	(11)
Douglas R. Shier
Shortest Paths	652	(11)
J. B. Orlin
Ravindra K. Ahuja
Maximum Flows	663	(10)
J. B. Orlin
Ravindra K. Ahuja
Minimum Cost Flows	673	(10)
J. B. Orlin
Ravindra K. Ahuja
Communication Networks	683	(9)
David Simchi-Levi
Sunil Chopra
Difficult Routing and Assignment Problems	692	(14)
Bruce L. Golden
Bharat K. Kaku
Network Representations and Data Structures	706	(11)
Douglas R. Shier
Partially Ordered Sets	717	(36)
Basic Poset Concepts	724	(14)
Graham Brightwell
Douglas B. West
Poset Properties	738	(15)
Graham Brightwell
Douglas B. West
Combinatorial Designs	753	(44)
Block Designs	759	(11)
Charles J. Colbourn
Jeffrey H. Dinitz
Symmetric Designs & Finite Geometries	770	(8)
Charles J. Colbourn
Jeffrey H. Dinitz
Lating Squares and Orthogonal Arrays	778	(8)
Charles J. Colbourn
Jeffrey H. Dinitz
Matroids	786	(11)
James G. Oxley
Discrete and Computational Geometry	797	(92)
Arrangements of Geometric Objects	805	(19)
Ileana Streinu
Space Filling	824	(6)
Karoly Bezdek
Combinatorial Geometry
Janos Pach	830	(9)
Polyhedra	839	(5)
Tamal K. Dey
Algorithms and Complexity in Computational Geometry	844	(9)
Jianer Chen
Geometric Data Structures and Searching	853	(8)
Dina Kravets
Computational Techniques	861	(6)
Nancy M. Amato
Applications of Geometry	867	(22)
W. Randolph Franklin
Coding Theory and Cryptology	889	(66)
Alfred J. Menezes
Paul C. van Oorschot
Communication Systems and Information Theory	896	(4)
Basics of Coding Theory	900	(3)
Linear Codes	903	(12)
Bounds for Codes	915	(2)
Nonlinear Codes	917	(1)
Convolutional Codes	918	(5)
Basics of Cryptography	923	(4)
Symmetric-Key Systems	927	(8)
Public-Key Systems	935	(20)
Discrete Optimization	955	(84)
Linear Programming	959	(27)
Beth Novick
Location Theory	986	(10)
S. Louis Hakimi
Packing and Covering	996	(10)
Sunil Chopra
David Simchi-Levi
Activity Nets	1006	(10)
S. E. Elmaghraby
Game Theory	1016	(11)
Michael Mesterton-Gibbons
Sperner's Lemma and Fixed Points	1027	(12)
Joseph R. Barr
Theoretical Computer Science	1039	(62)
Computational Models	1048	(14)
Jonathan L. Gross
Computability	1062	(4)
William Gasarch
Languages and Grammars	1066	(11)
Aarto Salomaa
Algorithmic Complexity	1077	(8)
Thomas Cormen
Complexity Classes	1085	(6)
Lane Hemaspaandra
Randomized Algorithms	1091	(10)
Milena Mihail
Information Structures	1101	(52)
Abstract Datatypes	1108	(9)
Charles H. Goldberg
Concrete Data Structures	1117	(8)
Jonathan L. Gross
Sorting and Searching	1125	(14)
Jianer Chen
Hashing	1139	(3)
Viera Krnanova Proulx
Dynamic Graph Algorithms	1142	(11)
Joan Feigenbaum
Sampath Kannan
Biographies	1153	(20)
Victor J. Katz
Index	1173