topic badge

4.02 Network representations

Lesson

Network representations

We will start this lesson by exploring some situations that can be represented by graphs or networks.

Examples

Example 1

A beach volleyball social competition team can have 3 players on the court at any time. The team has 5 players at the tournament. The table shows 3 combinations that the coach has already used in the first three games.

GamesPlayers chosen
1Ryan, Jimmy, Lucy
2Lucy, Beth, Ellie
3Ellie, Ryan, Jimmy
a

Which of the following graphs shows the combinations of players that have already played together?

A
A graph that shows combinations of players. Ask your teacher for more information.
B
A graph that shows combinations of players. Ask your teacher for more information.
C
A graph that shows combinations of players. Ask your teacher for more information.
D
A graph that shows combinations of players. Ask your teacher for more information.
Worked Solution
Create a strategy

Choose the graph where the players for each game are connected to one another.

Apply the idea

For game 1, Ryan, Jimmy, and Lucy played together. So Ryan, Jimmy, and Lucy should be connected to form a triangle. This is satisfied by options B and C.

For game 2, Lucy, Beth, and Ellie played together. So Lucy, Beth, and Ellie should be connected to form a triangle. This is again satisfied by options B and C.

In game 3, Ellie, Ryan and Jimmy played together. So Ellie, Ryan and Jimmy should be connected to form a triangle. This is satisfied by option C only.

So the correct answer is option C.

b

There is one more game left in the tournament. Who should the coach choose to play so that every team member has played with every other team member at least once?

A
Beth
B
Jimmy
C
Lucy
D
Ryan
E
Ellie
Worked Solution
Create a strategy

Find the names that are not connected by a line.

Apply the idea
A graph that shows combinations of players. Ask your teacher for more information.

The graph should show a line connecting every player's name to satisfy the condition that every team member has played with every other team member at least once.

Ryan and Beth, as well as Jimmy and Beth, are not connected by a line. This means that Beth, Jimmy, and Ryan have not yet played together.

So the coach should choose Beth, Jimmy, and Ryan. The correct answers are options A, B, and D.

Example 2

The following table lists the amount of time it takes to queue up for three rides at an amusement park, and the amount of time it takes to travel between them:

CarouselPirate ShipHaunted House
Carousel354
Pirate Ship5136
Haunted House4611

Represent this information using a network.

Worked Solution
Create a strategy

Let the vertices represent the rides and the edges be weighted with the times.

Apply the idea
A weighted undirected network with vertices C H P and a loop at each vertex. Ask your teacher for more information.

We use an undirected network since the table is symmetrical.

Vertex C represents the carousel, vertex P represents the Pirate Ship, and vertex H represents the Haunted House.

Since each ride has a time to get from the end to the beginning of its own queue, each vertex will need a loop with the time to get to through its own queue.

Idea summary

Some situations that can be represented by graphs or networks. Vertices can represent objects or places, edges can represent paths or connections, and weights can represent numerical data that connects the vertices like times or distances.

Adjacency matrices for undirected networks

It is sometimes useful to use an adjacency matrix to represent a network. This is a square matrix of numbers, with a row and a column for each vertex, that records how many connections there are between the vertices. For an undirected network, the entry for a particular row and column represents the number of edges connecting the matching vertices.

This image shows a simple network with vertices A, B, C, D, E. Ask your teacher for more information.

Here’s a simple network (no loops and no multiple edges) with 5 vertices.

Now we can create a matrix, with a row and a column for each vertex:

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \\ E \end{matrix} & \begin{bmatrix} \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \end{bmatrix} \end{matrix}

Then we put the number edges connecting two vertices as the corresponding table entry. Let’s start by filling out the first row by putting a 1 if it is connected to A, and a 0 if it isn’t.

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \\ E \end{matrix} & \begin{bmatrix} \, 0 &\, 1 &\, 1 &\, 1 &\, 1 \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \end{bmatrix} \end{matrix}

0 comes first because A isn’t connected to itself (there’s no loop at A), and A is connected to B, \, C, \, D, and E, so we put a 1 for each other entry in the table.

Since these edges are undirected, we can fill out the first column with the same numbers - if A is connected to B, then B is connected to A, and so on:

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \\ E \end{matrix} & \begin{bmatrix} \, 0 &\, 1 &\, 1 &\, 1 &\, 1 \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \end{bmatrix} \end{matrix}

Now to fill out the second row, we notice that B is connected to A (already recorded), not itself (no loop), and it is connected to C, \, D, and E:

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A\\ B\\ C\\D\\E \end{matrix} & \begin{bmatrix} \, 0 &\, 1 &\, 1 &\, 1 &\, 1 \\ \, 1 &\, 0 &\, 1 &\, 1 &\, 1 \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \end{bmatrix} \end{matrix}

We then record the remaining connections between C, \, D, and E in the same way:

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A\\ B\\ C\\ D \\E \end{matrix} & \begin{bmatrix} \, 0 &\, 1 &\, 1 &\, 1 &\, 1 \\ \, 1 &\, 0 &\, 1 &\, 1 &\, 1 \\ \, 1 &\, 1 &\, 0 &\, 1 &\, 0 \\ \, 1 &\, 1 &\, 1 &\, 0 &\, 0 \\ \, 1 &\, 1 &\, 0 &\, 0 &\, 0 \end{bmatrix} \end{matrix}

In the completed matrix, notice that:

  • The diagonal running top-left to bottom-right (called the main diagonal) has only 0's. This indicates that no edge is connected to itself in the network - there are no loops.

  • The numbers off the main diagonal are only 0's and 1's. This indicates that there are no multiple edges.

All adjacency matrices representing simple networks will have these features.

As an added bonus, for a network with no loops, the sum of all the entries in a row (or column) gives us the degree of the corresponding vertex - we can tell from the table that C and E have degree 2, \, D has degree 3, and A and B have degree 4.

Examples

Example 3

Consider the following network:

An undirected network with vertices P, Q, R, S and edges Q  P, P R, and R S. With a loop at P and at S.
a

Fill in the adjacency matrix for this network:\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Worked Solution
Create a strategy

For each box, write the number of edges that connect the vertex in that row and the vertex in that column.

Apply the idea

The given network is an undirected network, so each edge connects in both directions. This means that the adjacency matrix is symmetric about the main diagonal.

Vertex P is connected to itself and vertices Q and R. So we write a 1 under P, \, Q, and R, and a 0 under S.

\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} \,\, 1 &\, 1 \,&\, 1 \,&\, 0 \,\, \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Next, we fill out the first column with the same numbers as the first row in the same order.

\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} \,\, 1 &\, 1 \,&\, 1 \,&\, 0 \,\, \\ \,\, 1 &⬚ &⬚ &⬚ \\ \,\, 1 &⬚ &⬚ &⬚ \\ \,\, 0 &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

To fill out the second row, we notice that Q is only connected to P. So we put a 1 under P and 0s for the rest. We can then write the same numbers in column Q.

\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} \,\, 1 &\, 1 \,&\, 1 \,&\, 0 \,\, \\ \,\, 1 &\, 0 \,&\, 0 \,&\, 0 \,\, \\ \,\, 1 &0 &⬚ &⬚ \\ \,\, 0 &0 &⬚ &⬚ \end{bmatrix} \end{matrix}

Continuing in the same way, since R and S are connected, and there is a loop at vertex S, we have the following adjacency matrix for the network.

\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} \,\, 1 &\, 1 \,&\, 1 \,&\, 0 \,\, \\ \,\, 1 &\, 0 \,&\, 0 \,&\, 0 \,\, \\ \,\, 1 &\, 0 \,&\, 0 \,&\, 1 \,\, \\ \,\, 0 &\, 0 \,&\, 1 \,&\, 1 \,\, \end{bmatrix} \end{matrix}

b

What is the degree of vertex P?

Worked Solution
Create a strategy

Add the entries in the column corresponding to the vertex in the adjacency matrix, double the number on the main diagonal for vertices with loops.

Apply the idea

The network has a loop at P, so we first need to double the number in the first row.

\displaystyle \text{Degree}\displaystyle =\displaystyle 2\times 1+1+1+0Use the numbers from the first column
\displaystyle =\displaystyle 4Evaluate
Idea summary

The degree of a vertex is the number of edges connected to that vertex. Loops are counted twice.

An adjacency matrix is a square array of numbers, a row and a column for each vertex, that records how many connections there are between the vertices.

For undirected networks, the element for a particular row and column represents the number of edges connecting the matching vertices.

Adjacency matrices for directed and weighted graphs

Now for a directed network, the entry in a particular row and column indicates the number of edges going from the corresponding row vertex to the corresponding column vertex.

Here’s a directed, non-simple network with 5 vertices and its corresponding adjacency matrix:

A non-simple network with vertices A, B, C, D, E and its equivalent adjacency matrix. Ask your teacher for more information.

This matrix looks a little different from the last one. Notice that:

  • The matrix is not symmetrical across the main diagonal (an edge from A to B can exist without an edge from B to A),

  • There is a 1 on the main diagonal because it is not a simple graph as there is a loop at C, and

  • There’s a 2 in the table because there are two edges from D to E.

While an asymmetrical matrix means the network is directed, there are directed networks that will produce a symmetrical adjacency matrix.

For directed networks, we can add all of the elements in the adjacency matrix to determine the number of edges on the graph.

When a network contains loops, there will be non-zero values on the main diagonal of the adjacency matrix. Each loop is counted as the vertex as having one connection to itself.

When we calculate the degree of a vertex by adding the elements in a row (or column) of the adjacency matrix, numbers on the main diagonal need to be doubled because loops are counted twice.

In the graph above the degree of vertex C is 4, because the loop is considered to be two edges into vertex C. However if we add the numbers in row C of the corresponding adjacency table we only get 3. The 1 on the main diagonal must be counted twice as it represents the loop at C.

Adjacency matrices can be used for weighted graphs where each element in the matrix represents the weight assigned to that edge.

This image shows a weighted directed network with vertices A, B, C, D. Ask your teacher for more information.

Setting up the matrix template we need, 4 vertices means it will be a 4 \times 4 matrix.

\begin{matrix} & \begin{matrix} A&B&C&D\end{matrix}\\ \begin{matrix} A\\ B\\ C\\ D \end{matrix} & \begin{bmatrix} \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, \end{bmatrix} \end{matrix}

From vertex A, there are 2 edges. The edge connected to B has weight 2, and the edge to 2 has weight 4.

\begin{matrix} & \begin{matrix} A&B&C&D\end{matrix}\\ \begin{matrix} A\\ B\\ C\\ D \end{matrix} & \begin{bmatrix} \, 0 \, &\,2\, &\,4\, &\,0\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, \end{bmatrix} \end{matrix}

From vertex B there is just one edge. It goes to C with weight 3.33.

\begin{matrix} & \begin{matrix} A&B&C&D\end{matrix}\\ \begin{matrix} A\\ B\\ C\\ D \end{matrix} & \begin{bmatrix} 0 &2 &4 &0 \\ 0 &0 &3.33 &0 \\ \, . &\,\, . &\,\, . &\,\, . \\ \, . &\,\, . &\,\, . &\,\, . \end{bmatrix} \end{matrix}

From vertex C there is just one edge. It goes to D with weight 4.

From vertex D there are two edges. One of them is a loop and this gets written in the D to D position.

\begin{matrix} & \begin{matrix} A&B&C&D\end{matrix}\\ \begin{matrix} A\\ B\\ C\\ D \end{matrix} & \begin{bmatrix} 0 &2 &4 &0 \\ 0 &0 &3.33 &0 \\ 0 &0 &0 &4 \\ 0 &0 &3.5 &2 \end{bmatrix} \end{matrix}

If we know that we have a directed or undirected network, the information in the adjacency matrix is enough for us to draw a graph to represent the network.

Here’s a table with 6 rows and columns (so there are 6 vertices in the network), and we are also told that the network is undirected.

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

This is a representation of the network that we get when we draw it out:

A 6 by 6 matrix and its corresponding undirected network with 6 vertices. Ask your teacher for more information.
  • start with the first row, and the vertex on the left

  • draw in the edges connected to that vertex

  • move on to the next row/next vertex clockwise, ignoring the numbers below the main diagonal - they get drawn into the network when we do earlier rows for undirected networks. If the graph is directed, all the numbers need to be turned into edges.

Examples

Example 4

Select the network with this adjacency matrix:

\begin{matrix} & \begin{matrix} X&Y&Z\end{matrix}\\ \begin{matrix} X\\ Y\\ Z \end{matrix} & \begin{bmatrix}\, 0 &\, 0 &\, 0 \\ \, 2 &\, 0 &\, 0 \\ \, 1 &\, 1 &\, 0 \end{bmatrix} \end{matrix}

A
A directed network with vertices X, Y, Z where X is connected to Z, Z to X, Z to Y, and Y to X.
B
A directed network with vertices X, Y, Z where X is connected Y, Y to Z, and Z is connected to X twice.
C
A directed network with vertices X, Y, Z where Z is connected X, Y to Z, and X is connected to Y twice.
D
A directed network with vertices X, Y, Z where Z is connected X, Y to Z, and Y is connected to X twice.
E
A directed network with vertices X, Y, Z where Z is connected X and Y is connected to X twice.
Worked Solution
Create a strategy

Start with the first row, and the vertex on the left. Draw in the edges connected to that vertex and move on to the next row.

Apply the idea

Let's start with the first row. All the numbers are 0. This means that vertex X is not connected to the other vertices. This means options A, B and C are incorrect.

There is a 2 in row Y, column X, so there should be two edges from Y to X. This is true for both remaining options D and E.

In row Z, 1 is written in columns X and Y. So there should be an edge from Z to X and from Z to Y. This is ony true for option E.

The correct answer is option E

Idea summary

For directed networks, the element in a particular row and column indicates the number of edges going from the corresponding row vertex to the corresponding column vertex.

Loops are indicated by elements on the main diagonal with each loop counting as one connection.

Adjacency matrices can be used for weighted graphs where each element in the matrix represents the weight assigned to that edge.

If we know that we have a directed or undirected network, the information in the adjacency matrix is enough for us to draw a graph to represent the network.

Multi-stage connections

The elements in an adjacency matrix for a directed graph represent direct connections from one vertex to another.

A directed graph with vertices A, B, C, D where A is connected B and D, C is connected to B, A, and D.

For example, the directed graph can be represented by the adjacency matrix M.

M \,=\, \begin{matrix} & \begin{matrix} A&B&C&D\end{matrix}\\ \begin{matrix} A\\ B\\ C\\ D \end{matrix} & \begin{bmatrix} 0 &1 &0 &1 \\ 0 &0 &0 &0 \\ 1 &1 &0 &1 \\ 0 &0 &0 &0 \end{bmatrix} \end{matrix}

Matrix M shows that there are three one-stage connections from vertex C - one each to vertices A, \, B and D.

A two-stage connections is a connections between two nodes that goes via some other node. In the given graph, the path C, \, A, \, B is a two-stage path from C to B. There is also a two-stage path C, \, A, \, D from C to D.

The two-stage connections can be seen in the M^2 matrix, which can be obtained by multiplying the matrix M by itself, either using technology or performing matrix multiplication.

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

This video shows how to evaluate the square of a matrix using a calculator:

Loading video...

Two-stage connections are indicated by the non-zero elements in M^2. The two 1’s in the matrix indicate there are two 2-step paths from C to B \, (CAB) and from C to D \, (CAD). But how does this method actually work?

Let's consider the entry in the third row and second column of the matrix M^2, which indicates that there is a single 2-step path from C to B. To get this value via matrix multiplication, we need to take the product of the third row of matrix M with the second column of matrix M. Since the third row of matrix M counts the number of paths from C to the other vertices, and the second row counts the number of paths to B from other vertices, multiplying them together is the same as counting "how many paths are there from C to B through one other vertex?".

This use of matrix arithmetic can even be extended to use M^{n} to identify n-stage connections.

For this particular graph, we can see that there are no three-stage connections because M^3 is a zero matrix. That means there is no way to get to one vertex to another in three steps.

M^{3} = \begin{bmatrix} 0 &0 &0 &0 \\ 0 &0 &0 &0 \\ 0 &0 &0 &0 \\ 0 &0 &0 &0 \end{bmatrix}

TThis video shows how to evaluate the cube of a matrix using a calculator:

Loading video...

Multi-stage connections can represent numerous practical situations, such as air transport links between cities, the ranking of players in sporting competitions, connections in computer networks and many others.

Examples

Example 5

Consider the given graph.

A directed network with vertices X, Y, Z. X is connected to Y, Z is connected to Z and Y is connected X and Z.
a

Create the adjacency matrix, M.\begin{matrix} & \begin{matrix} X&Y&Z \end{matrix}\\ \begin{matrix} X \\ Y \\ Z \end{matrix} & \begin{bmatrix} ⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Worked Solution
Create a strategy

Follow these steps:

  1. Start with the first row, which represents the vertex X.

  2. If an arrow points from X to the column vertex, write 1, otherwise write 0.

  3. Repeat this for each row.

Apply the idea

The top left cell is 0 since there is no arrow from X to X. The next cell is 1 since there is one arrow that points from X to Y. The next cell is 0 since there is no arrow that points from X to Z.M\,=\,\begin{matrix} & \begin{matrix} X&Y&Z \end{matrix}\\ \begin{matrix} X \\ Y \\ Z \end{matrix} & \begin{bmatrix} 0 &1 &0 \\ ⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

The first cell in row Y is 1 since there is an arrow pointing from Y to X. The next cell is 0 since there is no arrow that points from Y to itself. The next cell is 1 since there an arrow that points from Y to Z.M\,=\,\begin{matrix} & \begin{matrix} X&Y&Z \end{matrix}\\ \begin{matrix} X \\ Y \\ Z \end{matrix} & \begin{bmatrix} 0 &1 &0 \\ 1 &0 &1 \\ ⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}The first cell in row Z is 1 since there is an arrow pointing from Z to X. There are no other arrows pointing from Z so the last two cells are zeros.M\,=\,\begin{matrix} & \begin{matrix} X&Y&Z \end{matrix}\\ \begin{matrix} X \\ Y \\ Z \end{matrix} & \begin{bmatrix} 0 &1 &0 \\ 1 &0 &1 \\ 1 &0 &0 \end{bmatrix} \end{matrix}

b

Find the second-stage adjacency matrix M^2 using technology or otherwise.M^2 \,=\,\begin{matrix} & \begin{matrix} X&Y&Z \end{matrix}\\ \begin{matrix} X \\ Y \\ Z \end{matrix} & \begin{bmatrix} ⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Worked Solution
Create a strategy

Use technology to calculate M^2.

Apply the idea

The second-stage adjacency matrix M^2 is:M^2 \,=\,\begin{matrix} & \begin{matrix} X&Y&Z \end{matrix}\\ \begin{matrix} X \\ Y \\ Z \end{matrix} & \begin{bmatrix} 1 &0 &1 \\ 1 &1 &0 \\ 0 &1 &0 \end{bmatrix} \end{matrix}

c

How many two-stage paths are there between Y and X?

Worked Solution
Create a strategy

Find the value of the cell in the adjacency matrix M^2 in row Y column X.

Apply the idea

From the matrix in part (b), the value in row Y column X is 1.\text{Number of paths}= 1

d

There is one two-stage path from Y to X. What is this path?

Worked Solution
Create a strategy

Use the original graph.

Apply the idea
A directed network with vertices X, Y, Z. X is connected to Y, Z is connected to Z and Y is connected X and Z.

By following the arrows from Y we can see that the two-stage path from Y to X is Y, \, Z, \, X.

e

Find the third-stage adjacency matrix M^3 using technology or otherwise.M^3 \,=\,\begin{matrix} & \begin{matrix} X&Y&Z \end{matrix}\\ \begin{matrix} X \\ Y \\ Z \end{matrix} & \begin{bmatrix} ⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Worked Solution
Create a strategy

Use technology to calculate M^3.

Apply the idea

The third-stage adjacency matrix M^3 is:M^3 \,=\,\begin{matrix} & \begin{matrix} X&Y&Z \end{matrix}\\ \begin{matrix} X \\ Y \\ Z \end{matrix} & \begin{bmatrix} 1 &1 &0 \\ 1 &1 &1 \\ 1 &0 &1 \end{bmatrix} \end{matrix}

f

Which vertices are connected by a three-stage path? Write only the start and end vertices.

Worked Solution
Create a strategy

Choose a pair of vertices that are connected by a 1 in the matrix from part (e).

Apply the idea

From part (a) we found: M^3 \,=\,\begin{matrix} & \begin{matrix} X&Y&Z \end{matrix}\\ \begin{matrix} X \\ Y \\ Z \end{matrix} & \begin{bmatrix} 1 &1 &0 \\ 1 &1 &1 \\ 1 &0 &1 \end{bmatrix} \end{matrix} so any pair of vertices that have a 1 in the corresponding cell are connected by a three-stage path.

Below is a list of three-stage paths that exist for the graph, with only the start and end vertices listed:

Start vertexEnd vertex
Path 1XX
Path 2XY
Path 3YX
Path 4YY
Path 5YZ
Path 6ZX
Path 7ZZ
Idea summary

The elements in an adjacency matrix for a directed graph represent direct (one-step) connections from one vertex to another.

The elements in the adjacency matrix squared, M^2, for a directed graph represent two-step connections from one vertex to another.

The elements in the adjacency matrix cubed, M^3, for a directed graph represent three-step connections from one vertex to another.

Outcomes

ACMGM079

identify practical situations that can be represented by a network, and construct such networks; for example, trails connecting camp sites in a National Park, a social network, a transport network with one-way streets, a food web, the results of a round-robin sporting competition

ACMGM080

construct an adjacency matrix from a given graph or digraph

What is Mathspace

About Mathspace