13.1 Definitions and properties

A graph $\mathbf{G} = (\mathbf{V}, \mathbf{E})$ consists of a set of vertices $\mathbf{V}$ and a set of edges $\mathbf{E}$, such that each edge in $\mathbf{E}$ is a connection between a pair of vertices in $\mathbf{V}$. The number of vertices is written $|\mathbf{V}|$, and the number of edges is written $|\mathbf{E}|$. $|\mathbf{E}|$ can range from zero to a maximum of $|\mathbf{V}|^2 - |\mathbf{V}|$.

A graph whose edges are not directed is called an undirected graph, as shown in part (a) of the following figure. A graph with edges directed from one vertex to another (as in (b)) is called a directed graph or digraph. A graph with labels associated with its vertices (as in (c)) is called a labeled graph. Associated with each edge may be a cost or weight. A graph whose edges have weights (as in (c)) is said to be a weighted graph. These are depicted in Figure 13.1.

An edge connecting vertices $a$ and $b$ is written $(a, b)$. Such an edge is said to be incident with vertices $a$ and $b$. The two vertices are said to be adjacent. If the edge is directed from $a$ to $b$, then we say that $a$ is adjacent to $b$, and $b$ is adjacent from $a$. The degree of a vertex is the number of edges it is incident with. For example, vertex $e$ in Figure 13.2 has a degree of three.

In a directed graph, the out degree for a vertex is the number of neighbours adjacent from it (or the number of edges going out from it), while the in degree is the number of neighbours adjacent to it (or the number of edges coming in to it). In Figure 13.1 (c), the in degree of vertex 1 is two, and its out degree is one.

A sequence of vertices $v_1, v_2, ..., v_n$ forms a path of length $n-1$ if there exist edges from $v_i$ to $v_{i+1}$ for $1 \leq i < n$. A path is a simple path if all vertices on the path are distinct. The length of a path is the number of edges it contains. A cycle is a path of length three or more that connects some vertex $v_1$ to itself. A cycle is a simple cycle if the path is simple, except for the first and last vertices being the same. These are depicted in Figure 13.3.

An undirected graph is a connected graph if there is at least one path from any vertex to any other. The maximally connected subgraphs of an undirected graph are called connected components. For example, Figure 13.4 shows an undirected graph with three connected components.

A graph with relatively few edges is called a sparse graph, while a graph with many edges is called a dense graph. A graph containing all possible edges is said to be a complete graph. A subgraph $\mathbf{S}$ is formed from graph $\mathbf{G}$ by selecting a subset $\mathbf{V}_s$ of $\mathbf{G}$’s vertices and a subset $\mathbf{E}_s$ of $\mathbf{G}$ ’s edges such that for every edge $e \in \mathbf{E}_s$, both vertices of $e$ are in $\mathbf{V}_s$. Any subgraph of $V$ where all vertices in the graph connect to all other vertices in the subgraph is called a clique. See Figure 13.5 for examples of these kinds of graphs.

A graph without cycles is called an acyclic graph. Thus, a directed graph without cycles is called a directed acyclic graph or DAG. They are shown in Figure 13.6.

A free tree is a connected, undirected graph with no simple cycles. An equivalent definition is that a free tree is connected and has $|\mathbf{V}| - 1$ edges.