Discrete Computational Structures

PrefaceAcknowledgementsChapter 1 Basic Forms and Operations 1. Introduction 2. Elements and Sets 3. Subsets 4. Venn Diagrams and Set Complements 5. Computer Representation of Sets 6. Set Operations 7. Set Algebra 8. Computer Operations on Sets 9. Product Sets 10. Relations, Mappings, Functions 11. Equivalence and Order Relations 12. The Lattice of Subsets 13. Vectors and MatricesChapter 2 Undirected Graphs 1. Graph Theory 2. Basic Definitions 3. Special Classes of Graphs 4. Matrix Representation of Graphs 5. Relations among Graph Matrices 6. Invariants and Graph Isomorphism 7. Cycle Basis 8. Maximal Complete Subgraphs 9. Storage Minimization for Matrices 10. Bandwidth of Cubic Graphs 11. Bandwidth of Bipartite Graphs 12. Planar Graphs and the Four Color Conjecture ReferencesChapter 3 Gorn Trees 1. Introduction 2. Tree Domains 3. Trees 4. Prefix Representation and Tree Forms 5. Explicit Definitions 6. Searching, Subroutines, and Theorem Proving ReferencesChapter 4 Directed Graphs 1. Introduction 2. Basic Definitions 3. Special Classes of Graphs 4. Matrix Representation of Directed Graphs 5. Flowcharts 6. Networks 7. Minimal Cost Flows 8. Pruning Branches to Find the Shortest Path 9. Critical Paths 10. Graphs of Multiprocessing Systems 11. Information Networks ReferenceChapter 5 Formal and Natural Languages 1. Introduction 2. Semigroups 3. Formal Languages 4. Backus Naur Form and Algol-Like Languages 5. Semantics of Formal Languages 6. Natural Languages ReferencesChapter 6 Finite Groups and Computing 1. Definitions of Groups and Subgroups 2. Groups of Graphs 3. Graphs of Groups 4. Generators and Relations 5. Permutations and Permutation Groups 6. Permutation GeneratorsChapter 7 Partial Orders and Lattices 1. Introduction 2. Partial Orders 3. Lattices 4. Specialized Lattices 5. Atomic Lattices ReferenceChapter 8 Boolean Algebras 1. Introduction 2. Properties of Boolean Algebras 3. Boolean Algebras and Set Algebras 4. Boolean Functions 5. Switching Circuits 6. Boolean Function Minimization 7. Computer Arithmetic ReferenceChapter 9 The Propositional Calculus 1. Introduction 2. Fundamental Definitions 3. Truth Tables 4. Well-Formed Formulas 5. Minimal Sets of Operators 6. Polish Notation 7. Proofs in Logic 8. Sets and Wordsets ReferenceChapter 10 Combinatorics 1. Introduction 2. Permutations of Objects 3. Combinations of Objects 4. Enumerators for Combinations 5. Enumerators for Permutations 6. Stirling Numbers 7. Cycle Classes of Permutations 8. Partitions and Compositions ReferencesChapter 11 Systems of Distinct Representatives 1. Introduction and History 2. The Third Question, General Case 3. The Third Question, Partition Case 4. Summary ReferencesChapter 12 Discrete Probability 1. Probabilities on a Discrete Set 2. Conditional Probability and Independence 3. Computation of Binomial Coefficients 4. Distributions 5. Random Numbers ReferenceAnswers and Hints for Selected ExercisesIndex