Search topics

Search

Represent a network in a matrix

Start a set of 8
Step 3 of 8

Encode the full undirected multigraph

In order A, B, C, D, record two AB edges in both AB cells, one BC edge in both BC cells, and the loop at C once on the diagonal. All other entries are zero. D retains an all-zero row and column. The graph and matrix carry the same incidence information

\[M=\begin{bmatrix}0&2&0&0\\2&0&1&0\\0&1&1&0\\0&0&0&0\end{bmatrix}\]
Year 11, VCE Units 1 & 2, Chapter 2, 2 difficulty levels, No calculatorBuild a worksheet

Undirected adjacency matrices

State vertex order and the loop convention before translating a graph. Here each loop is recorded once on the diagonal

  1. Fix both orders Use the same declared vertex order for the rows and columns. Entry aᵢⱼ is read at row i, column j
  2. Record multiplicity An off-diagonal entry counts all direct edges joining that vertex pair, not merely whether a connection exists
  3. Mirror undirected edges For distinct vertices, each edge is represented in both mirrored cells. Those two cells still describe one edge \(\displaystyle a_{ij}=a_{ji}\)
  4. Count each loop once on the diagonal In this course and the retained generators, aᵢᵢ is the number of loops at vertex i. Some sources use doubled diagonal entries; state and follow the convention rather than mixing them
  5. An isolated vertex remains visible Its entire row and column are zero, but the vertex is still included in the matrix order

Worked example

Use order A, B, C, D for the graph with two AB edges, one BC edge, one loop at C and isolated D. Construct its adjacency matrix

\[M=\begin{bmatrix}0&2&0&0\\2&0&1&0\\0&1&1&0\\0&0&0&0\end{bmatrix}\]
  1. \(\displaystyle a_{12}=a_{21}=2\)Record the two AB edges in both mirrored cells
  2. \(\displaystyle a_{23}=a_{32}=1\)Record the single BC edge in both mirrored cells
  3. \(\displaystyle a_{33}=1\)Record the loop once on the diagonal. All unlisted entries are zero
  4. \(\displaystyle M=\begin{bmatrix}0&2&0&0\\2&0&1&0\\0&1&1&0\\0&0&0&0\end{bmatrix}\)Keep the all-zero row and column for isolated D

Common mistakes

Collapsing repeated edges
✕\(\displaystyle a_{12}=1\)✓\(\displaystyle a_{12}=2\)
For the worked graph there are two separate AB edges, not a single yes/no connection
Adding loops automatically
✕\(\displaystyle a_{ii}=1\text{ always}\)✓\(\displaystyle a_{ii}=\text{actual loop count}\)
A vertex or an indirect return route does not create a loop
Doubling the diagonal convention
✕\(\displaystyle a_{33}=2\)✓\(\displaystyle a_{33}=1\)
For the worked graph the loop is entered once. Degree counts it twice, but the adjacency convention is different

Difficulty levels

introConstruct a whole undirected adjacency matrix
standardConstruct missing entries or a requested entry of an undirected adjacency matrix

Questions about this topic

Why is the matrix square?+

Every vertex appears once in the row order and once in the column order, so n vertices give n rows and n columns

Why use the same order for rows and columns?+

It makes the vertex labels and symmetry unambiguous. A different consistent order changes positions, not the graph

Why can a diagonal entry be zero?+

It means no loop at that vertex, not that the vertex is absent

What if my textbook doubles loop entries?+

State its convention and follow it consistently. This course and these practice generators record each loop once on the diagonal; degree then adds the diagonal entry to the row sum

Are directed matrices practised here?+

No. This Specialist section serves only the existing undirected intro and standard variants

Can I use a calculator?+

No. This topic is practised without a calculator

Which year level and chapter is this?+

Year 11, VCE Units 1 & 2, Specialist Mathematics, chapter 2: Graph theory

In this chapter

Count the vertices, edges and loops of a graphRepresent a network in a matrixIdentify the network a connection matrix describesDegrees, the degree sum, and even and odd vertices2B Graph families and structure: Graph types, subgraphs, connection models and method selectionConnected graphs and bridgesIdentify isomorphic graphsTrees and spanning treesGraph families and tree conditionsPlanar graphs and drawings in planar formFaces and Euler's formula2C Planarity and graph proofs: Graph types, subgraphs, connection models and method selectionClassify a route: walk, trail, path, circuit or cycleEulerian trails and circuits: existence and identificationHamiltonian paths and cycles