Glossary
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
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.
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
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.
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
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
D
u 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
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
A
x =
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).
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 K
th 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:
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.
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
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
.
k-Complete Graph
A
k-complete graph is a
complete graph
with
k vertices.
k-Regular Graph
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.
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).
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
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.
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
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
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.
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.
Trail
A trail is a
walk with no
repeated edges.
Tree
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
Valence
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.
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.
Copyright © 1998 Rensselaer Polytechnic Institute.
All Rights Reserved.