abelian group
A group G whose operations satisfies the commutative law a*b =
b*a for any a and b in G.
acyclic
A graph with no cycles is called acyclic.
adjacent
1) Two nodes in a graph are adjacent if there is an edge joining them.
2) Two nodes in a digraph are adjacent if there is an arc joining them. If there is an arc from node u to node v, u is adjacent to v and v is adjacent from u.
3) Two edges are adjacent if they are incident with a common node.
adjacency
matrix
If a graph has n nodes, the adjacency matrix is an n x n matrix for which the entry in row i
and column j is 1 if there is an edge (arc) from node i to node j
and 0 if there is not. (The matrix is dependent on choosing an ordering of the
vertices from 1 to n.)
arc
In a digraph, nodes are joined by directed lines from one to another;
these directed lines are called arcs. See also edge.
arc disjoint
See edge-disjoint.
Aut G
The set of all automorphisms of G.
automorphism
1. For groups: an isomorphism from a group to itself.
2. For graphs: an isomorphism from the node set of a graph to itself.
bipartite
graph
A graph whose set of nodes can be divided into 2 subsets such that each
edge has one node in each of the subsets.
block
A maximal nonseparable subgraph of a graph.
branch (branch
weight)
A branch at a node u of a tree T is a maximal subtree
containing u as an endnode. The branch weight at u is the
maximum number of edges in any single branch.
breadth-first
A method of finding a spanning tree for a graph which has as its first
principle finding as many edges as possible incident with a given node.
bridge
An edge (arc) whose removal from a graph (digraph) would increase the
number of components. See also cutnode.
Cn
A cycle with n nodes.
Cayley
color-graph
A method of assigning colored edges to a graph whose nodes are the
vertices of a group G so that the resulting graph has automorphism group
G.
center
That set of nodes in a connected graph of minimum eccentricity in that
graph. Each node in the center is called a central node. See also eccentricity
and radius.
central node
A node of minimum eccentricity in a graph.
central
place theory
A method of describing, using tiling of the plane by an hierarchy of
hexagons, the manner in which places share space according to various ideas
involving marketing, transportation, or administration.
centroid
The set of all nodes in a tree of minimum branch weight. See also center.
centroid node
A node in a tree of minimum branch weight.
chirality
Two directed cycles are chiral if they are oriented in different
directions (one clockwise, one counterclockwise) in the plane. Otherwise
they are achiral.
chromatic
number
χ(G)
the minimum number of colors needed to color the nodes of a graph G so that no
adjacent nodes have the same color.
circumference
The length of a longest cycle in a graph (not defined for acyclic
graphs).
closed
interval
[a,b] is the set of all real numbers x such that a ≤ x
≤
b.
closed walk
See walk.
coloring
An assignment of different colors to the vertices of a graph so that
edges which are adjacent have different colors. If different geographic regions
are viewed as single nodes, and regions are adjacent if they have a common
border of more than one point, assigning colors to the graph thus defined
colors the regions, also.
color ramp
A subset of colors chosen to form a smooth sequence of colors for a thematic
map.
complement of G
The graph consisting of the same set of nodes as G and having
edge set the set of non-edges of G.
complete
bipartite graph (Km,n)
The bipartite graph consisting of one set of m nodes, another set of n
nodes, and all mn possible edges between nodes of the two sets.
complete graph
with n nodes (Kn)
The graph with n nodes containing all of the n(n-1)/2 possible edges;
that is, every node is adjacent to every node and is of degree n - 1.
component
A maximal connected subgraph of a graph. The component containing a node
v consists of all nodes which can be reached from v by a walk and all edges in
those walks. See also connected.
composition
of two transformations f followed by g; defined by a(fg)
= (af)g.
condensation
A digraph whose nodes are the strong components of another digraph, with
edges between nodes where edges exist between strong components in the original
digraph.
congruent
a is congruent to b (modulo m) if m is a
divisor of a - b.
connected
A graph is connected if there is a walk between any two nodes. A
connected graph has only one component.
contrapositive
The contrapositive of the proposition "if p then q"
is the equivalent proposition "if not q, then not p."
cube
A three-dimensional solid with six square faces and right angles at all
corners (also called Q3).
cut
A set of arcs whose removal would disconnect a network.
cutedge
See bridge.
cutnode (cutpoint)
A node whose removal from a graph increases the number of components.
Note that the removal of a node requires the removal of all edges incident with
that node.
cycle
A closed walk with at least 3 nodes, all of whose nodes are distinct
(except:first=last). See also walk.
cyclic group
A group all of whose elements are powers of a single element g;
the group is denoted <g>.
degree (in-degree,
out-degree) of a node
1) In a graph, the degree is the number of nodes adjacent with the node.
2) In a digraph, the indegree is the number of nodes adjacent to the node, and the outdegree is the number of nodes adjacent from the node.
degree
sequence
A list, in descending order, of the degrees of each of the nodes in a
graph.
depth-first
A method for finding a spanning tree for a graph which has as its first
principle finding as long a path as possible in the graph.
developable
surfaces
A surface which can be cut so that it will unroll perfectly onto the
plane.
diameter
The length of a longest geodesic in a graph.
digraph (directed
graph)
A set of nodes V and arcs E such that each arc is a
directed connection from one node to another. See also graph.
Dijkstra's
algorithm
An algorithm designed to compute the length of the shortest path between
a given pair of nodes in a connected, weighted graph.
Diophantine
equation
An equation that is studied (classically in number theory) to determine
which integer values it assumes.
direct product
If G, H are groups, the direct product G x H = {(g,h)| g∈G,
h∈H}
with (g1,h1) * (g2,h2)
= (g1*g g2, h1*h
h2).
discrete
Separated from each other, as opposed to continuous. The set of
nodes of a graph is usually a discrete set.
disjoint paths
Two paths from u to v are called disjoint if they have no
nodes or edges in common except u and v.
distance d(u,v)
The length of the shortest walk from u to v.
dodecahedron
Polyhedron with 12 pentagonal faces.
dual graph
A graph obtained from a plane map by placing a node inside each region
and joining nodes which lie in adjacent regions.
eccentricity
The eccentricity of a node v in a connected graph is the maximum
distance d(u,v) taken over all nodes u in the graph. See
also radius.
edge
In a graph, nodes are joined by undirected lines from one to another;
these undirected lines are called edges. See also arc.
edge-disjoint
Two paths from u to v are called edge-disjoint if they
have no edges in common.
embed
A graph is embedded on a surface if it can be drawn on that surface
without artificial intersections of edges.
endnode
A node of degree one.
eulerian
A graph is called eulerian if there is a closed trail containing every
edge.
F-diagram
A shorthand for describing graphs with a lot of symmetry; first
described by Frucht.
flow
A function which assigns weights to each arc in a network in such a way
that capacity is never exceeded.
fractal
Fractional dimension; used to describe the relative amount of space a
curve fills, for example.
geodesic
A shortest path between two nodes.
girth
The length of a shortest cycle (non defined for acyclic graphs).
GIS, Geographical Information
System, Geographic Information System
A tool for making computer maps from information stored in a data base.
gnomonic
projection
A method of projecting the sphere onto the plane using the center of the
sphere as the center of projection.
graph
A set of nodes V and edges E such that each edge is an
undirected connection between two nodes. See also adjacent, degree,
digraph,
incident,
multigraph, subgraph, tree.
grayscale
An assignment of different shades of gray to represent different regions
on a thematic map; less expensive than color in traditional publishing
environments.
greedy algorithm
An algorithm which sets about optimization locally yet still achieves it
globally.
group
A set G of objects together with a binary operation * on that
object such that for each a, b∈G
hamiltonian
A graph is called hamiltonian if it contains a cycle containing every
node.
Hasse's
algorithm
An algorithm to compute the shortest paths in a connected graph between
each pair of nodes.
hierarchy
A systematic ranking of persons or objects.
homeomorphic
(homeomorphism as distinct from homomorphism)
Two graphs are homeomorphic if one can be obtained from the other by a
sequence of subdivisions of edges by insertion of a node along such edges,
turning one edge into two.
hue
A term to describe basic color.
icosahedron
A polyhedron with 20 triangular faces.
identity
The element e of a group G such that e * a =
a * e = a for every a∈G.
incident
1) In a graph, if an edge e consists of an unordered pair of
nodes u and v, u and v are said to be incident with
e, or e is said to be incident with u and v.
2) In a digraph, if an arc e consists of an ordered pair of nodes u and v, so that e is an arc from u to v, we still say that e is incident with u and v.
indegree
See degree.
induced
subgraph
For a set S of nodes in a graph G, the maximal subgraph
whose set of nodes is S.
invariant
A property left unchanged under isomorphism.
inverse
1. of an element x of a group: that element x-1
with x * x-1 = x-1 * x = e
2. of a one-to-one correspondence f: A → B: the mapping g: B → A defined by bg = a if and only if af = b.
isolated node
A node of degree 0.
isomorphism
1. between groups A and B: a one-to-one
correspondence f: A → B such that (a * b)f = af * bf for
every a, b in A (this latter property makes f a homomorphism;
thus an isomorphism is a one-to-one correspondence which is a homomorphism).
2. between graphs G and H: a one-to-one correspondence between the nodes sets of G and H which induces a one-to-one correspondence between their edge sets.
Klein
four-group
Z2 x Z2
Kruskal's
algorithm
An algorithm to find a minimal spanning tree in a connected weighted
graph.
labeled
A graph is labeled if names are given to the nodes.
latitude
A measure (in degrees) of north-south displacement from the horizontal
axis of the Equator.
length of a walk
The number of edges or arcs in a walk.
longitude
A measure (in degrees) of east-west displacement from the Prime
Meridian.
loop
An edge joining a node to itself. See also pseudograph.
luminosity
A measure of relative lightness or darkness of a color.
Manhattan
space
A space in which distances are measured along perpendicular straight
lines, such as the streets in a rectangular grid system like that of Manhattan.
matrix
An array of numbers arranged into rows and columns. A matrix with m
rows and n columns is called an m by n matrix (m x n).
metric
A measure defining distances on a structure so that distance is non-zero,
symmetric, and satisfies the triangle inequality.
minimal
spanning tree
A spanning tree in a connected weighted graph such that the sum of the
weights of its edges is as small as possible.
mixed
multigraph
A multigraph with some undirected edges and some directed arcs.
modulo
See congruent.
multigraph
A set of nodes V and edges G, like a graph except that
there may be more than one edge joining the same two nodes. The
"graph" of Königsberg is a multigraph, as there are multiple bridges
joining the same landmasses.
mutually
reachable
A pair of nodes in a digraph is mutually reachable if paths exist from
each to the other.
node
An object which is joined to other objects by edges or arcs (also called
point or vertex).
non-Euclidean
A geometry which does not rely on Euclid's parallel postulate.
nonseparable
A connected non-trivial graph with no cutnodes is
called nonseparable.
octahedron
A polyhedron with eight triangular faces.
one-to-one
A transformation f such that if a ≠ b, then af
≠ bf.
open walk
See walk.
oriented graph
A digraph with no pairs u, v of nodes such that uv
and vu are both arcs.
Pn
A path with n nodes and n - 1 edges.
path
See walk.
permutation
1. A one-to-one correspondence between members of a set
2. The set of all permutations of {1, 2, ..., n} is denoted Sn.
pixel
The underlying unit of a grid; a computer monitor's screen consists of
square pixels.
planar
A graph is called planar if it can be drawn in the plane without any
edges crossing except at nodes with which they are incident.
Platonic solid
A regular polyhedron.
Prim's
algorithm
A greedy algorithm that finds a minimal spanning tree in a connected
weighted graph.
pseudograph
A set of nodes and edges allowing both multiple edges joining the same
pair of nodes and edges joining nodes to themselves. See also loop,
multigraph.
Qn
1. Q2 is the square
2 Q3 is the cube
3. Qn is called an n-cube and is the regular graph of degree n with 2n nodes obtained by joining corresponding nodes of two copies of Qn-1 (n≥3).
radius
In a connected graph, the minimum of the eccentricities of the nodes.
reachable
A node u in a digraph is reachable from v if there is a
walk from v to u.
reflection
A transformation in which every object is mapped to its mirror image
across some line.
regular
Having all nodes of the same degree.
regular
polyhedron
A three-dimensional figure all of whose sides are regular polygons of
the same size and all of whose interior angles are equal.
root
A single node in a tree distinguished from the others. A rooted tree is
a tree in which one node has been singled out as the root.
rotation
A transformation which rotates each object the same amount about some
axis.
saturation
A term to describe the amount of hue in a color; also called
intensity.
Schläfli
symbol
{p,q} represents a regular polyhedron whose faces are
regular p-gons, q of which meet at a vertex.
Schlegel
diagram
A planar representation of a regular polyhedron.
self-complementary
A graph is called self-complementary if it is isomorphic to its
complement.
self-similar
Containing a subset which is in structure identical to itself.
semicycle
A non-trivial closed semiwalk with all nodes distinct (except
first=last).
semipath
A semiwalk in which all nodes are distinct.
semiwalk
See walk.
separate
A set S of nodes is said to separate u and v in G
if u and v are in different components of G - S.
sink
A node of outdegree zero in an acyclic digraph.
source
A node of indegree zero in an acyclic digraph.
spanning tree
A tree containing all the nodes of a connected graph.
spanning
subgraph
A subgraph containing all the nodes of the original graph.
spanning walk
A walk containing all the nodes of the graph.
Steiner
transformation
The process of locating a Steiner network within a set of polygonal
cells and discarding the original structure.
Steiner tree
A tree of shortest length constructed to connect a given set of points
in the plane.
stereographic
projection
A method of projecting the sphere onto the plane using a pole as the
center of projection.
strongly
connected, unilaterally connected, weakly connected
1) A digraph is strongly connected or strong if each pair of nodes in
the digraph is mutually reachable.
2) A digraph is unilaterally connected if, for each pair of nodes in the digraph, at least one is reachable from the other.
3) A digraph is weakly connected if each pair of nodes is connected by a semiwalk.
Every strongly connected digraph is unilaterally connected; every unilaterally connected digraph is weakly connected.
strongly
orientable
A multigraph is strongly orientable if each edge can be given
a direction in such a way that the resulting multidigraph is strongly
connected.
subgraph
A subgraph H of a graph G is a graph having all of its
nodes and edges in G.
subgroup
A subset of a group which is itself a group under the same operation.
subpath
A path contained as part of a larger path.
supergraph
G is a supergraph of H if H is a subgraph of G.
tetrahedron
A four-sided polyhedron with four triangular faces.
thematic map
A map which represents different regions by different colors depending
on the context of data concerning those regions.
theta graph
A graph containing two nodes of degree three and three disjoint paths
connecting them (named for its resemblance to the Greek letter theta).
thickness
The thickness of a graph is the minimum number of planar subgraphs of G
whose union is G.
torus
A doughnut-shaped solid obtained by attaching two opposite ends of a
cylinder.
trail
See walk.
transformation
A function f:A → B which assigns an element af ∈ B
to each a ∈ A.
transposition
A permutation which interchanges two objects and leaves all the others
fixed.
tree
A connected graph without any cycles. In a tree, there is a unique walk
between any two nodes. A tree with n nodes has n-1 edges.
Triangulated Irregular
Network (TIN)
A method of dividing the plane into non-overlapping triangles, with
elevations at the vertices, as an aid in drawing three-dimensional maps.
underlying
multigraph
The multigraph obtained from a (multidigraph by replacing all arcs by
undirected edges.
union
The union of two graphs is the graph with node set the union of the two
node sets and sedge set the union of the two edge sets of the two graphs.
voxel
Volume pixel.
walk
1) An alternating sequence of nodes and edges, beginning and ending with
nodes, such that an edge in the sequence is in fact an edge between the nodes
it is listed between. Given this convention, one often lists only a
sequence of edges, with the proviso that consecutive edges are incident.
2) A walk is called closed if the first and last node are the same. Otherwise it is open.
3) A walk is called a trail if all the edges are distinct.
4) If all the nodes are distinct (except perhaps the first being also the last), the walk is called a path.
In digraphs, walks are directed; that is, each arc must be from the node preceding it in the sequence to the node following it. A sequence without this added restriction is called a semiwalk.
weight
In some applications, a number or weight may be attached to each edge in
a graph. A typical situation might be for the weight to represent distance or
time between nodes.
wheel
The union of a cycle Cn with a bipartite K1,n
(the one node being the hub of the wheel).
wreath product
A[B] of two groups of permutations is a group which uses
the operation of B on elements determined by A; useful for
describing automorphisms of multiple copies of the same graph.