5.1. Basics

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.

Figure 5.1. A directed graph

A directed graph

A directed graph with the node set V={0,1,2,3,4,5,6} and the edge set E={(0,1),(0,3),(1,1),(1,2),(2,3),(3,0),(4,5),(4,6)}. The source of edge (0,1) is node 0, the target is node 1. The edge (0,1) leaves node 0 and is incident to node 1. Node 1 is adjacent to node 0, but not vice-versa. Nodes 0 and 1 are neighbors. The edge (1,1) is a self-loop. The in-degree of 0 is 1, the out-degree is 2. The degree of 0 is 1+2=3. The path (0,1,1,1,2,3) leads from node 0 to node 3; its length is 5; it is not simple. The path (0,1,2,3,0) is a cycle of length 4, so the graph is cyclic. It is not strongly connected, because 4 is not reachable from 1, for example.


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.

Figure 5.2. An undirected graph

An undirected graph

An undirected graph with the node set V={0,1,2,3,4,5,6} and the edge set {{0,1},{0,3},{1,2},{2,3},{4,5},{4,6}}. The edge {0,1} is incident to the nodes 0 and 1. Nodes 0 and 1 are adjacent to each other. The degree of node 0 is 2. The graph is cyclic and not connected.


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]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 v0 to a node vk is a sequence (v0, v1, ..., vk) of nodes in which each two nodes vi and vi+1 next to one another are connected with an edge (vi, vi+1) ({vi, vi+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 v0 (that is, vk = v0), 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.

Exercises

Exercise 46.

In Figure 2.26 we have got to know a tree. As we can see from this figure, every tree is a graph in particular: It consists of nodes and edges.

[Tip]Tip

Accordingly, LEDA has no separate class for trees, because they can always be managed with the class graph, which is introduced in the next section.

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.

Figure 5.3. Graph or tree?

Graph or tree?


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 parent, child, ancestor, descendant, root, leaf, subtree, subgraph, forest, and connected component.

Exercise 47.

The Handshaking Lemma says that in an undirected graph the sum of the degrees of all nodes is exactly two times the sum of the edges. Think over why this always holds true. Where does the lemma have its name from?

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?




Imprint-Dataprotection