Game Development Reference
In-Depth Information
Appendix Notation
Our notation for graphs follows Diestel [2005] and we refer to this topic
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 .