Represent a network in a matrix

Vertex order

\(\displaystyle A, B, C\)

Three towns Ash (A), Birch (B) and Cedar (C) are joined by two-way roads. Two direct roads join A to B, one direct road joins B to C, and one direct road joins A to C. In vertex order A, B, C, what is the entry in row B, column A?

A link with no arrowhead is two-way. Move the Q to R slider from 0 to 2 and watch the two cells for Q and R, then move the track count and watch the cells for P and Q

As the Q to R link went from none to one-way to two-way, what happened to the two cells for Q and R?

Build a connection matrix

A connection matrix has one row and one column for each vertex, in the declared order. Each entry counts direct links from the row vertex to the column vertex

1. 1Write one row for each town For towns A, B and C, two two-way roads join A and B, one joins A and C, and one joins B and C. Keep A, B, C as both orders. The two roads between A and B give the mirrored 2s; no town has a loop, so the diagonal entries are zero \(\displaystyle M=\begin{bmatrix}0&2&1\\2&0&1\\1&1&0\end{bmatrix}\)
2. 2Use one vertex order Use the same declared vertex order for the rows and the columns \(\displaystyle \text{order of }M=3\times 3\)
3. 3Count direct connections Enter the number of direct links between the named row and column vertices \(\displaystyle M_{21}=2\)
4. 4Record loops on the diagonal A loop is recorded on the leading diagonal. The town network above has no loop at B, so its entry is 0; one loop at B would make that entry 1. \(\displaystyle M_{22}=0\quad\text{for the town network}\)
5. 5Mirror two-way connections The two roads between A and B give 2 in both mirrored positions. Each one-way link contributes only from its start to its end \(\displaystyle M_{12}=M_{21}=2\)

Vertex order

\(\displaystyle K, L, M, N\)

One-way track

\(\displaystyle L\to N\)

Loop at M (a track from M back to M)

\(\displaystyle M\to M\)

Courier depots K, L, M and N are joined by tracks. Two tracks join K to L, one track joins L to M, one track joins M to N, and one track runs one-way from L to N. There is also a loop at M. In vertex order K, L, M, N, find the sum of row M (links leaving M)

List each link that starts at M, including the loop, then add the counts

Vertex order

\(\displaystyle K, L, M, N\)

One-way track

\(\displaystyle L\to N\)

Loop at M (a track from M back to M)

\(\displaystyle M\to M\)

For the same depot network, find the sum of column N (links arriving at N)

List each link that ends at N, then add the counts

Tracks between K and L

\(\displaystyle 2\)

Vertex order

\(\displaystyle K, L, M, N\)

Which entry correctly records the two tracks between K and L?