Directed and Undirected Graphs

Before we start diving into graph algorithms, let’s introduce some of the basic concepts of graph theory that we’ll use throughout the course.

Directed graphs

We’ll start with the most basic question: what even is a graph? Let’s look at an example.

The above graph consists of three nodes (named $a$, $b$, $c$) and four edges (drawn as arrows between nodes). The edges have a direction, indicated by the arrowhead. Hence, we call such a graph a directed graph:

• $a \to b$
• $a \to c$
• $b \to c$
• $c \to b$

The actual positioning of the nodes in the graph does not matter. In other words, it has no significance that in the above drawing $a$ is “above” $b$. In fact, here is the same graph drawn in a different layout:

In other words, a graph is completely described by its set of nodes and edges.

By convention, the capital letter $V$ (for vertices) is used to denote the set of nodes. In our example graph, we have

$$V = \{a, b, c\}.$$

To denote the set of edges, we use the capital letter $E$. Each edge is a pair of two vertices, its source and target. In our example graph,

$$E = \{(a, b), (a, c), (b, c), (c, b)\}.$$

In total, a graph $G$ can then be written as:

$$G = (V, E) \quad\text{ with }\quad E \subseteq V \times V.$$

For our example graph,

$$G = (\{a, b, c\}, \{(a, b), (a, c), (b, c), (c, b)\}.$$

In this course, we’ll only consider graphs whose edges fulfill the following properties:

• There are never two edges with the same source and the same target.
• There are no “self-loop” edges of the form $(v, v)$.

Such graphs are called simple graphs. The following figure shows the two forbidden situations that were described above.

Undirected graphs

So far, the graphs we’ve considered have had directed edges with a source and target. However, many times we’ll find that all of the connections between vertices are bidirectional. One example is a traffic network, where the intersections are the nodes and the roads are the edges. Usually, the roads can all be traversed in both directions.

We can describe such a graph as a directed graph, for example.

The above graph has the set of edges:

$$E = \{(a, b), (b, a), (a, c), (c, a), (b, d), (d, b)\}.$$

But, if we know that all connections are bidirectional anyway, there is no need to draw two arrows between each pair of connected nodes. To simplify the drawing, we can just draw a straight line between connected nodes, implying they are connected bidirectionally.

We call such a graph an undirected graph.

How should we define the set of edges $E$ of an undirected graph? We could use a new definition where every edge is not an ordered pair of source and origin, but instead is an unordered set of two vertices. However, it would be inconvenient to have two different definitions of graphs.

The more pragmatic solution is to use the same definition as before: edges are a pair of source and origin. But in an undirected graph, we always require that if: $(u, v)$ is an edge in the graph, then also its reverse $(v, u)$ is an edge. Formally,

$$\text{for all } u, v\in V:\quad (u, v) \in E \to (v, u) \in E.$$

So, the set of edges of our undirected example graph is still

$$E = \{(a, b), (b, a), (a, c), (c, a), (b, d), (d, b)\}.$$

The graph itself has not changed, but the way we have drawn it and interpreted it is different! We can think of the undirected connection between $a$ and $b$ as being represented by the two “half-edges” $(a, b)$ and $(b, a)$.