DISCRETE AND COMBINATORIAL UTHEMATICS

HANDBOOK OF

DISCRETE AND COMBINATORIAL

UTHEMATICS

KENNETH H. ROSEN AT&T Laboratories Editor-in-Chief JOHN G. MICHAELS SUNY Brockport Project Editor JONATHAN L. GROSS Columbia University Associate Editor JERROLD W. GROSSMAN Oakland University Associate Editor DOUGLAS R SHIER Clemson University Associate Editor

CRC Press Boca Raton London New York Washington, D.C.

Library of Congress Cataloging-in-Publication Data

Handbook of discrete and combinatorial mathematics / Kenneth H. Rosen, editor in chief, John G. Michaels, project editor...[et al.].

p. c m . Includes bibliographical references and index. ISBN 0-8493-0149-1 (alk. paper) 1. Combinatorial analysis-Handbooks, manuals, etc. 2. Computer science-Mathematics-Handbooks, manuals, etc. I. Rosen, Kenneth H. II. Michaels, John G.

QAl64.H36 1999 5 I I .`6--dc21

99-04378

This book contains information obtained from authentic and highIy regarded sources. Reprinted materia1 is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials or for the consequences of their use.

Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, microfilming, and recording, or by any information storage or retrieval system, without prior permission in writing from the publisher.

All rights reserved. Authorization to photocopy items for internal or personal use, or the personal or internal use of specific clients, may be granted by CRC Press LLC, provided that $50 per page photocopied is paid directly to Copyright clearance Center, 222 Rosewood Drive, Danvers, MA 01923 USA. The fee code for users of the Transactional Reporting Service is ISBN 0-8493-0149-1/00/$0.00+$.50. The fee is subject to change without notice. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.

The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for creating new works, or for resale. Specific permission must be obtained in writing from CRC Press LLC for such copying.

Direct all inquiries to CRC Press LLC, 2000 N.W. Corporate Blvd., Boca Raton, Florida 33431.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation, without intent to infringe.

Visit the CRC Press Web site at

? 2000 by CRC Press LLC

No claim to original U.S. Government works International Standard Book Number 0-8493-0149-1

Library of Congress Card Number 99-04378 Printed in the United States of America 4 5 6 7 8 9 IO 11 12 13

Printed on acid-free paper

CONTENTS

1. FOUNDATIONS

1.1 Propositional and Predicate Logic -- Jerrold W. Grossman 1.2 Set Theory -- Jerrold W. Grossman 1.3 Functions -- Jerrold W. Grossman 1.4 Relations -- John G. Michaels 1.5 Proof Techniques -- Susanna S. Epp 1.6 Axiomatic Program Verification -- David Riley 1.7 Logic-Based Computer Programming Paradigms -- Mukesh Dalal

2. COUNTING METHODS

2.1 Summary of Counting Problems -- John G. Michaels 2.2 Basic Counting Techniques -- Jay Yellen 2.3 Permutations and Combinations -- Edward W. Packel 2.4 Inclusion/Exclusion -- Robert G. Rieper 2.5 Partitions -- George E. Andrews 2.6 Burnside/Po? lya Counting Formula -- Alan C. Tucker 2.7 Mo? bius Inversion Counting -- Edward A. Bender 2.8 Young Tableaux -- Bruce E. Sagan

3. SEQUENCES

3.1 Special Sequences -- Thomas A. Dowling and Douglas R. Shier 3.2 Generating Functions -- Ralph P. Grimaldi 3.3 Recurrence Relations -- Ralph P. Grimaldi 3.4 Finite Differences -- Jay Yellen 3.5 Finite Sums and Summation -- Victor S. Miller 3.6 Asymptotics of Sequences -- Edward A. Bender 3.7 Mechanical Summation Procedures -- Kenneth H. Rosen

4. NUMBER THEORY

4.1 Basic Concepts -- Kenneth H. Rosen 4.2 Greatest Common Divisors -- Kenneth H. Rosen 4.3 Congruences -- Kenneth H. Rosen 4.4 Prime Numbers -- Jon F. Grantham and Carl Pomerance 4.5 Factorization -- Jon F. Grantham and Carl Pomerance 4.6 Arithmetic Functions -- Kenneth H. Rosen 4.7 Primitive Roots and Quadratic Residues -- Kenneth H. Rosen 4.8 Diophantine Equations -- Bart E. Goddard 4.9 Diophantine Approximation -- Jeff Shalit 4.10 Quadratic Fields -- Kenneth H. Rosen

c 2000 by CRC Press LLC

5. ALGEBRAIC STRUCTURES

5.1 Algebraic Models 5.2 Groups 5.3 Permutation Groups 5.4 Rings 5.5 Polynomial Rings 5.6 Fields 5.7 Lattices 5.8 Boolean Algebras

-- John G. Michaels

6. LINEAR ALGEBRA

6.1 Vector Spaces -- Joel V. Brawley 6.2 Linear Transformations -- Joel V. Brawley 6.3 Matrix Algebra -- Peter R. Turner 6.4 Linear Systems -- Barry Peyton and Esmond Ng 6.5 Eigenanalysis -- R. B. Bapat 6.6 Combinatorial Matrix Theory -- R. B. Bapat

7. DISCRETE PROBABILITY

7.1 Fundamental Concepts -- Joseph R. Barr 7.2 Independence and Dependence -- Joseph R. Barr 435 7.3 Random Variables -- Joseph R. Barr 7.4 Discrete Probability Computations -- Peter R. Turner 7.5 Random Walks -- Patrick Jaillet 7.6 System Reliability -- Douglas R. Shier 7.7 Discrete-Time Markov Chains -- Vidyadhar G. Kulkarni 7.8 Queueing Theory -- Vidyadhar G. Kulkarni 7.9 Simulation -- Lawrence M. Leemis

8. GRAPH THEORY

8.1 Introduction to Graphs -- Lowell W. Beineke 8.2 Graph Models -- Jonathan L. Gross 8.3 Directed Graphs -- Stephen B. Maurer 8.4 Distance, Connectivity, Traversability -- Edward R. Scheinerman 8.5 Graph Invariants and Isomorphism Types -- Bennet Manvel 8.6 Graph and Map Coloring -- Arthur T. White 8.7 Planar Drawings -- Jonathan L. Gross 8.8 Topological Graph Theory -- Jonathan L. Gross 8.9 Enumerating Graphs -- Paul K. Stockmeyer 8.10 Algebraic Graph Theory -- Michael Doob 8.11 Analytic Graph Theory -- Stefan A. Burr 8.12 Hypergraphs -- Andreas Gyarfas

9. TREES

9.1 Characterizations and Types of Trees -- Lisa Carbone 9.2 Spanning Trees -- Uri Peled 9.3 Enumerating Trees -- Paul Stockmeyer

c 2000 by CRC Press LLC

10. NETWORKS AND FLOWS

10.1 Minimum Spanning Trees -- J. B. Orlin and Ravindra K. Ahuja 10.2 Matchings -- Douglas R. Shier 10.3 Shortest Paths -- J. B. Orlin and Ravindra K. Ahuja 10.4 Maximum Flows -- J. B. Orlin and Ravindra K. Ahuja 10.5 Minimum Cost Flows -- J. B. Orlin and Ravindra K. Ahuja 10.6 Communication Networks -- David Simchi-Levi and Sunil Chopra 10.7 Difficult Routing and Assignment Problems -- Bruce L. Golden and Bharat K. Kaku 10.8 Network Representations and Data Structures -- Douglas R. Shier

11. PARTIALLY ORDERED SETS

11.1 Basic Poset Concepts -- Graham Brightwell and Douglas B. West 11.2 Poset Properties -- Graham Brightwell and Douglas B. West

12. COMBINATORIAL DESIGNS

12.1 Block Designs -- Charles J. Colbourn and Jeffrey H. Dinitz 12.2 Symmetric Designs & Finite Geometries -- Charles J. Colbourn and Jeffrey H. Dinitz 12.3 Latin Squares and Orthogonal Arrays -- Charles J. Colbourn and Jeffrey H. Dinitz 12.4 Matroids -- James G. Oxley

13. DISCRETE AND COMPUTATIONAL GEOMETRY

13.1 Arrangements of Geometric Objects -- Ileana Streinu 13.2 Space Filling -- Karoly Bezdek 13.3 Combinatorial Geometry -- Ja? nos Pach 13.4 Polyhedra -- Tamal K. Dey 13.5 Algorithms and Complexity in Computational Geometry -- Jianer Chen 13.6 Geometric Data Structures and Searching -- Dina Kravets 853 13.7 Computational Techniques -- Nancy M. Amato 13.8 Applications of Geometry -- W. Randolph Franklin

14. CODING THEORY AND CRYPTOLOGY

Paul C. van Oorschot

14.1 Communication Systems and Information Theory 14.2 Basics of Coding Theory 14.3 Linear Codes 14.4 Bounds for Codes 14.5 Nonlinear Codes 14.6 Convolutional Codes 14.7 Basics of Cryptography 14.8 Symmetric-Key Systems 14.9 Public-Key Systems

-- Alfred J. Menezes and

15. DISCRETE OPTIMIZATION

15.1 Linear Programming -- Beth Novick 15.2 Location Theory -- S. Louis Hakimi 15.3 Packing and Covering -- Sunil Chopra and David Simchi-Levi 15.4 Activity Nets -- S. E. Elmaghraby 15.5 Game Theory -- Michael Mesterton-Gibbons 15.6 Sperner's Lemma and Fixed Points -- Joseph R. Barr

c 2000 by CRC Press LLC

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download