1 minute read

Combinatorics

Trees

Trees are yet another type of graph. Trees have all the properties of graphs except they must be connected with no cycles. A computer's hard drive directory structure is set up as a tree, with subdirectories branching out from a single root directory. Typically trees have a vertex labeled as the root vertex from which every other vertex can be reached from a unique path along the edges. Not all vertices can be a root vertex. Trees come into importance for devising searching algorithms.


Resources

Books

Berman, Gerald, and K.D. Fryer. Introduction to Combinatorics. Academic Press, 1972.

Bogard, Kenneth P. Introductory Combinatorics. Harcourt Brace Jovanovic Incorporated, 1990.

Bose R.C., and B. Manvel. Introduction to Combinatorial Theory. John Wiley & Sons, 1984.

Jackson, Bradley, and Dmitri Thoro. Applied Combinatorics with Problem Solving. Addison-Wesley, 1990.

Trudeau, Richard J. Introduction to Graph Theory. Dover, 1993.


David Gorsich

KEY TERMS

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

Binomial coefficients

—Numbers that stand for the number of subsets of equal size within a larger set.

Combinatorics

—The branch of mathematics concerned with the study of combining objects (arranging) by various rules to create new arrangements of objects.

Cycles

—A graph has a cycle if there is a path from a vertex back to itself where no edge is passed over twice. The triangle has one cycle.

Enumeration

—The methods of counting objects and arrangements.

Equivalence relations

—A way to relate two objects which must abide by the reflexive, symmetric and transitive laws.

Factorial

—An operation represented by the symbol!. The term n! is equal to multiplying n by all of the positive whole number integers that are less than it.

Graph

—A graph is a finite set of vertices or points and a set of finite edges.

Königsberg Bridge Problem

—A common question in the Königsberg town on how to travel through the city and over all the bridges without crossing one twice.

Network

—A term used in graph theory to mean a graph with directions and weights assigned to each edge.

Permutations

—Changing the order of objects in a particular arrangement.

Recurrence relation

—A means of generating a sequence of numbers by using one or more previous numbers of the sequence and multiplying or adding terms in a repetitive way. Recurrence relations are especially important for computer algorithms.

Trees

—Graphs which have no cycles.

Additional topics

Science EncyclopediaScience & Philosophy: Cluster compound to ConcupiscenceCombinatorics - History Of Combinatorics, Enumeration, Binomial Coefficients, Equivalence Relations, Recurrence Relations, Graph Theory