*Learning objectives*

Important fundamental terms: graph, node, edge, directed and undirected, incident, adjacent, source, target, neighbor, self-loop, degree, path, cycle, (strongly) connected |

In Section “A working example: Breadth first search in a graph” we already got
to know a graph. In Figure 3.2 we
interpreted four-letter words as nodes that we connected to each
other with an edge if they differed in one letter only; in this
sense they are “neighbors”. Such a construct of nodes
and edges is called a *graph*. As we already
mentioned there briefly, such structures appear
frequently in computer science: They appear wherever
it is about modeling relations between individual objects.
There the objects correspond to the nodes, the relations to the
edges of a graph. Before we address LEDA's implementation of
graphs, we want to become acquainted with some important
fundamental terms from this topic complex.

Figure 5.1 shows a graph with *directed* edges, in contrast to Figure 3.2, where the edges are undirected. Therefore this graph
is called a *directed
graph*. Such graphs appear if the relation between two
objects is not necessarily symmetric, for instance, in graphs that
model relationships: If Anja is a parent of Sibylle, Sibylle can
never be a parent of Anja. The relation is
“one-way”.

Formally speaking, such a graph G is a pair (V,E) with V
a finite set and E a set of pairs (v1, v2) with v1 and v2 from
V. The elements of V are called *nodes* (or
*vertices*), the elements of E
are called *edges*. An edge (v1, v2) is
interpreted as directed from v1 to v2; it *leaves* v1 and is *incident* to v2. The node v1 is
called the *source* of the
edge, the node v2 is called the *target*. v2 is *adjacent* to v1; the inversion does
not have to hold necessarily, because the *reverse edge* (v2,v1) does not
have to exist necessarily. v1 is a *neighbor* of v2 and vice-versa. An
edge (v1,v1), whose source is equal to its target, is called a
*self-loop*.

In contrast to a directed graph, the edges of an undirected
graph have no direction. More formally speaking, the set E in an
*undirected graph* is a set of two-element
subsets {v1,v2} of V. An edge {v1,v2} is both incident to v1 and
to v2. v1 is adjacent to v2 and vice-versa. v1 and v2 are
neighbors. Since the set {v,v} is the same as the set {v}, self-loops
are impossible in undirected graphs.

Figure 5.2 shows an undirected graph. Such graphs appear if the relation between each two objects is symmetric, for instance, in graphs that model the games that have already been played in the opening-round of a football season: If team A has already played against team B, then team B conversely has played against team A.

The *undirected
version* of a directed graph results from all edges
losing their direction and from self-loops being
removed. Conversely, the *directed version* of an
undirected graph results from creating two edges (u,v) and (v,u)
reversed to each other for every undirected edge {u,v}.

Note | |
---|---|

Already here, we want to point out that LEDA's notion of the terms “directed” and “undirected” is a little different. We will dwell on this in Section 5.2.3. |

The *degree* of a node
in an undirected graph is the number of edges that are incident to
it. In a directed graph, in contrast, one distinguishes between
the *in-degree* and the
*out-degree* of a node v;
the former is the number of edges that are incident to v, the latter
is the number of edges that leave v. The degree of a node in a
directed graph is the sum of its in-degree and its
out-degree.

A *path* in a directed
graph (in an undirected graph) from a node
v_{0} to a node v_{k} is a
sequence (v_{0}, v_{1},
..., v_{k}) of nodes in which each two
nodes v_{i} and v_{i+1}
next to one another are connected with an edge
(v_{i},
v_{i+1}) ({v_{i},
v_{i+1}}). The number k of edges in the path
is called the *length* of
the path. If there is a path P from a node u to a node v, v is called
*reachable* from u via
P. A path is called *simple* if all nodes on it are
different. A path that leads back to the start node
v_{0} (that is, v_{k} =
v_{0}), and that contains at least one edge,
(that is, k > 0), is called a *cycle*. A graph that contains a cycle
is called *cyclic*.

An undirected graph in which each pair of nodes is connected
with an edge is called *connected*. A directed graph in
which each node is reachable from every other node via a path is
called *strongly
connected*.

Generally, *n* denotes the number of
nodes in a graph, whereas *m* denotes the
number of edges.

| In Figure 2.26 we have
got to know a
But not every graph is also a tree, because, for example, a tree must not contain a cycle. Figure 5.3 gives more examples for trees and graphs that are not trees. Work out the difference between a tree and a graph
in detail. Distinguish between the directed and the
undirected case. Have in mind that graphs and trees do not
necessarily have to be connected. Intuitively define the
terms | |||

| The Additionally show that the number of nodes with odd degree is always even. In contrast, in a directed graph the sum of all in-degrees is always equal to the sum of all out-degrees, and both sums are equal to the number of edges. Why does this hold? |