# 4.02 Network representations

Worksheet
Network representations
1

Draw a directed graph to represent each of the following food chain descriptions. Draw the arrows pointing from the animal that is eaten to the animal that eats it.

a

Within a water system:

• Tadpoles, water beetles and snails all survive by eating algae.

• Small fish eat the tadpoles, whilst frogs survive on water beetles and snails.

• The kingfisher, a skillful fishing bird, survives on eating small fish and frogs.

b

Rabbits and squirrels both eat plants. Foxes and hawks eat both rabbits and squirrels.

c

The killer whale depends on tuna as a primary food source. In turn, the tuna feeds on fish called mackerel. For mackerel to survive, they depend on microscopic organisms collectively known as zooplankton.

2

For each of the following networks, state:

i

What the edges represent.

ii

What the vertices represent.

iii

The number of vertices.

iv

The number of edges.

a

This network represents the internet fiber optics cables connecting several cities:

b

This network represents an electrical circuit that includes a globe, resistors and multiple switches.

c

This network displays newspaper routes between several houses:

d

This network represents the roads between several towns:

3

Consider the map below which shows major roads connecting various towns. The shaded regions indicate how far each town extends:

Draw a graph that represents the major roads connecting towns on the map.

4

A beach volleyball team of 5 players can use 3 players in any one game.

The table shows the combinations that the coach has already used in the first three games:

a

Draw a network to represent this information.

b

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

5

A group of journalists have been asked to work in pairs to collaborate on an article.

• Derek has already collaborated with Neil, Xavier, and Xanthe.

• Neil has already collaborated with Xanthe, Xavier, and Tina.

• Xanthe and Tina have collaborated together.

a

Draw an undirected graph to represent the journalists who have worked together.

b

Name the journalists who still need to collaborate with someone else so that each journalist will have collaborated with every other journalist at least once.

6

Over a year students work in pairs to complete poster projects.

A group of 4 friends have already completed the following projects together:

a

Draw an undirected graph to represent the pairs of students who have completed projects together.

b

Name the pairs of students that should work together on the next poster project so that all 4 friends have worked with each other.

7

Consider the following image which shows a train network, and the stations that are connected by train lines:

Draw the graph that represents the train network.

8

The following table displays the times buses arrive and depart from several bus stops:

Draw the graph that represents the bus routes.

9

Create an adjacency matrix for the following network:

10

For each of the given networks:

i

Create an adjacency matrix for the network.

ii

State the degree of the vertex indicated.

a

Vertex A

b

Vertex P

c

Vertex Q

d

Vertex P

11

For each of the following adjacency matrices, draw the corresponding network:

a
\begin{matrix} & \begin{matrix} A&B&C&D\end{matrix}\\ \begin{matrix} A\\ B\\ C\\D \end{matrix} & \begin{bmatrix}0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix} \end{matrix}
b
\begin{matrix} & \begin{matrix} A&B&C&D\end{matrix}\\ \begin{matrix} A\\ B\\ C\\D \end{matrix} & \begin{bmatrix}0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix} \end{matrix}
c
\begin{matrix} & \begin{matrix} P&Q&R&S&T\end{matrix}\\ \begin{matrix} P\\ Q\\ R\\S\\T \end{matrix} & \begin{bmatrix}0 & 1 & 2 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix} \end{matrix}
d
\begin{bmatrix} 0&0&1&1&1 \\ 0&0&2&0&0 \\1&2&0&0&0 \\1&0&0&2&0 \\1&0&0&0&2 \end{bmatrix}
12

The following adjacency matrix lists the fees (as a percentage) charged by a bank to convert between five types of currency:

Represent this information using a network.

13

The following adjacency matrix 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:

Represent this information using a network.

\begin{matrix} & \begin{matrix} \text{Carousel} & \text{P. S.} & \text{H.H.} \end{matrix} \\ \begin{matrix} \text{Carousel} \\ \text{Pirate Ship} \\ \text{Haunted House} \end{matrix} & \begin{bmatrix} 3 \qquad & 5 \qquad & 4 \\ 5 \qquad & 13 \qquad & 6 \\ 4 \qquad & 6 \qquad & 11 \end{bmatrix} \end{matrix}
14

Create an adjacency matrix for each of these networks:

a
b
15

For each of the following adjacency matrices, draw the corresponding network:

a
\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}
b
\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A\\ B\\ C\\D\\E \end{matrix} & \begin{bmatrix}0 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 &0\\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \end{bmatrix} \end{matrix}
16

Consider the given graph:

a

Create the corresponding adjacency matrix, M.

b

State the number of one-stage paths between B and D.

c

Find the second-stage adjacency matrix M^2 using technology or otherwise.

d

Hence determine the number of two-stage paths between C and D.

17

Consider the given graph:

a

Create the corresponding adjacency matrix, M.

b

State the number of one-stage paths between R and S.

c

Find the second-stage adjacency matrix M^2 using technology or otherwise.

d

There are four two-stage paths from S to P. Give an example of one of these paths.

18

Consider the given graph:

a

Create the corresponding adjacency matrix, M.

b

Find the second-stage adjacency matrix M^2 using technology or otherwise.

c

State the number of two-stage paths between I and F.

d

Give an example of one of the two-stage paths from I to F.

e

Find the third-stage adjacency matrix M^3 using technology or otherwise.

f

Hence state the number of three-stage paths between I and F.

19

Consider the given graph:

a

Create the corresponding adjacency matrix, M.

b

Find the second-stage adjacency matrix M^2 using technology or otherwise.

c

State the number of two-stage paths between Y and X.

d

State a two-stage path from Y to X.

e

Find the third-stage adjacency matrix M^3 using technology or otherwise.

f

State the vertices that are connected by a three-stage path. Write only the start and end vertices of each path.

20

Consider the given graph:

a

Create the corresponding adjacency matrix, M.

b

Create the adjacency matrix, M^3 using technology or otherwise.

c

List the vertices connected by 5 different three-stage paths. Give a single example, writing only the start and end vertices.

21

The following adjacency matrix lists the number of likes that four friends give to each other's social media posts over a week:

Represent this information using a directed network.

22

The following adjacency matrix lists the number of termites observed to be moving within and between three sites in 1 hour:

Represent this information using a directed network.

\begin{matrix} & \quad \text{Destination} \\ \text{Origin} & \begin{matrix} & \begin{matrix} \text{Nest} & \text{Plains} & \text{Forest} \end{matrix} \\ \begin{matrix} \text{Nest} \\ \text{Plains} \\ \text{Forest} \end{matrix} & \begin{bmatrix} 3570 \quad & 325 \quad & 1240 \\ 65 \quad & 475 \quad & 965 \\ 410 \quad & 535 \quad & 230 \end{bmatrix} \end{matrix} \end{matrix}
23

Which key features indicates that this adjacency matrix represents a complete graph?

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

Which key feature indicates that this adjacency matrix represents a directed graph?

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

Which key feature indicates that there are loops in the graph represented by this adjacency matrix?

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

Which key feature indicates there are multiple edges in the graph represented by this adjacency matrix?

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

For each adjacency matrix, describe the associated graph using the appropriate terms from the given list:

• Complete

• Bipartite

• Directed

• Simple

a
\begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 2 & 0 & 2 \\ 1 & 0 & 0 & 0 \end{bmatrix}
b
\begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix}
28

State whether the following adjacency matrix represents a bipartite graph:

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

a

State the key feature that indicates that the graph represented by this adjacency matrix is a bipartite graph.

b

State whether the matrix represents a complete bipartite graph.

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

Consider the adjacency matrix shown that represents a bipartite graph:

a

List the vertices in the bipartite group containing 2 vertices.

b

State whether the matrix represents a complete bipartite graph.

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

Create an adjacency matrix for the following complete bipartite graph:

32

Create an adjacency matrix for the following bipartite graph:

### 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