Skip to main content
Logo image

Applied Discrete Structures

Index Index

Abelian Group, Definition
a Limerick, Poem
Adjacency Matrix, Definition
adjacency matrix
a Limerick, Poem
Adjacency Matrix Method, Subsection
Algebraic Systems, Section
algorithm
a Limerick, Poem
Alternating Group, Definition
Alternating group
a Limerick, Poem
Analog-to-digital Conversion, Example
Antisymmetric Relation, Definition
Associative Property, Definition
Atom of a Boolean Algebra, Definition
augmented matrix
a Limerick, Poem
Automata, Section
Automorphism
Inner, Exercise
Basic Law Of Addition:, Theorem
Basic Set Operations, Section
Basis, Definition
Biconditional Proposition, Definition
Bijection, Definition
Binary Conversion Algorithm, Algorithm
Binary Operation., Definition
Binary Representation, Section
Binary Search, Subsection
Binary Tree, Definition
Binary Trees, Section
Binomial Coefficient, Definition
Recursive Definition, Definition
Binomial Coefficient Formula, Theorem
Binomial Theorem, The, Theorem
Bipartite Graph., Definition
Bipartitie
a Limerick, Poem
Bit, Glossary
Boolean Algebra, Definition
Boolean Algebras, Section
Boolean Arithmetic, Definition
Boolean Expression, Definition
Boolean Expressions, Section
Bounded Lattice, Definition
Breadth-First Search, Subsection
Breadth-first Search, Algorithm
Bridge, Definition
Bubble Sort, Subsection
Byte, Glossary
Bézout’s lemma, Theorem
Cancellation in Groups, Theorem
Cardinality., Definition
Cartesian Product, Definition
Center of a Graph, Item
Center of a graph, Item
Characteristic Equation, Definition
Characteristic function, Exercise
Characteristic Polynomial, Example
Characteristic Roots, Definition
Child
of a Root, Definition
Chinese Remainder Theorem, Theorem
Chromatic Number, Definition
Closed Form Expression., Definition
Closest Neighbor Algorithm, Algorithm
Closure Property, Definition
Code
Polynomial, Example
Codes
Linear, Section
Coding Theory, Section
Cofactor, Definition
Combinations, Subsection
Commutative Property, Definition
Complement of a Lattice Element, Definition
as an operation, Definition
Complement of a set, Definition
Complemented Lattice, Definition
Complete Undirected Graph., Definition
Complex Number, Glossary
Composite Integer, Glossary
Composition of Functions, Definition
Composition of Relations, Definition
Concatenation, Definition
Conditional Statement, Definition
Congruence Modulo \(n\), Definition
Conjunction, Logical, Definition
Connected Component, Definition
Connectivity in Graphs, Section
Constant, Glossary
Contradiction, Definition
Contrapositive, Definition
Converse, Definition
Coset, Definition
Coset Counting Formula, Corollary
Coset Representative, Definition
Cosets
Operation on, Definition
Cosets and Factor Groups, Section
Countable Set, Definition
Counting Binary Trees, Subsection
covering relation, Definition
Creative Commons, Glossary
Cycle, Definition
Cycle Notation, Subsection
Cyclic Group, Definition Definition
Cyclic Subgroup, Definition
Data Structure, Glossary
Degree, Definition
Degree Sequence of a Graph, Definition
Derangement, Subsection
Detachment, Table
Determinant, Definition
\(1 \times 1\) and a \(2 \times 2\) cases, Definition
diagonal matrix
a Limerick, Poem
Diagonalizable Matrix, Definition
Diagonalization Process, The, Section
Diameter of a Graph, Item
Digraph, Paragraph
Dihedral Group, Subsection
Definition, Definition
Dimension of a Vector Space, Definition
Direct Product, Definition
of Two Groups, Definition
Direct Products, Section
Direct proof, Example
Directed Graph, Definition
Directed graph, Paragraph
Disjoint Cycles, Note
Disjoint Sets, Definition
Disjunction, Logical, Definition
Distinct, Glossary
Distributive Lattice, Definition
Distributive Property, Definition
Divides, Definition
Division Property for Integers, Theorem
Division Property for Polynomials, Theorem
Divisors of an Integer, Definition
Doyle, Chris, Poem Poem
Duality for Boolean Algebras, Definition
Eccentricity of a vertex, Item
Egg, Bob, Poem
Eigenvalue, Definition
Eigenvector, Definition
Elementary Operations on Equations, Theorem
Elementary Row Operations, Theorem
Embedding of a graph, Paragraph
Empty Graph, Note
Empty set, Paragraph
empty set
a Limerick, Poem
Equivalence, Definition
Equivalence Classes, Definition
Equivalence Relation, Definition
Equivalence Relations, Subsection
Euclidean Algorithm, The, Subsection
Euler, Leonhard, Subsection
Eulerian Paths, Circuits, Graphs, Definition
Euler’s Formula, Theorem
Euler’s Theorem, Theorem
Koenigsberg Case, Theorem
Even Integer, Glossary
Existential Quantifier, Definition
Exponentiation in Groups, Definition
Expression Tree, Subsection
Extended Rule Of Products, The, Theorem
Factor, Glossary
Factor Group, Definition
Factor Theorem, Theorem
Factorial, Definition
Fibonacci Sequence, Example
Matrix Representation, Example
Fibonacci sequence
a Limerick, Poem
Field, Definition
field extension
a Limerick, Poem
Finite-State Machine, Definition
Finite-State Machines, Section
Five-Color Theorem, Theorem
Flow Augmenting Path, Definition
Forest., Definition
Formal Language, Definition
formal logic
a Limerick, Poem
Four-Color Theorem, Theorem
Frankovich, Jesse, Poem
Free Monoids and Languages, Section
Full binary tree, List Item
Function, Definition
Bijective, Definition
Composition, Definition
Equality, Definition
Injective, Definition
One-to-one, Definition
Onto, Definition
Surjective, Definition
Functions
Of two Variables, Subsection
Functions Between Two Sets
Set of, Definition
Fundamental Theorem of Group Homomorphisms, Theorem
Gauss-Jordan Algorithm, Algorithm
genealogical terms, List
Generalized Set Operations, Definition
Generate, Definition
Generating Function, Definition
Generating Functions, Section
Closed form expressions for, Subsection
Operations on, Subsection Definition
Generation Problem, Problem
Generator, Definition
George Boole
a Limerick, Poem
Glossary, Glossary
Goldie, Poem Poem
Graph
Data Structures, Section
Multigraph, Definition
Simple Directed, Definition
Simple Undirected, Definition
Graph Coloring, Definition
Graph Optimization, Section
Graphic Sequence, Definition
Gray Code, Example
Gray Code Decoder, Exercise
Greatest Common Divisor (\(\gcd\)), Definition
Greatest Element, Definition
Greatest Lower Bound, Definition
Group, Definition
Hamiltonian Paths, Circuits, and Graphs, Definition
Hamming Distance, Definition
Hasse Diagram, Paragraph
Homogeneous Recurrence Relation., Definition
Homomorphism, Definition
Group, Section
Howlett,Chris, Poem
Idempotent Property, Definition
Identity Function, Definition
Identity Matrix, Definition
Identity Property, Definition
Iff, Glossary
Image of an Element., Definition
Implication, Definition
Improper subset, Paragraph
Inclusion-Exclusion, Laws of, Theorem
Indirect proof, Paragraph
Indirect Reasoning, Table
Induced Subgraph, Definition
Induction and Recursion, Subsection
Injection, Definition
Integer, Glossary
Integers Modulo \(n\)
Additive Group, Definition
Multiplicative Group, Definition
Integral Domain, Definition
Intersection, Definition
Inverse
Logical, Definition
Matrix, Definition
Inverse Function
of a function on a set, Definition
Inverse Property, Definition
Involution Property, Definition
Irrational Number, Glossary
Irreducibility of a Polynomial, Definition
Isomorphic Graphs, Definition
Isomorphism
Group, Definition
Isomorphisms, Section
Join, Definition
Karnaugh map, Paragraph
Kernel, Definition
kernel of a function, Exercise
Kruskal’s Algorithm, Algorithm
Lagrange’s Theorem, Theorem
LaTeX, Glossary
Lattice, Definition
Lattice Paths, Exercise
Lattices, Section
Laws of Matrix Algebra, Section
Leaf of a binary tree, Item
Leaf, of a binary tree, Item
Least Element, Definition
Least Upper Bound, Definition
Left Distributive Property, Definition
Level of a vertex, Paragraph
Levels of Abstraction, Subsection
Limerick
countably infinite, Poem
Enumerative Combinatorics, Poem
Linear Code, Paragraph
Linear Combination., Definition
Linear Dependence, Definition
Linear Equations
over the Integers Mod 2, Section
Linear Equations in a Group, Theorem
Linear Independence, Definition
Logarithm
General Base, Definition
Logarithm, base 2, Definition
Logarithms, Subsubsection
Properties, Theorem
Logic Design, Section
Lower Bound, Definition
Machine of a Monoid, Section Definition
Many Faces of Recursion, The, Section
Matrix Addition, Definition
Matrix Inversion, Section
Matrix Multiplication, Definition
Matrix Oddities, Section
Maximal flow, Paragraph
Meet, Definition
Merge Sort, Subsection
Mesh Graph, Exercise
Minimal Spanning Tree, Definition
Minimum Diameter Spanning Tree, Definition
Minor, Definition
Minset, Definition
Minset Normal Form, Definition
Minterm, Definition
Minterm Normal Form, Definition
Modular Addition, Definition
Modular Arithmetic, Subsection
Properties, Subsection
Modular Multiplication, Definition
Modus Ponens
see Detachment, Table
Modus Tollens
see Indirect Reasoning, Table
Monoid, Definition
of a Finite-State Machine, Section
Monoids, Section
Multigraph, Definition
Multiple Pop and Push, Definition
Multiples, Glossary
Multiplicative Inverses, Definition
N-cube, Definition
Natural Homomorphism, Definition
Natural Numbers, Glossary
Negation, Logical, Definition
Network, Definition
Networks, Subsection
Ngai, Steve, Poem
Nonhomogeneous of Finite Order Linear Relations
Solution, Subsection
Nonnegative Number, Glossary
Normal Subgroup., Definition
Normal Subgroups, Section Subsection
Odd Integer, Glossary
Operation Tables, Subsection
Operations, Section
Order
of elements of a finite cyclic group, Theorem
Order of a Group Element, Definition
Order of a Recurrence Relation, Definition
Order Sequence, Definition
Ordering Diagram, Paragraph
Oslan, Steven, Item
Parent of a vertex, Definition
Partial Ordering, Definition Definition
Partially ordered set, Definition
Partition, Definition
of a group by cosets, Theorem
Path Graph, Definition
Perfect Codes, Exercise
Permutation, Definition Definition
Permutation Counting Formula, Theorem
Permutation Groups, Section
Permutations
Composition, Note
Phrase Structure Grammar, Definition
Pigeonhole Principle, Theorem
Planar Graph, Definition
Plane Graph, Definition
Polynomial
Irreducible, Definition
Polynomial Addition, Definition
Polynomial Code, Example
Polynomial Expression
Non-recursive)., Definition
Recursive definition, Definition
Polynomial Multiplication, Definition
Polynomial over a Ring, Definition
Polynomial Units, Theorem
Polynomials, Subsection
Polynomials and their evaluation, Subsection
Poset, Definition
Posets Revisited, Section
Positive Number, Glossary
Power Series, Definition
Power Series Units, Theorem
Power Set, Definition
Power Set Cardinality Theorem, Theorem
Powers, Glossary
Powers of Functions, Definition
PreTeXt, Glossary
Prime, Glossary
Prime number, Paragraph
Prim’s Algorithm, Algorithm
Products
Extended Rule of, Theorem
Rule of, Theorem
Proper subset, Paragraph
Properties of Functions, Section
Properties of Operations, Subsection
Proposition, Definition
Propp, Jim, Paragraph
psheil, Poem
Quantifiers, Section
Multiple, Subsection
Negation, Subsection
Queue, Glossary
Radius of a graph, Item
Range of a Function., Definition
Rational Number, Glossary
Real Number, Glossary
Recognition Problem, Problem
Rectangular codes, Exercise
Recurrence Relation, Definition
Recurrence Relations
Solving, Subsection
Recurrence Relations Obtained from “Solutions”, Subsection
Recursive Language, Definition
Recursive Searching, Subsection
Reducible Polynomial, Definition
References, References
Reflexive Relation, Definition
Regular Grammar, Definition
Relation, Definition
Relation Notation, Paragraph
Relation on a Set, Definition
Relatively Prime, Definition
Right Distributive Property, Definition
Ring, Definition
Commutative, Definition
Ring Isomorphism., Definition
Ring with unity, Definition
Robinson, Andrew, Poem
Rooted Tree, Definition
Rooted Trees, Section
Row Equivalent Matrices, Definition
Rule Of Products, The, Theorem
SageMath, Glossary
SageMath Note
bridge hands, Subsection
Cartesian Products and Power Sets, Subsection
Functions, Subsection
Graphs, Subsection
Kruskal’s Algorithm, Subsection
Matrix Diagonalization, Subsection
Matrix Exponential, Subsection
Matrix Reduction, Subsection
Modular Arithmetic, Subsection
Power Series, Subsection
Search in a Graph, Subsection
Sets, Subsection
Scalar Multiplication, Definition
Sequence, Definition
Sequences, Section
Operations on, Definition
Recursively Defined, Subsection
Set of Functions Between Two Sets, Definition
Set-Builder Notation, Paragraph
Sheffer Stroke, Definition
SheilaB, Poem
Simple Undirected Graph, Definition
Solution Set, Definition
solutions, Appendix
Some General Properties of Groups, Section
Span, Definition
Spanning Subgraph, Definition
Spanning Tree, Definition
Spanning Trees, Section
Spindel, Howard, Poem
Strings over an Alphabet, Definition
STT. See Sun Tzu’s Theorem
Subgraph, Definition
Subgroup, Item
Conditions, Theorem
Submonoid
Generated by a Set, Definition
Subsystem, Definition
Subsystems, Section
Subtraction, Glossary
Summation Notation and Generalizations, Section
Sun Tzu’s Theorem, Theorem
Surjection, Definition
Switching Theory, Section
Symmetric Difference, Definition
Symmetric Group, Definition
Symmetric Relation, Definition
Syndrome, Example
Systems of Linear Equations, Section
Tautology, Definition
Term, Glossary
Three Utilities Puzzle, Paragraph
Tournament Graph, Definition
Transitive Closure, Definition
Transitive Relation, Definition
Transposition, Definition
Traveling Salesman Problem, The, Subsection
Traversals of Binary Trees, Subsection
Traversals of Graphs, Section
Tree, Definition
Triple Repetition Code, Example
Truth Set, Definition
Unary Operation., Definition
Union, Definition
Unique, Glossary
Units
of a ring, Definition
of Polynomial Rings, Theorem
of Power Series Rings, Theorem
Unity of a Ring, Definition
Universal Quantifier, Definition
Universe, Definition
Upper Bound, Definition
Value of a Flow, Definition
Variable, Glossary
Vector Space, Definition
Vector Spaces, Section
Venn, John, Subsection
Weighted Graph, Definition
What Is a Tree?, Section
XOR linked list, Example
Zero Divisor, Definition
zqms, Poem