Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

INDEX 473

Regular:
expression, 305
grammar, 306
graph, 163
language, 306
Relation, 23–25
Relative:
complement, 6
frequency, 123
Relatively prime, 273, 449
Remainder, 268, 447
function, 48
Theorem, 447
Repeated trials, 130
Residue system, 275
Ring, 443
of polynomials, 444
with identity element
1, 444
Root:
of a binary tree, 235
of a polynomial, 447
Rooted trees, 204
ordered, 205
Row (of a matrix), 410
canonical form, 418
equivalence, 418
operations (elementary),
417

Sample:
mean, 136
space, 123
Scalar, 409
multiplication, 410, 411
Schroeder-Bernstein Theorem,
56
Search:
breadth first, 176, 215
depth-first, 173, 214
linear, 58
Search tree, binary, 243
Semigroup, 304, 435
product, 438
Sequences, 50
Fibonacci, 54, 115
Sets, 1
Short-lex order, 339
Shortest path, 162
algorithm, 216
Similar:
binary trees, 236
ordered sets, 344
Simple:
directed graph, 206
graph, 157
path, 159
Sink, 203

Size of a natrix, 411

Sort, topological, 217

Source, 203

Spanning tree, 164

path, 203

Sparse, 171, 206

Special sequences, 381

Square matrices, 414

Stabilizer, 455

Stack, 155

Standard deviation, 134

Star graph, 168

Start symbols, 310

State,

diagram, 307, 329

table, 324

Strings, 303

Strong, 204

Strongly connected, 208

Subgroup, 440

normal, 440

Subsemigroup, 435

Subset, 2

proper, 3

Substitution, Principle of, 74

Subword, 304

Succeeds, 332

Success, 131

Successor, 201

list, 201

Sum rule, 88

Sum-of-products, 372

Summation symbol,51

Sums of random variables,

132

Supremum (sup), 342

Surjective function, 46

Syllogism, Law of, 77

Symmetries, group of, 455

Symmetric:

difference, 6

group Sn, 439

relation, 33

Synthetic division, 56, 448

Tables, truth, 73

Tape (Turing machine), 324

expression, 327

output, 324

Tautology, 74

Terminal node, 235

Ternary relation, 33

Top of a stack, 155

Topological sort, 217

Trace of a matrix, 414

Trail, 160

Euletrian, 160

traversable, 195

Transfinite induction, 346

Transitive relation, 29

closure of, 31

Transpose of a matrix, 414

Traveling salesman problem,

186

Traversable multigraph, 160

Traversal of binary trees,

240

Tree, 164

binary, 235

spanning, 164

2-tree, 237

Triangular form, 418

Trichotomy, law of, 265

Trivial graph, 158

Truth:

set, 77

tables, 73

values, 70

Turing machine, 314, 329

Types of grammars, 312

UFD (unique factorization

domain), 445

Unary operation, 432

Uncountable set, 8

Unilaterally connected, 204

Union of sets, 4

Unique factorization domain,

445

Unit, 368, 445

matrix In, 414

Unity (identity) element in a ring,

444

Universal:

address system, 205

quantifiers, 78

setU,3

Unordered partition, 108

Upper bound, 348

Usual order, 338

Utility graph, 168

V(G) (vertices of a graph),

201

Valid arguments, 76

Variable, 43, 310

random, 132

Variance, 134

Var(X) (variance), 134

Vectors, 409

Venn diagram, 3

Vertex, 156, 201

coloring, 168

file, 168, 212

isolated, 160