Identify the network a connection matrix describes practice questions | General Mathematics (Year 12, VCE Units 3 & 4, Graphs and networks, Adjacency matrices)

Reading a connection matrix

A connection matrix has one row and one column for each vertex in a declared order. Each entry records direct connections from the row vertex to the column vertex, including loops and repeated connections

M_{ij}=\text{number of direct connections from row }i\text{ to column }j

Fix the vertex order Use the declared order for both rows and columns before reading any connection \(\displaystyle (A,B,C)\text{ gives rows and columns }1,2,3\)
Read row to column An off-diagonal entry in row i and column j records a direct connection from vertex i to vertex j. \(\displaystyle M_{23}=2\Rightarrow 2\text{ to }3\text{ has two direct connections}\)
Read the diagonal as loops A leading-diagonal entry records a connection from a vertex to itself only when a loop is present \(\displaystyle M_{22}=1\Rightarrow\text{one loop at vertex }2\)
Check mirrored entries Equal mirrored entries give equal counts in the two directions. Unequal entries give different counts; check every mirrored pair before calling the whole matrix symmetric \(\displaystyle M_{12}=M_{21}=1\Rightarrow\text{one connection in each direction}\)

Worked example

The vertex order is A, B, C. Use the connection matrix below to identify the connections involving B and count the direct connections arriving at B, counting the loop once

M=\begin{bmatrix}0&1&0\\1&1&2\\0&2&0\end{bmatrix}

\(\displaystyle M_{22}=1\)The entry on the diagonal shows one loop at B.
\(\displaystyle M_{12}=M_{21}=1,\quad M_{23}=M_{32}=2\)The equal mirrored entries show one connection between A and B and two connections between B and C, each in both directions
\(\displaystyle M_{12}+M_{22}+M_{32}=1+1+2=4\)Adding column 2 counts the connection at B, its loop and the two connections from C.
\(\displaystyle \text{B has }4\text{ direct connections}\)The total includes the loop once because its matrix entry is 1.

Common mistakes

Treating the diagonal as automatic connections

✕\(\displaystyle M_{ii}=1\text{ for every vertex}\)✓\(\displaystyle M_{ii}=1\text{ only when a loop at vertex }i\text{ is present}\)

A diagonal entry is non-zero only when the network includes a loop at that vertex

Recording repeated connections as one

✕\(\displaystyle M_{23}=1\text{ when two direct connections join vertices 2 and 3}\)✓\(\displaystyle M_{23}=2\text{ when two direct connections join vertices 2 and 3}\)

The entry records the number of direct connections, not only whether at least one connection exists

Reversing the row and column

✕\(\displaystyle M_{23}=1\Rightarrow 3\to2\)✓\(\displaystyle M_{23}=1\Rightarrow 2\to3\)

The row names the starting vertex and the column names the ending vertex

Difficulty levels

introMatch a small undirected network with its connection matrix

standardRead one-way links, repeated connections and vertex counts from a four-vertex matrix

challengeInterpret a directed five-vertex matrix containing a loop and repeated connection

examSelect the network whose direct connections match every matrix entry

Questions about this topic

What does a diagonal entry mean in a connection matrix?+

It records a loop from a vertex to itself. It is zero when no loop is present; a vertex reaching itself indirectly is not recorded on the diagonal of the direct connection matrix

How are repeated direct connections recorded?+

The entry is the number of direct connections between the row vertex and the column vertex. For example, two direct connections are recorded as 2.

How can a matrix show a two-way connection?+

A two-way connection contributes equally to the two mirrored entries. Equal non-zero entries show equal counts in the two directions; they can also arise from separately stated one-way links in both directions

Can I use a calculator?+

No. This topic is practised without a calculator

Which year level and chapter is this?+

Year 12, VCE Units 3 & 4, General Mathematics, chapter 13: Graphs and networks

In this chapter

Count the vertices, edges and loops of a graph Degrees, the degree sum, and even and odd vertices Graph types, subgraphs, connection models and method selection Connected graphs and bridges Identify isomorphic graphs Planar graphs and drawings in planar form Faces and Euler's formula Represent a network in a matrix Identify the network a connection matrix describes Classify a route: walk, trail, path, circuit or cycle Eulerian trails and circuits: existence and identification Hamiltonian paths and cycles Read a weighted graph The shortest path by inspection Dijkstra's algorithm for shortest distances and routes Trees and spanning trees Minimum spanning trees by Prim's and Kruskal's algorithms A full network investigation