Graph Theory → Computational Representation

Let \(G = (V, A)\) be a graph with \(V = \{v_1, v_2, \dots, v_n\}\). The adjacency matrix of \(G\) is the matrix

\[ M = (m_{ij}) \in \mathbb{R}^{n \times n} \] defined by

m_{ij} = \begin{cases} 1, & \text{if there exists an edge (or arc) from } v_i \text{ to } v_j, \\ 0, & \text{otherwise.} \end{cases}

Each entry \(m_{ij}\) indicates whether the vertices \(v_i\) and \(v_j\) are adjacent in the graph.

Arcs in the graph (from the figure):

A → B (q) A → C (w) A → D (r) B → C (t) B → E (u) C → D (y) D → E (i)

Vertex order: (A, B, C, D, E)

Let G = (V, A) with V = {A, B, C, D, E}. The adjacency matrix of G is:

M= \begin{pmatrix} 0&1&1&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0\\ 0&0&0&0&1\\ 0&0&0&0&0 \end{pmatrix}

Each entry \(m_{ij}\) indicates whether there exists an arc from vertex \(v_i\) to vertex \(v_j\):

Examples (matching the graph):
\(m_{AB}=1\) indicates the arc A → B (q).
\(m_{EA}=0\) indicates that there is no arc E → A.

Discrete Mathsfor Engineers