DMP: Definitions


This is a tentative, and growing list of definitions, taken from various sources on Discrete Mathematics. Sources include:

A page by a student in a University of Oregon Discrete Math class has its own Terms Index page.

The Graph Theory Tutorial has a Graph Theory Glossary of its own.

A glossary of mathematical terms used in the Colorado Model Content Standards for Mathematics lists some general mathematics terms that are important for mathematics educators.

Please send corrections, comments, additions to Dominic Peressini .
Last updated January 19, 1997.

index Definitions: A

Absorbing State
Addition Principle
Adjacent Vertices, Adjacency Matrix
Two vertices in a graph are said to be adjacent if they are connected directly by an edge.

An adjacency matrix is a means of representing a graph in the form of a matrix. In the adjacency matrix, both the rows and columns represent the vertices. If If two vertices are adjacent, then a 1 is place in the corresponding position in the matrix, otherwise a zsero appears. Note the this applies to a simple graph, where there are no multiple edges connecting different vertices, nor any loops. In the case of such multigaphs, the entries of the matrix will be integers larger than one. If the graph is not a digraph, the adjacency matrix will be symmetric.

A graph       The corresponding
adjacency matrix
In essence, an algorithm is a sequence of instructions that, if followed for an operation (whether mathematical or not), will always lead to a result. [NCTM 1991 Yearbook, p.25]
Apportionment deals with the issue of dividing items of value among a group of people who desire them. Apportionment may include division of discrete objects, as in the division of seats of a representative government among districts, or may involve division of continuous objects such as dividing a cake among a group of people. In addition, topics such as estate division combine division of both discrete and continuous objects. Apportionment represents an aspect of both fair division as well as an aspect of election theory.
Apportionment Algorithms
Various apportioment algorithms are used to allocate seats in a representative government system. The need for apportionment algorithms arise when the number of seats given to each group (possibly states, or student classes) can not exactly represent their relative sizes in terms of the ideal ratio. Apportionment algorithms include the Hamilton method, the Hill method, the Jefferson method and the Webster method.

In addition, various apportionment algorithms are used for dividing estates as well as continuous objects, such as cakes using the cut and choose method.

Approval Voting
In approval voting, you may vote for as many choices as you like, but you do not rank them. You mark all those of which you approve. Approval voting violates Arrow's criteria less than any other known method. [refcomap, p.29]
Arithmetic Series
Arrow's Conditions, Arrow's Criteria and Arrow's Paradox
Arrow's conditions (or criteria) are a list of five conditions which Kenneth Arrow selected as necessary for a fair determination of a group ranking. These conditions are:
  1. Nondictatorship: The preferences of a single individual should not become the group ranking without considering the other individuals' preferences.
  2. Individual sovreignty: Each individual is allowed to order the choices in any way and can indicate ties.
  3. Unanimity: If every individual prefers one choice to another, the group ranking should do the same.
  4. Freedom from irrelevant alternatives: The group ranking between any pair of choices does not depend on the individuals' preferences for the remaining choices.
  5. Uniqueness of the group ranking: The method of producing the group ranking should give the same result whenever it is applied to a given set of preferences. The group ranking must also be transitive.
Arrow's paradox (otherwise known as Arrow's Impossibility Theorem states that given such a set of restrictions, no fair group-ranking can be found.[refcomap, pp.27-29]

index Definitions: B

Binary Tree
A binary tree is a tree in which each vertex has at most two children.
Binomial Distribution
Binomial Theorem
For all possible integers n and numbers x and y,
binomial theorem
or, equivalently,
binomial theorem 2
[Precalculus and Discrete Mathematics, UCSMP, p. 612]
Borda Count, Borda Method
The Borda method is a group ranking method which assigns weights to individual preference schedules by giving a number of points for each first place vote another number for each second place vote and so on. The most common way of assigning values in a group ranking of n choices is to assign n points to first place, n-1 points to second, and so on. The group ranking is determined by totalling each choice's points.[refcomap, p10]
The Borda method is common in sports polls, such as the AP's poll for college football.

index Definitions: C

Child, Children
A child of a vertex (called the parent) is an adjacent vertex one level lower on the tree. See tree.
Chromatic Number
The chromatic number of a graph is the minimum number of colors needed to color the graph.
A circuit is a path which begins and ends at the same vertex. Note that a circuit does not necessarily have to pass by every vertex or edge, nor is a circuit restricted to passing vertices and edges only once. Compare with a cycle.
Closed Form Solution
Cobweb Diagram, Cobweb Graph
See graph coloring.
A situation in which the order of selecting various items does not matter. The combination of n things taken m at a time is written formally as C(n,m) or nCm or nCm. In general, C(n,m) is calculated by evaluating the expression P(n,m)/m!, But P(m,n) = n!/(n-m)!, so combination. [DMTA, p 285]
Common Difference
Common Ratio
Complete Graph
A complete graph is a graph where each vertex is connected to every other with a single edge.
Conditional Probability
A conditional probability is the probability of one event occurring given that another event has already occurred. For instance, if we are rolling two dice, the probability that their sum will be grater than seven is 11/36 (since of the 36 possible rolls, 11 are eight or greater), however the conditional probability that their sum will be greater than seven given that the first die rolled is a 4 is 2/6 or 1/2 (since we must roll a five or a six). [DMTA p. 295, Ross,An Introduction to Probability]
Condorcet Method, Condorcet Paradox
The Condorcet method is a means of determining a winner of an election using group rankings. Condorcet's method requires that the winning choice be able to defeat each of the other choice in a one-on-one contest. Unfortunately, for a given a set of preference schedules, it may be impossible to generate a Condorcet winner.
voting schedule What this means is that in a set of head-to-head elections, it would be possible for choice A to beat choice B, choice B would beat choice C, yet choice C would beat choice A. This represents the Condorcet paradox. For instance, in this set of preference schedules, A would beat B by 10 votes to 9, B would beat C by ten votes to nine yet C would beat A by ten votes to nine as well!
Continuous Mathematics
A branch of mathematics which deals with problems that are based on a continuous set of numbers. As opposed to discrete mathematics.
Counting Problems, Counting Techniques
A category of discrete mathematics which investigates how many solutions exist for problems with known solutions.
Critical Path
When a graph is used to model project scheduling, the critical path is a path from the start to the finish which passes through all of the tasks which are critical to completing the project in the shortest amount of time.[refcomap, p.158]
Cut and Choose Method
A cycle is a path that begins and ends at the same vertex and does not use any edge or vertex more than once. Note that a cycle is necessarily a curcuit but a curcuit is not necessarily a cycle. [DMTA, p 196]

index Definitions: D

In a graph, the degree of a vertex is the number of edges which have that vertex as an endpoint.[refcomap, p.170]
See directed graph.
The dimenstion of a square matrix is the number of rows (or columns in that matrix.
Directed Graph
A directed graph is a graph which has edges which can only be traversed in one direction.[refcomap, p.177]

A directed graph
Discrete Mathematics
Discrete mathematics problems can be classified in three broad categories, existence problems, counting problems and optimization problems. [NCTM 1991 Yearbook, p.1-2]

index Definitions: E

Earliest Start Time
The earliest start time (EST) is the earliest that an activity can begin if all the activities preceding it begin as early as possible.[refcomap, p.158]
An edge connects a pair of vertices. See graph.
Election Theory
Branch of social decision making which deals with making decisions based on preferences of a group of individuals.
See earliest start time.
Estate Division
Estate division is a category of fair division which deals with determining a fair method for dividing an estate among a number heirs.
Euler Circuit
An Euler circuit is a circuit which traverses each edge of a graph exactly once. (Since this is a circuit, it must start and end at the same vertex.)
Euler Path
An Euler path is a path which traverses each edge of a graph exactly once. (Since this is a path, the route need not start and end at the same vertex.)
Existence Problems
A category of discrete mathematics which deals with whether a given problem has a solution or not. [NCTM 1991 Yearbook, p.2]
Expectation, Expected Value

index Definitions: F

Fair Division, Fairness
Fair division deals with dividing an object among a number of people in such a way as to treat each person fairly. Fair division issues include topics such as apportionment, divide continuous items such as food, or estate division. In the continuous case, we call a division among n people fair if each person feels that he or she has received at least 1/nth of the object. [DMTA, p77]
Fibonacci Sequence
Finite Differences, Finite Difference Method
Four Color Theorem
The Four Color Theorem, proved in 1976 by Appel and Haken, states that all planar graphs can be colored with only four colors.[reftucker, p.30]
Fundamental Counting Theorem

index Definitions: G

Game Theory
Geometric Series
Informally, a graph consists of a finite set of vertices and edges which connect them. Graphs are usually depicted pictorially as a set of points representing the vertices with lines (usually straight, but not necessarily so) connecting them to represent the edges. Types of graphs are: simple, directed or digraphs, multigraphs or planar.

A Graph
Golden Ratio
Graph Coloring
Graph coloring consists of of assigning colors to the vertices of a graph so that adjacent vertices are given different colors.[reftucker, p.66]
Group Ranking
A group ranking is a determination of the preferences of a group towards a set of choices. Often the preferences of the individuals are represented in the form of preference schedules. Some group ranking methods include the Borda method, the Condorcet Method or plurality and sequential runoff winners, among others.

index Definitions: H

Hamilton Method
The Hamilton method is an apportionment algorithm which assigns additional representative seats based on looking at the decimal portion of the quotas for the various groups. The group with the largest decimal remainder to their qouta is given the first additional extra seat.
Hamiltonian cycle, path or curcuit
In a graph a Hamiltonian path is a path that contains each vertex once and only once. A Hamiltonian cycle is a cycle that includes each vertex. [Dossey, p. 108]
Hill Method of Apportionment
The Hill method is an apportionment algorithm which is used to assign seats in a representative body. The Hill method requires adjusting the ideal ratio until the quota of one of the groups exceeds the geometric mean of two consecutive integers. While seemingly complicated, the only difference between the the Hill method, the Jefferson method and the Webster method is how the quotas are rounded.

index Definitions: I

Ideal Ratio</>
When representative seats are being apportioned amongst various groups, the ideal ratio represents the number of people each seat should ideally represent. For example, if the total population of a school is 400 and there are 20 voting seats in a student council, then each seat should ideally represent 20 students. Usually, however, it is impossible to allocate the seats in such a manner so that each group has the ideal number of seats represented so one of various apportionment algorithms must be implemented.
Independent Random Events
Two events A and B are said to be independent if the probability of both events occurring is the same as the product of each of the events occurring on their own. Symbolically,
Initial State Matrix
Insincere Voting
Insincere voting occurs when people vote differently than the way they actually feel. Insincere voting usually occurs when people have some knowledge beforehand of the possible outcomes of an election. Insincere voting has been seeen in plurality elections, such as three-party presidential elections as well as sports ranking polls, such as the AP football poll.

index Definitions: J

Jefferson Method
The Jefferson method is an apportionment algoritm which assigns representative seats by decreasing the ideal ratio until the quota for one of the groups exceeds an integer value. This group is then given that number of seats.

index Definitions: K

index Definitions: L

Latest Start Time
In a project scheduling situation, the latest that a task can begin without delaying the project's completion is known as the latest start time (LST) for the task.[refcomap, p.164]
Leaf, leaves
A leaf is a vertex in a tree which has no children.
Leontif Input-Output Model
Leontif Population Model
In a graph, a loop is an edge which connects a vertex to itself. See multigraph.
See latest start time.

index Definitions: M

Majority Winner
A choice which is placed first on over half of a group's preference schedules is the majority winner of that group's election.
Markov Chain
A multigraph is a graph in which there are multiple edges connecting the same pair of vertices. If an edge connects a vertex to itself, then that edge forms a loop.

A Multigraph
Multiplication Principle
The multiplication principle states that if events A and B can occur in a and b ways, respectively, then events A and B can occur together in a times b ways.
The word and in the description of an event often indicates that the multiplication principle should be used. [DMTA, p. 272-3]
Mutually Exclusive

index Definitions: N

Nearest Neighbor Algorithm
The nearest neighbor algorithm is a method for solving the traveling salesperson problem. The algorithm requires following a path which always travels along the edge with the lowest weight connecting the current vertex to another which has not yet been visited. Note that the nearest neighbor algorithm will find a circuit, however, there is no guarantee that this solution will represent the minimal possible route.
Network, Networking

index Definitions: O

The odds of an event occuring is the ratio of the probability of that event occurring to the probability of the event not occuring. Note that this is significantly different from just the probability of the event occurring. For example, the probability of rolling a six on one fair die is 1/6, however, the odds of rolling a six is 1:5.
Optimization Problems
A category of discrete mathematics which focuses on finding a best solution for a particular problem. [NCTM 1991 Yearbook, p.2]

index Definitions: P

Pascal's Triangle
Pascal's triangle is an array of numbers that is constructed by beginning with a row of two ones: 1   1. Each new row after the starts and ends with a one, and the other numbers are formed by adding the numbers above and on either side of them:

[DMTA, p. 322, Precalculus and Discrete Mathematics, UCSMP, p. 610]
A path is a sequence of adjacent vertices. In other words, a path is a route through a graph which travels along the edges from vertex to vertex. If a path starts and ends at the same vertex, then it is a circuit.
Payoff Matrix
A situation in which order matters. In general, the number of permutations of n things taken m at a time is denoted asP(n,m) and is calculated by evaluating the expression

[DMTA, p. 275]
Planar Graph
A planar graph is a graph which can be drawn in the plane with no edges crossing.
Plurality Winner
In a election, the choice which receives the most first place votes is determined to be the plurality winner.
Power Index
In a situation where weighted voting is used, the number of winning coalitions to which a group is essential is that group's power index.
Preference Schedule
A list of alternatives and individual rankings, sometimes presented as a graph with higher-ranked preferences listed above lower-ranked ones. For instance, this preference schedule indicates that the individual prefers option E best, followed by option C, then A, then B. Option D would be this individual's least preferred choice.
In a project scheduling situation, any tasks which must be completed before a given task can be started are that task's prerequisites.
When an event can occur in a finite number of discrete outcomes, the probability of an event is the ratio of the number of ways in which the event can occur to the total number of possibilities, assuming that each of them is equally likely.

index Definitions: Q

In a representative body, the quota is defined as the ratio of the size of the popluation of a group being represented to the ideal ratio. The quota represents the ideal number of representatives that that specific group should have.

index Definitions: R

Recurrence Relation
A root of a tree is the vertex in a tree such that there is a uniques route from the root to any other vertex in the tree. In a digraph, if a root exists, it is unique. If the tree is undirected, the any vertex can be a root.[reftucker, p.80]
Row Minimum
Row Maximum
Runoff Elections
In a runoff election, all choices but the two receiving the most votes are eliminated and then these two choices are again voted upon by the group. In terms of a typical election, this would require that the population vote twice, once for the initial decidion of which two choices would run off, and then again to determine the winner. Using preference schedules, we can model both votes by examining which two choices receive the most first place votes and then comparing the head-to-head preferences of the group for those two choices. See the sequential runoff method.

index Definitions: S

Sequential Runoff
A sequential runoff election is similar to a basic runoff election except that instead of eliminating all choices but two and then deciding between those two, choices are eliminated one at a time, starting with the one that receives the least number of first place votes.
Shortest Path Algorithm
The shortest path algorithm is a method for finding the shortest route from one vertex to another in a weighted graph.The shortest path algorithm requires extending a tree from the starting vertex until it reaches the finishing vertex. At each step, the tree is extended in a direction such that the new leaf is at the shortest possible distance from the root.
Simple Graph
A simple graph is a graph which is not a multigraph. In other words, a simple graph is a graph which has at most one edge connecting each pair of vertices.
Social Decision Making
Social Decision Making includes the topics of Election Theory, Fair Division and Apportionment.
Spanning Tree
A spanning tree is a tree which is a subgraph of a graph which contains all of the vertices of the graph.
Stable State
A subgraph is of a graph is itself a graph in which all of the edges and vertices are contained within the original graph.[refcomap, p.212]

index Definitions: T

Task Table
A task table is a list of tasks, the time needed to complete them and the prerequisite tasks which must be completed before each can be started. A task table is used to organize information in a project scheduling situation.
Transition Matrix
Traveling Salesperson Problem
"The Traveling Salesperson Problem calls for a minimal-cost Hamilton circuit in a complete graph having an associated cost matrix C. Entry cij in C is the cost of using the edge from the ith vertex to the jth vertex. Minimal-cost means minimizing the sum of the costs of the edges." [Tucker, Applied Combinatorics, p. 97]
In other words, given a complete graph with weighted edges, the Traveling Salesperson Problem asks for the shortest route which visits all of the edges.
A tree is a graph which contains no cycles. We can visualize a tree by drawing it with a root at the top with the vertices below leading to the leaves at the lowest. If the vertices are placed on levels, higher level vertices are referred to the parents of the vertices directly below them, while the lower vertices are similarly referred to as their children.

A Tree

index Definitions: U

index Definitions: V

Venn Diagram
See graph. Informally, a vertex is located at the end of an edge and is usually represented pictorially by a dot.

index Definitions: W

Webster Method
The Webster method is an apportionment algorithm used to determine how seats in a representative body are assigned to various groups. The Webster method involves decreasing the ideal ratio until the quota of one of the groups passes the arithmetic mean of two consecutive integers (or, in other words, until the quota rounds up instead of down.)
Weighted Digraph
A weighted digraph is a weighted graph which is also a directed graph.
Weighted Graph
A weighted graph is a graph in which a number (often representing a distance) is assigned to each edge.
Weighted Voting
Weighted voting occurs when different numbers of votes are allotted to different members of a voting body. This can occur when voting members represent a group of people, such as on a school's student council where each representative is given a different number of votes depending on the size of the class that they represent.
Winning Coalition
A winning coalition is a collection of representatives voting under a weighted voting scheme which together has enough votes to pass an issue.[refcomap, p.34]

index Definitions: X

index Definitions: Y

index Definitions: Z

Zero Sum Game