7.3. Representing Graphs#

By now, we have know what graphs are, their many properties, and how to draw them. But, how can we make use of graphs in computers? Just like integers, which have Integer Representations, graphs also have special representations on computers.

Consider a graph \(G = (V,E)\) with

\[\begin{split} V &= \{a,b,c,d,e\} \\ E &= \{\{a,b\}, \{b,c\}, \{a,d\}, \{c,e\}, \{d,b\}, \{d,c\}, \{d,e\}, \{e,a\}\} \end{split}\]

We could directly encode these two sets. Right?

V = set(['a','b','c','d','e']);
E = set();
E.add(frozenset(['a', 'b']));
E.add(frozenset(['b', 'c']));
E.add(frozenset(['a', 'd']));
E.add(frozenset(['c', 'e']));
E.add(frozenset(['d', 'b']));
E.add(frozenset(['d', 'c']));
E.add(frozenset(['d', 'e']));
E.add(frozenset(['e', 'a']));

print(V)
print(E)

{'d', 'c', 'a', 'e', 'b'}
{frozenset({'a', 'e'}), frozenset({'a', 'b'}), frozenset({'d', 'b'}), frozenset({'c', 'b'}), frozenset({'e', 'c'}), frozenset({'d', 'e'}), frozenset({'d', 'c'}), frozenset({'a', 'd'})}

Sure… but should we do this? What even is a frozenset? Is there a better way?

Remember that one of the fundamental aspects of graphs is determining whether or not one vertex is adjacent to another vertex. Can we determine that easily or quickly from E encoded as a big set of sets?

7.3.1. Adjacency Lists#

Adjacency lists are very simple data structures for encoding a graph. It is essentially a dictionary of lists. Each vertex in the graph is a key in the dictionary. The value corresponding to the key is the list of vertices adjacent to the key.

../_images/graph-adjlist.svg

The adjacency list of the above graph is:

\[\begin{split} \{ &\\ &(1, \{2,3,4\}),\\ &(2, \{1,3,5\}),\\ &(3, \{1,2,4\}),\\ &(4, \{1,5\}),\\ &(5, \{2,4\})\\ \} & \end{split}\]

In practice, an adjacency list may be implemented as a dictionary of lists, a dictionary of sets, a list of lists, a list of sets, etc. It depends on the facilities of the particular programming language you are using.

In python, an adjacency list is easily implemented as a dictionary of lists. Querying the structure for answers of connectivity is then very easy.

d = {1: [2,3,4],
     2: [1,3,5],
     3: [1,2,4],
     4: [1,5],
     5: [2,4] }

if (4 in d[1]) :
    print("1 is adjacent to 4")
else:
    print("1 is not adjacent to 4")

if (3 in d[5]) :
    print("3 is adjacent to 5")
else:
    print("3 is not adjacent to 5")

1 is adjacent to 4
3 is not adjacent to 5

In practice, the list of vertices adjacent to a particular vertex can be implemented as a

Notice that this same data structure immediately encodes a directed graph as well. For a directed edge \((u,v)\) \(u\) is adjacent to \(v\), but \(v\) is not necessarily adjacent to \(u\). Thus, we be \(v\) in the adjacency list of \(u\), but \(u\) is not in the adjacency list of \(v\).

Adjacency lists

../_images/graph-adjlist2.svg

Give the adjacency list encoding the above graph. Use Python syntax if you’d like.

Adjacency lists

d = {1: [3,4],
     2: [4],
     3: [2],
     4: [],
     5: [1,3,4] }

7.3.2. Adjacency Matrix#

A more explicit representation compared to the adjacency list is an adjacency matrix. In this representation, every possible pair of vertices is represented in a matrix. The value of a particular entry in the matrix designates whether an edge exists between the pair of vertices or not. This is not dissimilar from Relations as Matrices.

Given a graph \(G = (V,E)\) of order \(n\), list the vertices in some order: \(v_1, v_2, \ldots, v_n\). The adjacency matrix \(A_G\) of \(G\), with respect to this order of vertices, is an \(n \times n\) zero-one matrix. Recall Section 3.3.3. \(A_G\) is defined as:

\[\begin{split} A_G = (a_{i,j}) \qquad a_{i,j} = \left\{ \begin{array}{l} 1, \text{ if $v_i$ and $v_j$ are adjacent} \\ 0, \text{ otherwise} \end{array}\right. \end{split}\]

Adjacency matrices are best used for graphs with many edges. Otherwise, the matrix will be mostly 0s!

Tip

For undirected graphs, the adjacency matrix is always symmetric.

Let’s do one.

Adjacency matrix

../_images/graph2.svg

The adjacency matrix for this graph with the natural ordering \(1, 2, 3, 4, 5\) is:

\[\begin{split} \begin{bmatrix} 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \end{split}\]

Adjacency matrices give us meaningful properties of a graph with a very quick glance. For example, all loops are always along the matrix’s main diagonal.

Adjacency matrices also easily extended to encode multigraphs. We haven’t spend much time talking about multigraphs, so let’s give a very simple example.

../_images/multigraph1.svg

Fig. 7.64 An undirected multigraph for \(4\) vertices and \(6\) edges.#

In this multigraph there are two edges between \(1\) and \(2\), and 3 edges between \(3\) and \(4\). What does your intuition tell you about encoding this as an adjacency matrix?

Rather than the adjacency matrix being a zero-matrix, it will be a matrix of non-negative integers. The integer in \(a_{i,j}\) encodes how many edges are between \(v_i\) and \(v_j\).

Thus, the adjacency matrix for the multigraph in Fig. 7.64 is:

\[\begin{split} \begin{bmatrix} 0 & 2 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 3 & 0 \\ \end{bmatrix} \end{split}\]

Just like adjacency lists, adjacency matrices can easily be used to encode directed graphs. \(a_{i,j}\) encodes when an edge exists from \(v_i\) to \(v_j\). For directed graphs, adjacency matrices are not symmetric.

Adjacency lists

../_images/graph-adjlist2.svg

Give the adjacency matrix encoding the above graph.

Adjacency lists

\[\begin{split} \begin{bmatrix} 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ \end{bmatrix} \end{split}\]

7.3.3. Exercises#

Exercise 7.7

Give the adjacency matrix for the complete graph \(K_5\).

Exercise 7.8

For a directed graph encoded as an adjacency matrix, how can you easily determine which vertices are sinks? How can you easily determine which vertices are sources?