Graphics Reference
In-Depth Information
Apathiscyclicif a node appears more than once in its corresponding list of edges.
A graph is cyclic if any path in the graph is cyclic. We oten call a directed acyclic
graph a DAG.
A topological sort ofthevertices ofaDAGisasequence ofdistinctvertices
v
,...,
v
n
. For every pair of vertices v
i
,v
j
in this sequence, if
(
v
i
,v
j
)
is an edge, then i
<
j.
edgesconnectvertices
that are adjacent in the list. A linear graph has only one path.
Two graphs G
A linear graph isagraphbasedonalistof n vertices; its n
−
are isomorphic if there exists a bijec-
tive mappingbetween thevertices in V
and V
and thereisan edgebetween two ver-
tices of one graph if and only if there is an edge between the two corresponding ver-
tices in the other graph. A graph G
=(
V
, E
)
and G
=(
V
, E
)
=(
V
, E
)
is a subgraph of a graph G
=(
V
, E
)
if V
.
he graph-theoretic distance (or geodesic distance)between connectednodes u and
v isthesumoftheweightsoftheedgesinanyshortestpathconnectingthenodes.his
distance is a metric, namely, symmetry, identity, and the triangle inequality apply.
he adjacency matrix for a graph G with n vertices is an n
V
and E
E
(
V
V
)
n matrix with entries
a
ij
having a value
if vertex i is adjacent to vertex j and zero otherwise. he set
ofeigenvaluesofthismatrixiscalledthegraph spectrum.hespectrumisuseful
for identifying the dimensionality of a space in which a graph may be embedded or
represented as a set of points (for vertices) and a set of connecting lines (for edges).
A geometric graph G
g
is a mapping of a graph toa metric space
S suchthatvertices gotopointsandedgesgotocurvesconnecting pairsofpoints.We
will discuss various types of geometric graphs in this chapter. When the meaning is
clear, we will omit the subscript and refer to G as a geometric graph. he usual map-
ping is to Euclidean space. Sometimes we will measure and compare the Euclidean
distance between points to the graph-theoretic distance between the corresponding
vertices of the graph.
A proximity graph G
p
=[
f
(
V
)
, g
(
E
)
, S
]
=[
V, f
(
V
)]
is a graph whose edges are defined by a prox-
imityfunction f
(
V
)
onpointsinaspace S.herangeoff
(
V
)
ispairsofvertices.One
may regard f
(
V
)
as an indicator function in which an edge exists when g
(
u,v
)<
d,
where d is some nonnegative real value and g
()
is a real-valued function associated
with f
.
A random graph is a function defined on a sample space of graphs. Although ran-
dom graphs are relevant to statistical data, this chapter will not cover them because
of space limitations. Marchette (
) is a standard reference.
()
Trees
5.2.1
A tree is a graph in whichany two nodesare connected by exactly one path. Trees are
thus acyclic connected graphs. Trees may be directed or undirected. A tree with one
nodelabeled root isa rooted tree.Directedtrees arerootedtrees;therootofadirected
tree is the node having no incoming edges.
A hierarchical tree is a directed tree with a set of leaf nodes (nodes of degree
)
representing a set of objects and a set of parent nodes representing relations among
the objects. In a hierarchical tree, every node has exactly one parent, except for the
