Game Development Reference

In-Depth Information

Appendix Notation

Our notation for graphs follows Diestel [2005] and we refer to this topic

for more information about graphs. This topic also contains an excellent

introduction to structural graph theory and the theory of tree-width or graph

decompositions in general.

If
V
is a set and
k

we denote by [
V
]
≤k
the set of all subsets of
V
of

cardinality at most
k
. We write Pow(
V
) for the set of all subsets of
V
.

All structures and graphs in this section are finite. If
G
is a graph we

denote its vertex set by
V
(
G
) and its edge set by
E
(
G
). The
size
of a graph

is the number of edges in
G
and its
order
is the number of vertices.

If
e
:=

∈
N

E
(
G
) then we call
u
and
v
adjacent
and
u
and
e
incident
.

H
is a
sub-graph
of
G
, denoted
H ⊆ G
,if
V
(
H
)
⊆ V
(
G
) and
E
(
H
)
⊆

E
(
G
). If
G
is a graph and
X ⊆ V
(
G
) we write
G
[
X
] for the sub-graph of
G

induced
by
X
, i.e., the graph (
X, E
) where
E
:=
{{u, v}∈E
(
G
):
u, v ∈

X}
. We write
G \ X
for the graph
G
[
V
(
G
)
\ X
]. If
e ∈ E
(
G
) is a single edge

we write
G − e
for the graph obtained from
G
by deleting the edge
e
and

analogously we write
G

{

u, v

}∈

−

v
, for some
v

∈

V
(
G
), for the graph obtained from

G
by deleting
v
and all incident edges.

The
neighbourhood
N
G
(
v
) of a vertex
v

∈

V
(
G
) in an undirected graph

G
is defined as
N
G
(
v
):=

.

A graph
G
is
connected
if
G
is non-empty and between any two
u, v

{

u

∈

V
(
G
):

{

u, v

}∈

E
(
G
)

}

∈

V
(
G
) there exists a path in
G
linking
u
and
v
.A
connected component

of a graph
G
is a maximal connected sub-graph of
G
.

A directed graph
G
is
strongly connected
if it is non-empty and between

any two
u, v

V
(
G
) there is a directed path from
u
to
v
.A
strongly

connected component
, or just a
component
,of
G
is a maximal strongly

connected sub-graph of
G
.

A
clique
is an undirected graph
G
such that

∈

{

u, v

}∈

E
(
G
) for all
u, v

∈

V
(
G
),
u

=
v
.

A
tree
is a connected acyclic undirected graph. A
directed tree
is a tree

T
such that there is one vertex
r ∈ V
(
T
), the
root
of
T
, and every edge of

T
is oriented away from
r
.

Finally, a
hypergraph
is a pair
H
:= (
V,E
) where
E ⊆
Pow(
V
)isaset

of
hyperedges
, where each hyperedge is a set of vertices. We write
V
(
H
)

and
E
(
H
) for the set of vertices and hyperedges of
H
.

Search Nedrilad ::

Custom Search