178 Appendix
We will consider various sub-structures of graphs, the simplest one being paths. A
path in a graph G =(V,E) is a sequence of vertices (v
0
,...,v
) such that for every
i ∈ []
def
={1,...,} it holds that v
i−1
and v
i
are adjacent in G. Such a path is said to
have
length .Asimple path is a path in which each vertex appears at most once, which
implies that the longest possible simple path in G has length |V |−1. The graph is
called
connected if there exists a path between each pair of vertices in it.
A
cycle is a path in which the last vertex equals the first one (i.e., v
= v
0
). The cycle
(v
0
,...,v
) is called simple if >2and|{v
0
,...,v
}| = (i.e., if v
i
= v
j
then i ≡ j
(mod ), and the cycle (u, v, u) is not considered simple). A graph is called
acyclic (or a
forest) if it has no simple cycles, and if it is also connected, then it is called a tree.Note
that G=(V,E) is a tree if and only if it is connected and |E|=|V |−1, and that there
is a unique simple path between each pair of vertices in a tree.
A
subgraph of the graph G =(V,E)isanygraphG
=(V
,E
) satisfying V
⊆ V
and E
⊆ E. Note that a simple cycle in G is a connected subgraph of G in which
each vertex has degree exactly two. An
induced subgraph of the graph G =(V,E)is
any subgraph G
=(V
,E
) that contains all edges of E that are contained in V
(i.e.,
E
={{u, v}∈E : u, v ∈V
}). In such a case, we say that G
is the subgraph induced
by
V
.
Directed Graphs. We will also consider (simple) directed graphs (also known as
digraphs), where edges are ordered pairs of vertices.
1
In this case, the set of edges is a
subset of V × V \{(v, v):v ∈V }, and the edges (u, v)and(v, u) are called
anti-parallel.
General (i.e., non-simple) directed graphs are defined analogously. The edge (u, v)is
viewed as going from u to v, and thus is called an
outgoing edge of u (resp., incoming edge
of v). The out-degree (resp., in-degree) of a vertex is the number of its outgoing edges
(resp., incoming edges). Directed paths and the related objects are defined analogously;
for example, v
0
,...,v
is a directed path if for every i ∈ [] it holds that (v
i−1
,v
i
)isa
directed edge (which is directed from v
i−1
to v
i
). It is common to consider also a pair
of anti-parallel edges as a simple directed cycle.
A
directed acyclic graph (DAG) is a digraph that has no directed cycles. Every DAG
has at least one vertex having out-degree (resp., in-degree) zero, called a
sink (resp., a
source). A simple directed acyclic graph G =(V,E) is called an inward (resp., outward)
directed tree if |E|=|V |−1 and there exists a unique vertex, called the root, having
out-degree (resp., in-degree) zero. Note that each vertex in an inward (resp., outward)
directed tree can reach the root (resp., is reachable from the root) by a unique directed
path.
2
Representation. Graphs are commonly represented by their adjacency matrix and/or
their incidence lists. The
adjacency matrix of a simple graph G =(V,E)isa|V |-by-|V |
1
Again, the term “simple” means that self-loops and parallel (directed) edges are not allowed. In
contrast, anti-parallel edges are allowed.
2
Note that in any DAG, there is a directed path from each vertex v to some sink (resp., from
some source to each vertex v). In an inward (resp., outward) directed tree this sink (resp.,
source) must be unique. The condition |E|=|V |−1 enforces the uniqueness of these paths,
because (combined with the reachability condition) it implies that the underlying graph
(obtained by disregarding the orientation of the edges) is a tree.