Algorithmic Problem Solving

In Section 12.7, we showed how binary relations can be depicted as graphs. In this chapter, we discuss the connection between relations and graphs in more detail. Many algorithmic problems involve finding and/or evaluating paths through a graph. Our goal in this chapter is to show how these problems are represented algebraically so that the solution to such tasks can be calculated.

16.1 PATHS IN A DIRECTED GRAPH

We begin the chapter with a number of formal definitions about graphs and paths in a graph. Informally, the notions we introduce are easy to grasp. So, on a first reading, it is not essential to pay attention to the details of the definitions. The details are essential later, when the definitions are used in earnest.

Definition 16.1 (Directed Graph) A directed graph comprises two sets N and E, called the nodes and the edges of the graph, and two functions from and to, both of which have type E→N.

If e is an edge of a graph and from(e) = m and to(e) = n (where m and n are nodes of the graph), we say that e is an edge from node m to node n.

We sometimes write statements of the form “let G = (N,E,from,to)” as a shorthand for introducing a graph and giving it the name G.

Very often, the graphs we consider have a finite set of nodes and a finite set of edges. Later, we also consider labelled graphs. A labelling of a graph is a function defined on the edges of the graph. The ...