Mathematical definitions
Graphs as mathematical structures are an important abstraction for reasoning about systems involving networks. Using a mathematical abstraction allows us to present algorithms in a context-independent way; for instance, a graph search algorithm can be applied to both social networks as well as to digital circuits.
Undirected Graphs
Mathematically, an undirected graph is a pair \(\Tuple{\Verts,\Edges}\), where
\(\Verts\) is a (usually finite) set of vertices, also called nodes, and
\(\Edges\) is a set of edges between the vertices. The elements in the set are pairs of the form \(\Set{u,v}\) such that \(u,v \in \Verts\) and \(u \neq v\). In this definition, edges between a vertex and itself, called self-loops, are thus not allowed.
The degree of a vertex is the number of edges incident to it; that is, the number of edges including the vertex.
Example: Undirected graph
Consider the graph \(\Tuple{\Verts,\Edges}\) with
the vertices \(\Verts = \Set{a,b,c,d,e,f,g}\), and
the edges \(\Edges = \{\Set{a,b},\Set{a,c},\Set{a,e},\Set{a,f},\Set{b,f},\Set{e,f},\Set{c,d},\Set{c,g},\Set{d,g}\}\).
It is illustrated graphically below. The vertices drawn as circles and edges as lines between the vertices. The degree of the vertex \(a\) is 4.
A path of length \(k\) from a vertex \(v_0\) to a vertex \(v_k\) is a sequence \(\Path{v_0,v_1,...,v_k}\) of \(k+1\) vertices such that \(\Set{v_{i-1},v_i} \in \Edges\) for each \(i \in [1 .. k]\). A vertex \(v\) is reachable from a vertex \(u\) if there is a path from \(u\) to \(v\). Note that each vertex is reachable from itself as there is a path of length \(0\) from the vertex to itself. A path is simple if all the vertices in it are distinct.
Example: Paths
The graph below
has a non-simple path \(\Path{a,c,d,g,c,d}\) of length 5 from \(a\) to \(d\), and
has a simple path \(\Path{a,c,d}\) of length 2 from \(a\) to \(d\).
A connected component is a maximal set of vertices such that every vertex in the set is reachable from every other vertex in the set. The graph is connected if it has only one connected component, meaning that every vertex in it is reachable from all the other vertices.
Example: Connectivity and connected components
The graph below is connected. Its only connected component is \(\Set{a,b,c,d,e,f,g}\)
The graph below is not connected as it has two two connected components: \(\Set{a,b,e,f}\) and \(\Set{c,d,g}\).
A cycle is a path \(\Path{v_0,v_1,...,v_k}\) with \(k \ge 3\) and \(v_0 = v_k\). A cycle \(\Path{v_0,v_1,...,v_k}\) is simple if \(v_1,v_2,...,v_k\) are all distinct. A graph is acyclic if it does not have any simple cycles.
Example: Cycles and acyclicity
The graph below is not acyclic as it contains a simple cycle \(\Path{a,e,f,a}\).
However, the graph below is acyclic.
Directed Graphs
Directed graphs are otherwise as undirected graphs except that the edges have a direction. Formally, a directed graph, or simply digraph, is a pair \(\Tuple{\Verts,\Edges}\), where
\(\Verts\) is a (usually finite) set of vertices, and
\(\Edges \subseteq \Verts \times \Verts\) is a set of edges between the vertices. A pair \(\Tuple{u,v} \in \Edges\) denotes an edge from the vertex \(u\) to the vertex \(v\).
Example: Directed graph
Consider the directed graph \(\Tuple{\Verts,\Edges}\) with
the vertices \(\Verts = \Set{a,b,c,d,e,f,g}\), and
the edges \(\Edges = \{\Tuple{a,b},\Tuple{a,e},\Tuple{b,b},\Tuple{b,f},\Tuple{c,a},\Tuple{c,d},\Tuple{c,g},\Tuple{d,g},\Tuple{e,f},\Tuple{f,a},\Tuple{g,d}\}\).
It is illustrated graphically below. Again, the vertices are drawn as circles. The edges are drawn as lines with direction arrow heads. Notice the loop from the vertex \(b\) to itself and the two edges between the vertices \(d\) and \(g\).
The out-degree of a vertex is the number of edges from it while the in-degree is the number of edges to it. A path of length \(k\) from a vertex \(u\) to the vertex \(u'\) is a sequence \(\Path{v_0,v_1,...,v_k}\) of \(k+1\) vertices such that \(v_0 = u\), \(v_k = u'\) and \(\Tuple{v_{i-1},v_{i}} \in \Edges\) for all \(i \in [1 .. k]\). A path is simple if all vertices in it are distinct. A path \(\Path{v_0,v_1,...,v_k}\) is a cycle if \(k \ge 1\) and \(v_0 = v_k\).
Example: Degrees and paths
In the directed graph shown below,
the in-degree of \(f\) is 2 and the out-degree is 1,
some simple paths are \(\Path{c}\), \(\Path{c,d,g}\), and \(\Path{a,b,f}\), while
the paths \(\Path{b,b}\), \(\Path{a,e,f,a}\), \(\Path{a,b,f,a}\), and \(\Path{d,g,d}\) are cycles.
Directed Acyclic Graphs (DAGs)
A directed acyclic graph, or simply a DAG, is a directed graph that does not contain any cycles. Such graphs arise in many applications, see, for instance, this Wikipedia page.
Example: DAG
DAGs arise naturally in many time- and order-related areas, where something has to be done before something else can be done. In such a situation, a cycle would mean that some things cannot be done at all. As a small toy example, a dependency graph between clothes for dressing up is shown below (source: Introduction to Algorithms (Aalto access)).
