Glossary


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)| gG, hH} 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, bG

  1. a * bG
  2. (a * b) * c = a * (b * c)
  3. There is eG with a * e = e * a = e for every aG.
  4. There is a-1G with a * a-1 = a-1 * a = e.

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 aG.

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: AB 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

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:AB 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.