SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, GEN1 2024 NHT 34 MC

The adjacency matrix below represents the road connections between four towns, labelled \(L, M, N\) and \(O\).

\begin{aligned}
&\ \ \  L \ \ \ M \ \  N \ \ O \\
\begin{array}{c} L\\ M \\ N \\ O \end{array}
&\begin{bmatrix}
1 & 0 & 1 & 1 \\
0 & 0 & 1 & 2 \\
1 & 1 & 0 & 0 \\
1 & 2 & 0 & 0
\end{bmatrix}
\end{aligned}

A graph that represents all the road connections in the adjacency matrix is:
 

 

     

Show Answers Only

\(C\)

Show Worked Solution

\(\text{By elimination:}\)

\(L ↔ L = 1\ \ \text{(eliminate E)}\)

\(L ↔ N = 1\ \ \text{(eliminate B and D)}\)

\(M ↔ O = 2\ \ \text{(eliminate A)}\)

\(\Rightarrow C\)

Networks, GEN2 2024 VCAA 13

A supermarket has five departments, with areas allocated as shown on the floorplan below.
 

The floorplan is represented by the graph below.

On this graph, vertices represent departments and edges represent boundaries between two departments.

This graph is incomplete.
 

  1. Draw the missing vertex and missing edges on the graph above. Include a label.   (1 mark)

Karla is standing in the Promotional department.

She wants to visit each department in the supermarket once only.

  1.  i.  In which department will she finish?  (1 mark)
  2. ii.  What is the mathematical name for this type of journey?  (1 mark)
  3. The supermarket adds a new Entertainment department \((E)\), and the floorplan is rearranged.
  4. The boundaries between the departments are represented in the adjacency matrix below, where a ' 1 ' indicates a boundary between the departments.

\begin{aligned}
& \ \ B \ \ \ D \ \ \  E \ \ \  F \ \ \ G \ \ \ P \\
\begin{array}{c}
B\\
D \\
E \\
F \\
G \\
P
\end{array}& \begin{bmatrix}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 \\
1 & 0 & 1 & 1 & 1 & 0
\end{bmatrix}
\end{aligned}

  1. Use the adjacency matrix to complete the floorplan below by labelling each department. The Bakery \((B)\) is already labelled.  (1 mark)

Show Answers Only

a. 

 
b.i.   \(\text{The bakery}\)

b.ii.  \(\text{Hamiltonian Path}\)
 

c.

Show Worked Solution

a. 

b.i.  \(\text{Bakery}\)

b.ii. \(\text{The path has no repeated edges or vertices, and }\)

\(\text{incudes all the edges of the graph.}\)

\(\therefore\ \text{It is a Hamiltonian Path.}\)

c.

Networks, GEN2 2023 VCAA 12

A country has five states, \(A, B, C, D\) and \(E\).

A graph can be drawn with vertices to represent each of the states.

Edges represent a border shared between two states.

  1. What is the sum of the degrees of the vertices of the graph above?   (1 mark)

  2. Euler's formula, \(v+f=e+2\), holds for this graph.
  3. i. Complete the formula by writing the appropriate numbers in the boxes provided below.   (1 mark)


  4. ii. Complete the sentence by writing the appropriate word in the space provided below.   (1 mark)


    Euler’s formula holds for this graph because the graph is connected and ______________.
  5. The diagram below shows the position of state \(A\) on a map of this country.
  6. The four other states are indicated on the diagram as 1, 2, 3 and 4.
     

  1. Use the information in the graph above to complete the table below. Match the state \((B, C, D\) and \(E)\) with the corresponding state number \((1,2,3\) and 4\()\) given in the map above.   (1 mark)

\begin{array} {|c|c|}
\hline
\rule{0pt}{2.5ex} \quad \quad \textbf{State} \quad \quad \rule[-1ex]{0pt}{0pt} & \textbf{State Number} \\
\hline
\rule{0pt}{2.5ex} B \rule[-1ex]{0pt}{0pt} & \\
\hline
\rule{0pt}{2.5ex} C \rule[-1ex]{0pt}{0pt} &  \\
\hline
\rule{0pt}{2.5ex} D \rule[-1ex]{0pt}{0pt} &  \\
\hline
\rule{0pt}{2.5ex} E \rule[-1ex]{0pt}{0pt} &   \\
\hline
\end{array}
Show Answers Only

a.    \(\text{Sum of degrees}\ = 2+3+4+3+2 = 14\)
 

b.i.   \(\text{Vertices = 5,  Faces = 4,  Edges = 7}\)

\(\Rightarrow 5 + 4 = 7 + 2\)
 

b.ii.     \(\text{Planar}\)
 

c.   

\begin{array} {|c|c|}
\hline
\rule{0pt}{2.5ex} \quad \quad \textbf{State} \quad \quad \rule[-1ex]{0pt}{0pt} & \textbf{State Number} \\
\hline
\rule{0pt}{2.5ex} B \rule[-1ex]{0pt}{0pt} & 3\\
\hline
\rule{0pt}{2.5ex} C \rule[-1ex]{0pt}{0pt} & 2 \\
\hline
\rule{0pt}{2.5ex} D \rule[-1ex]{0pt}{0pt} & 4 \\
\hline
\rule{0pt}{2.5ex} E \rule[-1ex]{0pt}{0pt} &  1 \\
\hline
\end{array}

Show Worked Solution

a.    \(\text{Sum of degrees}\ = 2+3+4+3+2 = 14\)
 

b.i.   \(\text{Vertices = 5,  Faces = 4,  Edges = 7}\)

\(\Rightarrow 5 + 4 = 7 + 2\)
 

b.ii.     \(\text{Planar}\)
 

c.   

\begin{array} {|c|c|}
\hline
\rule{0pt}{2.5ex} \quad \quad \textbf{State} \quad \quad \rule[-1ex]{0pt}{0pt} & \textbf{State Number} \\
\hline
\rule{0pt}{2.5ex} B \rule[-1ex]{0pt}{0pt} & 3\\
\hline
\rule{0pt}{2.5ex} C \rule[-1ex]{0pt}{0pt} & 2 \\
\hline
\rule{0pt}{2.5ex} D \rule[-1ex]{0pt}{0pt} & 4 \\
\hline
\rule{0pt}{2.5ex} E \rule[-1ex]{0pt}{0pt} &  1 \\
\hline
\end{array}

Networks, GEN1 2023 VCAA 37 MC

The adjacency matrix below represents a planar graph with five vertices.

\begin{aligned}
& \ \ \ J\ \ \ K\ \ \ L\ \ M\ \ N \\
& {\left[\begin{array}{lllll}
0 & 1 & 0 & 1 & 1 \\
1 & 0 & 2 & 1 & 1 \\
0 & 2 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 0
\end{array}\right] \begin{array}{l}
J \\
K \\
L \\
M \\
N
\end{array}} \\
\end{aligned}

The number of faces on the planar graph is

  1. 5
  2. 7
  3. 9
  4. 15
  5. 17
Show Answers Only

\(B\)

Show Worked Solution

\(\text{Sketch network:}\)

\(\Rightarrow B\)

NETWORKS, FUR1 2021 VCAA 7 MC

The network below shoes the pathways between five buildings: `J`, `K`, `L`, `M`, and `N`. 
 

An adjacency matrix for this network is formed.

The number of zeros in this matrix is

  1.   8
  2.   9
  3. 10
  4. 11
  5. 12
Show Answers Only

`C`

Show Worked Solution

`text{Adjacency matrix:}`

♦♦ Mean mark 33%.

 

`{:(qquadqquad J\ \ \ Kquad L\ \ M \ \ N),({:(J),(K),(L),(M),(N):}[(0,2,1,0,1),(2,1,2,1,0),(1,2,0,1,1),(0,1,1,0,0),(1,0,1,0,0)]):}`
 

`=> C`

NETWORKS, FUR1 2020 VCAA 8 MC

The adjacency matrix below shows the number of pathway connections between four landmarks: `J, K, L and M`.
 

`{:(qquadqquad J\ \ \ Kquad L\ \ M),({:(J),(K),(L),(M):}[(1,3,0,2),(3,0,1,2),(0,1,0,2),(2,2,2,0)]):}`
 

A network of pathways that could be represented by the adjacency matrix is

A.   B.  
C.   D.  
E.      
Show Answers Only

`E`

Show Worked Solution

`text(Matrix requires:)`

`text(3 paths directly between)\ J and K`

`:.\ text(Eliminate)\ A and D`

`text(2 paths directly between)\ M and J`

`:.\ text(Eliminate)\ C`

`text(1 path directly between)\ J and J`

`:.\ text(Eliminate)\ B`

`=>  E`

NETWORKS, FUR1-NHT 2019 VCAA 7 MC

A graph has five vertices, `A, B, C, D` and `E`.

The adjacency matrix for this graph is shown below.
 

`{:(qquad qquad A quad B quad C quad D quad E), ({:(A), (B), (C), (D), (E):} [(0, 1, 0, 1, 2),(1, 0, 1, 0, 1),(0, 1, 1, 0, 1),(1, 0, 0, 0, 1),(2, 1, 1, 1, 0)]):}`
 

Which one of the following statements about this graph is not true?

  1. The graph is connected.
  2. The graph contains an Eulerian trail.
  3. The graph contains an Eulerian circuit.
  4. The graph contains a Hamiltonian cycle.
  5. The graph contains a loop and multiple edges.
Show Answers Only

`C`

Show Worked Solution

`text(Consider the degree of each vertex:)`

`A – 4, B – 3, C – 3, D – 2, E – 5`

`text{Graph cannot be an Eulerian circuit because it}`

`text{has odd degree vertices.}`

`text{Note that an Eulerian circuit cannot have an odd degree}`

`text{vertex as it uses all edges exactly once and begins and ends}`

`text{at the same vertex.}`

`=>  C`

NETWORKS, FUR1 2019 VCAA 6 MC

The map below shows all the road connections between five towns, `P, Q, R, S` and `T`.
 


 

The road connections could be represented by the adjacency matrix

A.   `{:(qquad qquad P\ \ Q\ \ R\ \ \ S\ \ \ T), ({:(P),(Q),(R),(S),(T):}[(1, 3, 0, 2, 2),(3,0,1,1,1),(0,1,0,1,0),(2,1,1,0,2),(2,1,0,2,0)]):}` B.   `{:(qquad qquad P\ \ Q\ \ R\ \ \ S\ \ \ T), ({:(P),(Q),(R),(S),(T):}[(1, 2, 0, 2, 2),(2,0,1,1,1),(0,1,0,1,0),(2,1,1,0,2),(2,1,0,2,0)]):}`
       
C.   `{:(qquad qquad P\ \ Q\ \ R\ \ \ S\ \ \ T), ({:(P),(Q),(R),(S),(T):}[(0, 3, 0, 2, 2),(3,0,1,1,1),(0,1,0,1,0),(2,1,1,0,2),(2,1,0,2,0)]):}` D.   `{:(qquad qquad P\ \ Q\ \ R\ \ \ S\ \ \ T), ({:(P),(Q),(R),(S),(T):}[(0, 2, 0, 2, 2),(2,0,1,1,1),(0,1,0,1,0),(2,1,1,1,2),(2,1,0,2,0)]):}`
       
E.   `{:(qquad qquad P\ \ Q\ \ R\ \ \ S\ \ \ T), ({:(P),(Q),(R),(S),(T):}[(1, 2, 0, 2, 2),(2,0,1,1,1),(0,1,0,1,0),(2,1,1,1,1),(2,1,0,1,0)]):}`    

 

Show Answers Only

`A`

Show Worked Solution

`text(Consider town)\ P:`

`text(By Elimination,)`

`P\ \ text(to)\ \ P = 1 quad text{(a loop exists)} \ -> \ text(Eliminate)\ C, D`

`P\ \ text(to)\ \ Q = 3 \ -> \ text(Eliminate)\ B, E`

`=>  A`

NETWORKS, FUR1 2017 VCAA 3 MC

Consider the following graph.
 

 
The adjacency matrix for this graph, with some elements missing, is shown below.
 

 
This adjacency matrix contains 16 elements when complete.

Of the 12 missing elements

  1. eight are ‘1’ and four are ‘2’.
  2. four are ‘1’ and eight are ‘2’.
  3. six are ‘1’ and six are ‘2’.
  4. two are ‘0’, six are ‘1’ and four are ‘2’.
  5. four are ‘0’, four are ‘1’ and four are ‘2’.
Show Answers Only

`A`

Show Worked Solution

`text(Completing the adjacency matrix:)`
 

`=> A`

NETWORKS, FUR1 2007 VCAA 3 MC

Consider the following graph.
 

 
 

An adjacency matrix that could be used to represent this graph is

A.   `[(0,2,0,1), (2,0,1,1), (0,1,0,1), (1,1,1,0)]` B.   `[(0,2,0,1), (0,0,1,1), (0,0,0,1), (0,0,0,0)]`
       
C.   `[(0,1,0,1), (2,0,0,1), (0,1,0,1), (1,1,1,0)]` D.   `[(0,2,0,1), (0,1,1,1), (0,1,1,1), (0,1,1,1)]`
       
E.   `[(1,2,0,1), (2,1,0,1), (0,1,1,0), (0,0,1,1)]`    
Show Answers Only

`A`

Show Worked Solution

`=>  A`

NETWORKS, FUR1 2010 VCAA 3 MC

`{:(\ quad A\ quad B\ quad C\ quad D\ quad E), ([(0, 1, 0, 0, 1), (1, 0, 1, 0, 1), (0, 1, 0, 1, 2), (0, 0, 1, 0, 1), (1, 1, 2, 1, 0)] {:(A), (B), (C), (D), (E):}):}` 

 

A graph that can be drawn from the adjacency matrix above is

vcaa-networks-fur1-2010-3ai

vcaa-networks-fur1-2010-3aii

vcaa-networks-fur1-2010-3aiii

Show Answers Only

`B`

Show Worked Solution

`text(From the matrix, we can see that)\ C and E`

`text(have 2 parallel edges.)`

`:.\ text(Eliminate choices)\ C, D,\ text(and)\ E.`

 

`text(An edge exists between)\ B and E.`

`:.\ text(Eliminate)\ A.`

`=>  B`

NETWORKS, FUR1 2012 VCAA 4 MC

`{:({:qquadqquadPquadQquadRquadS:}),({:(P),(Q),(R),(S):}[(0,0,2,1),(0,0,1,1),(2,1,0,1),(1,1,1,0)]):}` 

 

The adjacency matrix above represents a planar graph with four vertices.

The number of faces (regions) on the planar graph is

A.   `1`

B.   `2`

C.   `3`

D.   `4`

E.   `5`

Show Answers Only

`D`

Show Worked Solution

`text(The graph can be represented)`
 

networks-fur1-2012-vcaa-4-mc-answer

`rArr D`

NETWORKS, FUR2 2009 VCAA 1

The city of Robville is divided into five suburbs labelled as `A` to `E` on the map below. 

A lake which is situated in the city is shaded on the map.

 

NETWORKS, FUR2 2009 VCAA 11

An adjacency matrix is constructed to represent the number of land borders between suburbs.

`{:({:qquadqquadAquadBquadCquadDquadE:}),({:(A),(B),(C),(D),(E):}[(0,1,1,1,0),(1,0,1,2,0),(1,1,0,0,0),(1,2,0,0,0),(0,0,0,0,0)]):}`

 

  1. Explain why all values in the final row and final column are zero.   (1 mark)

In the network diagram below, vertices represent suburbs and edges represent land borders between suburbs. 

The diagram has been started but is not finished.

 

Networks, FUR2 2009 VCAA 1_1
 

  1. The network diagram is missing one edge and one vertex. 

     

    On the diagram

  2.  i. draw the missing edge.   (1 mark)

  3. ii. draw and label the missing vertex.   (1 mark)

Show Answers Only
  1. `E\ text(has no land borders with other suburbs.)`
  2. i. & ii.
    Networks, FUR2 2009 VCAA 1 Answer
Show Worked Solution

a.   `E\ text(has no land borders with other suburbs.)`

 

b.i. & ii.    Networks, FUR2 2009 VCAA 1 Answer

NETWORKS, FUR2 2010 VCAA 1

The members of one team are Kristy (`K`), Lyn (`L`), Mike (`M`) and Neil (`N`). 

In one of the challenges, these four team members are only allowed to communicate directly with each other as indicated by the edges of the following network.
 

Network, FUR2 2011 VCAA 1
 

The adjacency matrix below also shows the allowed lines of communication.

`{:(quadKquadLquadMquadN),([(0,1,0,0),(1,0,1,0),(0,f,0,1),(0,g,1,0)]{:(K),(L),(M),(N):}):}`

 

  1. Explain the meaning of a zero in the adjacency matrix.   (1 mark)

  2. Write down the values of `f` and `g` in the adjacency matrix.   (1 mark)

Show Answers Only
  1. `text(No direct communication is allowed.)`
  2. `f = 1, g = 0`
Show Worked Solution

a.   `text(No direct communication is allowed.)`
  

b.   `f = 1, g = 0`