Skip to content

1.2 Representations of a graph

Part 1 · Graphs · Chapter 1 · Chapter 1: Graphs · Lecture notes, volume 1 (PDF) · Exercises: Graphs · App: Graph search: BFS and DFS

Definition 1.7: adjacency matrix

The adjacency matrix of a directed graph \(G=(N,A)\) is the \(n \times n\) matrix \(\mat{M}\) with entries

\[ m_{ij}=\begin{cases} 1 & \text{if } (i,j) \in A,\\ 0 & \text{otherwise,}\end{cases} \qquad \forall i,j \in \{1,2,\dots,n\}. \]

The adjacency matrix of an undirected graph has \(m_{uv}=m_{vu}=1\) for every edge \(\{u,v\}\): it is symmetric.

Definition 1.8: node–arc incidence matrix

Let \(G=(N,A)\) be a directed graph with arcs \(a_1,a_2,\dots,a_m\). The node–arc incidence matrix is the \(n \times m\) matrix \(\mat{B}\) with one row per node and one column per arc, whose entries are

\[ b_{ik}=\begin{cases} +1 & \text{if } i \text{ is the tail of } a_k,\\ -1 & \text{if } i \text{ is the head of } a_k,\\ 0 & \text{otherwise,}\end{cases} \qquad \forall i \in \{1,2,\dots,n\},~ \forall k \in \{1,2,\dots,m\}. \]

  • Every column of \(\mat{B}\) has exactly one \(+1\) (the tail) and one \(-1\) (the head), so the sum of the rows of \(\mat{B}\) is the zero vector.

  • Row \(i\) has a \(+1\) for every arc of \(\delta^+(i)\) and a \(-1\) for every arc of \(\delta^-(i)\): it has \(\deg^+(i)+\deg^-(i)\) nonzero entries.

  • The vertex–edge incidence matrix of an undirected graph has a \(1\) in both endpoints of every edge.

Example 1.4: the matrices of the reference graph

The adjacency matrix \(\mat{M}\) and the node–arc incidence matrix \(\mat{B}\) of the reference graph of Example 1.2 are shown with the index of each row (a node) and of each column (a node in \(\mat{M}\), an arc in \(\mat{B}\)):

\[ \mat{M}:\quad \begin{array}{c|rrrrrr} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & 0 & 1 & 1 & 0 & 0 & 0\\ 2 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & 0 & 1 & 0 & 0 & 1 & 0\\ 4 & 0 & 0 & 1 & 0 & 0 & 1\\ 5 & 0 & 0 & 0 & 1 & 0 & 1\\ 6 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array} \]
\[ \mat{B}:\quad \begin{array}{c|rrrrrrrrr} & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 & a_9\\ \hline 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 2 & -1 & 0 & 1 & -1 & 0 & 0 & 0 & 0 & 0\\ 3 & 0 & -1 & 0 & 1 & 1 & -1 & 0 & 0 & 0\\ 4 & 0 & 0 & -1 & 0 & 0 & 1 & 1 & -1 & 0\\ 5 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 1\\ 6 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1\\ \end{array} \]

For example, the column of \(a_6=(4,3)\) has \(+1\) in row \(4\) (the tail) and \(-1\) in row \(3\) (the head). Row \(6\) of \(\mat{M}\) is zero, because node \(6\) has no successors.

Definition 1.9: adjacency lists and arc list

Let \(G=(N,A)\) be a directed graph.

  • The adjacency lists store, for every node \(i\), the list \(L(i)\) of its successors, that is, the heads of the arcs of \(\delta^+(i)\). In this module every list is sorted by increasing index.

  • The arc list stores two arrays of length \(m\), with the tail and the head of every arc.

For an undirected graph the list \(L(v)\) contains the neighbourhood \(N(v)\), and every edge appears in two lists.

Example 1.5: the lists of the reference graph

The adjacency lists and the arc list of the reference graph are:

\(i\) \(L(i)\)
\(1\) \(2,~3\)
\(2\) \(4\)
\(3\) \(2,~5\)
\(4\) \(3,~6\)
\(5\) \(4,~6\)
\(6\) (empty)

arc \(a_1\) \(a_2\) \(a_3\) \(a_4\) \(a_5\) \(a_6\) \(a_7\) \(a_8\) \(a_9\)
tail \(1\) \(1\) \(2\) \(3\) \(3\) \(4\) \(4\) \(5\) \(5\)
head \(2\) \(3\) \(4\) \(2\) \(5\) \(3\) \(6\) \(4\) \(6\)

The lists of the underlying undirected graph are \(L(1)=\{2,3\}\), \(L(2)=\{1,3,4\}\), \(L(3)=\{1,2,4,5\}\), \(L(4)=\{2,3,5,6\}\), \(L(5)=\{3,4,6\}\) and \(L(6)=\{4,5\}\).

1.2.1 Space and access time

  • The table compares the four representations of a directed graph. The space is the number of stored entries; the two operations are the test of an arc and the scan of the successors of a node.
representation space is \((i,j) \in A\)? successors of \(i\)
adjacency matrix \(n^2\) \(O(1)\) \(O(n)\)
node–arc incidence matrix \(n\,m\) \(O(m)\) \(O(m)\)
arc list \(2\,m\) \(O(m)\) \(O(m)\)
adjacency lists \(n+m\) \(O(\deg^+(i))\) \(O(\deg^+(i))\)

  • For the reference graph the four representations store \(36\), \(54\), \(18\) and \(15\) entries.

  • A simple directed graph has \(m \le n(n-1)\). In the networks of the applications \(m\) is much smaller than \(n^2\) (the graph is sparse), and the adjacency lists are the representation of choice for the algorithms.

1.2.2 The incidence matrix and flow conservation

  • Given a value \(x_{ij}\) for every arc, row \(i\) of \(\mat{B}\vet{x}\) is what leaves node \(i\) minus what enters it:

    \[ (\mat{B}\vet{x})_i=\sum_{(i,j) \in \delta^+(i)} x_{ij} \;-\; \sum_{(j,i) \in \delta^-(i)} x_{ji}, \qquad \forall i \in N. \]

  • With \(x_{ij}=1\) for every arc of the reference graph, \(\mat{B}\vet{x}\) is the vector of the differences \(\deg^+(i)-\deg^-(i)\):

    \[ \mat{B}\vet{x}=(2,\,-1,\,0,\,0,\,1,\,-2)' . \]

The node–arc incidence matrix has \(+1\) in the tail and \(-1\) in the head of every arc; the adjacency lists store a graph in \(n+m\) space and give the successors of a node in \(O(\deg^+(i))\) time.

Next: 1.3 Connectivity