smc-622-40-Adjacency Matrix

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.

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

--- 0 WORK AREA LINES (style=lined) ---
Euler's formula, \(v+f=e+2\), holds for this graph.
1. Complete the formula by writing the appropriate numbers in the boxes provided below. (1 mark)
  
  --- 0 WORK AREA LINES (style=lined) ---
2. Complete the sentence by writing the appropriate word in the space provided below. (1 mark)
  
  --- 0 WORK AREA LINES (style=lined) ---
3. Euler’s formula holds for this graph because the graph is connected and ______________.
The diagram below shows the position of state \(A\) on a map of this country.
The four other states are indicated on the diagram as 1, 2, 3 and 4.

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)

--- 0 WORK AREA LINES (style=lined) ---

\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}\)

\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}\)

\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

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

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?

The graph is connected.
The graph contains an Eulerian trail.
The graph contains an Eulerian circuit.
The graph contains a Hamiltonian cycle.
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

eight are ‘1’ and four are ‘2’.
four are ‘1’ and eight are ‘2’.
six are ‘1’ and six are ‘2’.
two are ‘0’, six are ‘1’ and four are ‘2’.
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

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)`

`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.

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)]):}`

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.

The network diagram is missing one edge and one vertex.

On the diagram
1. draw the missing edge (1 mark)
2. draw and label the missing vertex. (1 mark)

Show Answers Only

`E\ text(has no land borders with other suburbs.)`
i. & ii.

Show Worked Solution

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

b.i. & ii.

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.

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):}):}`

Explain the meaning of a zero in the adjacency matrix. (1 mark)
Write down the values of `f` and `g` in the adjacency matrix. (1 mark)

Show Answers Only

`text(No direct communication is allowed.)`
`f = 1, g = 0`

Show Worked Solution

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

b. `f = 1, g = 0`