Glossary

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

A

Adjacent
Two vertices are adjacent in a graph G = (V, E) if there exists an edge (a, b) in E. See Incident
Archimedes Principle
If two weights balance, then the following equation holds:
w1d1 = w2d2

B

Bipartite
A graph is bipartite if its vertices can be partitioned into two disjoint subsets U and V such that every edge connects a vertex from U to one from V.

C

cardinality
A more formal way to describe the "size" of a set. For a finite set, the cardinality is the number of elements in the set. For an infinite set, the cardinality is one of a small number of "transfinite cardinals" called alephs; in particular, the cardinality of the integers is aleph-null (0). Also "cardinal number".
Cartesian coordinates

Cartesian (or rectangular) coordinates are used in the most common three-dimensional coordinate system. There are three mutually perpendicular axes, labeled x, y, and z. Click on the illustration for a larger picture.

Cartesian Product
The Cartesian product A × B of two sets A and B is the set of ordered pairs of elements {(a1, b1), (a1, b2), (a2, b1), ...}.
Circuit
A circuit is a path whose beginning and ending vertices are one and the same. See Cycle.
Clique
A clique is a subgraph, S = (V, E) of a graph, which is isomorphic to Korder(S).
Closed
A walk is considered closed if the beginning and end vertices are the same. See Circuit, cycle.
Complete Graph
A complete graph is a graph where each vertex is connected to every other vertex. See k-complete.
Component
A component of a graph G is a subgraph C of G such that every vertex of C is connected to every other vertex in C, and all vertices in V(G) not in V(C) are not connected to any vertex in V(C).
Connected
A graph is connected if there exists a path connecting every pair of vertices.
Contour Map
Let be a set of points in the domain of f and let K = a set of the corresponding values in the range of f. Then the set of level curves, , for , constitutes a contour map of f.
Coordinate Vector
A coordinate vector is a unit vector parrallel to one of the coordinate axes. In rectangular coordinates, the coordinate vectors are ,, and , unit vectors parallel to the x,y, and z - axes respectively.
Cycle
A cycle is a circuit which does not repeat any vertices, except for the first and last ones.
cylindrical coordinates

Cylindrical coordinates are another way to describe the position of a point in three-dimensional space. This coordinate system is similar to the two-dimensional polar coordinate system, which has a radius and a polar angle. The cylindrical coordinate system adds a height, usually represented by the symbol z. Click on the illustration for a larger picture.

Mathematics and physics have different conventions for the names of the cylindrical coordinates.

D

Degree
The degree (or valence) of a vertex is the number of edges incident that vertex. See In-Degree, Out-Degree.
Digraph
A digraph, or directed graph, is a graph, where E consists of directed edges.
Directed Edge
A directed edge is an edge (x, y) which is an ordered pair. Ordering these pairs adds a connotation of direction; the edge starts at an endpoint x and continues in the direction of y.
Directed graph
See Digraph.
Directional Derivative
Suppose that the function f is differentiable at a point P n, that OP is the position vector to P, and that u is a unit vector in n. The directional derivative of f at P in the direction of u, written Du f (P), is The directional derivative is a scalar that gives the rate of change of f in the direction of u. It may be calculated from the gradient of f at P, , by rising the scalar or dot product of the gradient vector

E

Edge
An edge is a connecting element of a graph. Edges in a graph connect (usually) two elements in a graph called vertices. See Endpoint, Graph, Loop.
Eigenvalue Problem
The problem is to find eigenvalues, , and eigenvectors, x, such that Ax = x for an operation 'A'. 'A' is usually a matrix, but can be any linear operator. For example,

and x"(t) = x(t) are both eigenvalue problems.
Empty
A graph is empty iff it has no edges.
Endpoint
The endpoints of an edge are the two vertices incident to that edge.
Euler Identity
The equation eix = cos(x) + i sin(x).

F

Ford Fulkerson Algorithm
The Ford Fulkerson Algorithm solves the maximum-flow problem for network graphs. It does so by repeatedly finding augmenting paths from the source vertex to the sink, until no augmenting flow path exists. At this point, the current flow is maximal.
Forest
A forest is a graph which contains no cycles. See tree
Fourier series
A method of approximating a periodic function by a series of sine and cosine functions. The Fourier series of a function f(x) with period 2P is given by

where:


the Kth approximation of f(x) is
fulcrum
The fulcrum, also known as the pivot point, is the point where the board of the see saw rests. In the following picture, the triangle is the fulcrum:

G

Graph
A graph is a pair of sets (V, E), where V is a set of points called vertices, and E is a set of pairs (u, v), where and , called edges. A graph with p vertices and q edges is called a p,q-graph. For a given graph G, the vertices and edges of G are denoted V(G) and E(G), respectively. See Simple Graph, Digraph, Multigraph, Pseudograph.

H

I

In-Degree
The in-degree of a vertex v is the number of directed edges with v as their terminal vertex. The in-degree of a vertex is denoted d-(v). See Digraph, Out-Degree.
Incident
A vertex v is said to be incident to an edge e if it is an endpoint to e. An edge is said to be incident with each of its endjoints.
Independent Set
An independent set of a graph G is a set of vertices I, where no two members of I are adjacent in G.
Induced Subgraph
An induced subgraph on a vertex set is a graph , where is the set of edges in E(G) whose endpoints are elements of .
Isolated
A isolated vertex is one with a degree of zero.
Isomorphic
Two graphs are isomorphic, if there exists a graph isomorphism between the two.
Isomorphism
A graph isomorphism between two graphs G and H is a bijective mapping f of vertices of G on the vertices of H such that iff .

J

K

k-Complete Graph
A k-complete graph is a complete graph with k vertices.
k-Regular Graph
See Regular Graph.

L

least squares fitting
The general problem is to find a curve which fits a set of data points. In least squares fitting, you choose the curve which minimizes the sum of the squares of the errors (i.e., the sum of the vertical distances between the points and the curve).
Leibnitz's Rule
The rule that if D is a differential operator, then D must have the property that D(uv) = (D(u))v + u(D(v)).
Length
For the length of a path see path.
Level Curves
One way on visualizing a function of two variables, , is to draw its level curves: curves where , where k is restricted to real numbers. For example, for the function represents a family of level curves and represents a specific level curve. The surface is an elliptic paraboloid, , is a family of ellipses in the xy-plane, and is a specific ellipse in this family.

If k denotes the height or elevation of the surface, , then the level curves show where the graph of has height k. The level curves may be regarded as the projections to the xy-plane of the traces of the graph of f in the horizontal plane z = k. If you visualize the level curves as being lifted up to the surface at the indicated height, you can put together a picture of the surface. The surface is steep where the level curves are close together and flatter where they are further apart.

Level Set
For any function f of n variables, define W = f (P) where the point P = (x1 , x2 , ..., xn ). The set {Pi } of points Pi = (x1i , x2i , ..., xni ) such that f (Pi ) = k, is called a level set. When f is a function of two variables, x and y, the graph of the points (x, y) that satisfy f (x, y) = k is called a level curve. For example, the graph of x 2 + y 2 = 9 is a level curve in 2 for the function f (x, y) = x 2 + y 2. When f is a function of three variables, x, y, and z, the graph of the points (x, y, z) such that f (x, y, z) = k is called a level surface in 3. For example, the graph of the ellipsoid, is a level surface for
Loop
A loop is an edge whose endpoints are the same vertex. See pseudograph.

M

mean
The mean or expected value of a random variable is a "weighted average" of the possible values in the domain of the variable. The weights are the probabilities associated with each value. Mean is one measure of central tendency of the associated probability distribution.

Mean(x) = E(x) = xf(x) for a discrete random variable. For a continuous random variable, the summation becomes the integral across all possible values of x.

Multigraph
A multigraph is a graph (V, E) where the set E is a multiset of pairs (x, y).

N

Natural Numbers
The set of numbers {1, 2, 3, ...}. Its symbol is N.
Neighbor
Two vertices are neighbors of each other if they are adjacent.
Node
A synonym for vertex.

O

one-to-one
A function or map f from set A into set B is one-to-one if no element of B is the image of more than one element of A. A one-to-one map is sometimes called an injection. See also onto.
onto
A function or map f from set A into set B is onto B if every element of B is the image of some element of A. An onto map is sometimes called a surjection. A function that is both one-to-one and onto is also called a bijection and has an inverse function that is also a bijection.
Order
The order of a graph G = (V, E) is the number of vertices in the graph, |V|. See Size.
Out-Degree
The out-degree of a vertex v is the number of directed edges with v as their initial vertex. The out-degree of a vertex is denoted d+(v). See also Digraph, In-Degree.

P

Path
A path is a walk where no vertex is repeated. A path with n edges is denoted Pn.
Planar
A graph is planar if it can be drawn on a plane so that the all of the edges do not cross each other. In other words, edges of a planar graph only intersect at vertices.
Proper Polygon
A proper polygon is a polygon with all of its sides of equal length.
Pseudograph
A pseudograph is a graph (V, E), where E could contain edges of the form (x, x). These edges are called loops.
Polar Coordinates
An alternative to the traditional rectangular coordinate system to locate points in the plane. Let P be a point in the plane with rectangular coordinates (x,y). The point P can be located in polar coordinates (r,) by specifying both the distance of OP, the radial line segment from the origin to P, and the positive angle (measured counter-clockwise) between the positive x-axis and the radial line segment r from the origin to P.
Relationships between the two coordinate systems can be obtained geometrically:


For a specified point P0(x0,y0), there are many distinct pairs of polar coordinates (r,) that locate the point. For example, if P0(x0,y0) = P0(3,-3) then P0 may be specified in polar coordinates by or more generally, by

Q

R

random variable
A random variable is variable used to describe the possible outcomes of a process or experiment. The set of all possible values that can be assumed by the random variable is known as the sample space. Each value in the sample space has an associated probability, which allows probabilistic statements to be made about process outcomes.
Rational Numbers
The set of numbers that are quotients of two integers. Its symbol is Q (for "quotients").
Rectangular Coordinates
See cartesian coordinates.
Regular
A graph is called regular if the degree of each vertex is exactly the same. If the degree of every vertex in a graph G is k, then the graph is k-regular.

S

Simple Graph
A simple graph is a graph G = (V, E) where E is a set of unordered pairs of distinct elements of V.
simulation
Simulation is a technique which allows the user to perform statistical experiments on mathematical models of complex stochastic (i.e., random) processes in order to estimate system performance. Generally, random numbers are generated according to some probabilistic model (e.g., the Poisson distribution) and substituted into the appropriate equations to generated the simulated outcome.

Simulation is particularly useful when testing on the real system is expensive or inconvenient, or if the system has not yet been physically implemented.

Size
The order of a graph G = (V, E) is the number of edges in the graph, |E|. See Order.
Spanning Graph
A spanning graph of G is a subgraph H, whose vertex set is V(G).
spherical coordinates

Spherical coordinates are a way to describe the position of a point in space. There are three coordinates: a radius from the origin, an azimuthal angle in the xy-plane, and a polar angle from the z-axis. Unlike cartesian coordinates, polar coordinates are limited in size. The radius must be a positive number, the azimuthal angle must be a number between 0 and 2, and the polar angle must be a number between 0 and . Click on the illustration for a larger picture.

Mathematics and physics have different conventions for the names of the spherical coordinates.

stochastic
Stochastic is used to describe processes or experiments where the outcomes are variable and where the likelihood of certain outcomes can be described by the principles of probability. A simple example of a stochastic process is a coin toss. In contrast, a deterministic model is one where repeated experiments produce (essentially) the same outcome every time, such as repeated measurements of the velocity of a falling object over the same distance.
Subgraph
A subgraph of a graph G = (V, E) is a graph S = (V′, E′) where V′ is a subset of V and E′ is a subset of E. See Induced Subgraph.
Supergraph
A graph G is a supergraph of a graph H, if H is a subgraph of G.
Superposition Principle
A method for solving differential equations or boundary value problems where the problem is split into two or more subproblems which are easier to solve. The solution to the original problem is obtained by adding the solutions for the subproblems.

T

Trail
A trail is a walk with no repeated edges.
Tree
A graph is called a tree if it is a forest and it is connected.

U

Unit Vector
Any vector of length 1 is a unit vector. The unit vector parallel to a non-zero vector is calculated by , the vector multiplied by the reciprocal of the length of

V

Valence
A synonym for Degree.
Variance
The variance of a random variable is a "weighted average" of the differences between the possible values in the domain of the variable and the mean of that variable. The weights are the probabilities associated with each value. Variance is one measure of spread or dispersion of the associated probability distribution.

Var(X) = E[(X - )2]

Vertex
A vertex is a point element of a graph. Vertices can be connected to each other by elements of a graph called edges. See graph.

W

Walk
A walk is a subgraph which can be characterized as an alternating sequence of vertices and edges, with each edge incident to the immediately preceeding and succeeding vertices. Walks with n edges are denoted Wn. See also trail and path.

X

Y

Z

Copyright © 1998 Rensselaer Polytechnic Institute. All Rights Reserved.