SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, GEN1 2024 VCAA 38 MC

A connected graph has six vertices and six edges.

How many of the following four statements must always be true?

  • the graph has no vertices of odd degree
  • the graph contains a Eulerian trail
  • the graph contains a Hamiltonian path
  • the sum of the degrees of the vertices is 12
  1. 1
  2. 2
  3. 3
  4. 4
Show Answers Only

\(A\)

Show Worked Solution

\(\text{Considering each option:}\)

\(\text{1.  Both Graph 1 & 2 above have vertices of odd degree }\rightarrow\ \text{Incorrect} \)

\(\text{2.  Graph 2 has 4 vertices of odd degree}\therefore \text{No Eulerian Trail}\rightarrow \text{Incorrect} \)

\(\text{3.  Path cannot be completed in Graph 2 without repeating a vertex}\)

\(\therefore\ \text{No Hamiltonian Path}\rightarrow \text{Incorrect} \)

\(\text{4. The sum of the degrees of the vertices is always 12}\ \rightarrow\ \text{Correct}\)
  

\(\therefore\ 1\ \text{of the statements is always true}\)

  
\(\Rightarrow A\)

Networks, GEN1 2022 VCAA 5 MC

A connected graph consists of five vertices and four edges.

Which one of the following statements is not true?

  1. The graph could be a tree.
  2. The graph could be planar.
  3. The graph could be bipartite.
  4. The graph could contain a path.
  5. The graph could contain a cycle.
Show Answers Only

\(E\)

Show Worked Solution

By elimination:

By definition the graph could be a tree or a path (eliminate  A and D).

Consider B: Planar graphs satisfy  \(f + v = e + 2.\)  In the connected graph described,  \(f = 1,\ v = 5,\ e = 4\). Satisfies equation (eliminate B).

Consider C: The graph could be bipartite – see below (eliminate C).

Consider E: The graph could not contain a cycle and remain connected.

\(\Rightarrow E\)


♦ Mean mark 54%.

Networks, GEN1 2023 VCAA 33 MC

Consider the following graph.
 

How many of the following five statements are true?

  • The graph is a tree.
  • The graph is connected.
  • The graph contains a path.
  • The graph contains a cycle.
  • The sum of the degrees of the vertices is eight.
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
Show Answers Only

\(D\)

Show Worked Solution

The graph is a tree (any two vertices are connected by one edge).  \(\checkmark\)

The graph is connected.  \(\checkmark\)

The graph contains a path.  \(\checkmark\)

The graph contains a cycle.  \(\cross\)

The sum of the degrees of the vertices is eight.  \(\checkmark\)

\(\Rightarrow D\)

NETWORKS, FUR1 2020 VCAA 7 MC

Four friends go to an ice-cream shop.

Akiro chooses chocolate and strawberry ice cream.

Doris chooses chocolate and vanilla ice cream.

Gohar chooses vanilla ice cream.

Imani chooses vanilla and lemon ice cream.

This information could be presented as a graph.

Consider the following four statements:

  • The graph would be connected.
  • The graph would be bipartite.
  • The graph would be planar.
  • The graph would be a tree.

How many of these four statements are true?

  1. 0
  2. 1
  3. 2
  4. 3
  5. 4
Show Answers Only

`E`

Show Worked Solution

`text(True statements :)`

♦♦♦ Mean mark 11%.

`text{The graph is connected (a path exists between all vertices).}`

`text{The graph is bipartite (vertices can be divided into two groups).}`

`text{The graph is planar (no edges cross if strawberry is moved to the top).}`

`text{The graph forms a tree (no cycles).}`

`=>  E`

NETWORKS, FUR2 2020 VCAA 1

The Sunny Coast Cricket Club has five new players join its team: Alex, Bo, Cameron, Dale and Emerson.

The graph below shows the players who have played cricket together before joining the team.

For example, the edge between Alex and Bo shows that they have previously played cricket together.
 

  1. How many of these players had Emerson played cricket with before joining the team?  (1 mark)
  2. Who had played cricket with both Alex and Bo before joining the team?   (1 mark)
  3. During the season, another new player, Finn, joined the team.

      

    Finn had not played cricket with any of these players before.

      

    Represent this information on the graph above.   (1 mark)

Show Answers Only
  1. `text(one)`
  2. `text(Dale)`
  3.  
Show Worked Solution

a.  `text{One (one edge connected to Emerson.)}`

 

b.  `text{Dale (he has edges directly connected to Alex and Bo.)}`

 

c.  

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 4 MC

Two graphs, labelled Graph 1 and Graph 2, are shown below.
 


 

Which one of the following statements is not true?

  1. Graph 1 and Graph 2 are isomorphic.
  2. Graph 1 has five edges and Graph 2 has six edges.
  3. Both Graph 1 and Graph 2 are connected graphs.
  4. Both Graph 1 and Graph 2 have three faces each.
  5. Neither Graph 1 nor Graph 2 are complete graphs.
Show Answers Only

`A`

Show Worked Solution

`text(Graph 1 → 5 edges)`

`text(Graph 2 → 6 edges)`

`:.\ text(Cannot be isomorphic.)`

`=>  A`

NETWORKS, FUR1 2018 VCAA 4 MC

Consider the graph below.
 


 

Which one of the following is not a path for this graph?

  1. `PRQTS`
  2. `PQRTS`
  3. `PRTSQ`
  4. `PTQSR`
  5. `PTRQS`
Show Answers Only

`D`

Show Worked Solution

`text(By trial and error:)`

`text(Consider option)\ D,`

`PTQSR\ text(is not a path because)\ S\ text(to)\ R`

`text(must go through another vertex.)`

`=> D`

NETWORKS, FUR1 2018 VCAA 1 MC

Consider the graph with five isolated vertices shown below.
 


 

To form a tree, the minimum number of edges that must be added to the graph is

  1.   1
  2.   4
  3.   5
  4.   6
  5. 10
Show Answers Only

`B`

Show Worked Solution

`text(5 vertices.)`

`text(Minimum edges for a tree = 4)`

`=> B`

NETWORKS, FUR1 2017 VCAA 7 MC

A graph with six vertices has no loops or multiple edges.

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

  1. If the graph is a tree it has five edges.
  2. If the graph is complete it has 15 edges.
  3. If the graph has eight edges it may have an isolated vertex.
  4. If the graph is bipartite it will have a minimum of nine edges.
  5. If the graph has a cycle it will have a minimum of three edges.
Show Answers Only

`D`

Show Worked Solution

`text(Consider option)\ D:`

`text(It is easy to construct a bipartite graph in this)`

`text(example with less than nine edges.)`

`text(For example, the graph below is bipartite with)`

`text(6 vertices and 5 edges.)`
 

`=> D`

NETWORKS, FUR1 2016 VCAA 3 MC

The following graph with five vertices is a complete graph.
 

Edges are removed so that the graph will have the minimum number of edges to remain connected.

The number of edges that are removed is

  1.   `4`
  2.   `5`
  3.   `6`
  4.   `9`
  5. `10`
Show Answers Only

`C`

Show Worked Solution

`text(The minimum number of edges for)`

♦♦ Mean mark 35%.

`text{a connected graph is 4 (spanning tree).}`
 

 
`:.\ text(Edges to be removed)`

`= 10 – 4`

`= 6`

`=> C`

NETWORKS, FUR1 2008 VCAA 4 MC

A simple connected graph with 3 edges has 4 vertices.

This graph must be

A.   a complete graph.

B.   a tree.

C.   a non-planar graph.

D.   a graph that contains a loop.

E.   a graph that contains a circuit.

Show Answers Only

`=> B`

Show Worked Solution

`text(Consider the graph below,)`
 

networks-fur1-2008-vcaa-4-mc-answer

`=> B`

NETWORKS, FUR1 2011 VCAA 6 MC

A store manager is directly in charge of five department managers.

Each department manager is directly in charge of six sales people in their department.

This staffing structure could be represented graphically by

A.   a tree.

B.   a circuit.

C.   an Euler path.

D.   a Hamiltonian path.

E.   a complete graph.

Show Answers Only

`A`

Show Worked Solution

`=>  A`

NETWORKS, FUR1 2013 VCAA 7 MC

A connected graph consists of five vertices and four edges.

Consider the following five statements.

•  The graph is planar.

•  The graph has more than one face.

•  All vertices are of even degree.

•  The sum of the degrees of the vertices is eight.

•  The graph cannot have a loop.

How many of these statements are always true for such a graph?

A.   `1`

B.   `2`

C.   `3`

D.   `4`

E.   `5`

Show Answers Only

`C`

Show Worked Solution

`text(The possible graphs with 5 vertices)`

`text(and 4 edges are:)`

vcaa-networks-fur1-2013-7

`text(By inspection, the true statements are:)`

♦ Mean mark 39%.

`•\ text(graph is planar)`

`•\ text(sum of degrees is eight)`

`•\ text(graph can’t have a loop)`

 `=>  C`

NETWORKS, FUR2 2007 VCAA 1

A new housing estate is being developed.

There are five houses under construction in one location.

These houses are numbered as points 1 to 5 below.
 

NETWORKS, FUR2 2007 VCAA 1

  
The builders require the five houses to be connected by electrical cables to enable the workers to have a supply of power on each site.

  1. What is the minimum number of edges needed to connect the five houses?  (1 mark)
  2. On the diagram above, draw a connected graph with this number of edges.  (1 mark) 
Show Answers Only
  1. `4`
  2.  
    networks-fur2-2007-vcaa-1-answer
Show Worked Solution

a.   `text(Minimum number of edges = 4)`
 

b.   `text(One of many possibilities:)`

networks-fur2-2007-vcaa-1-answer

NETWORKS, FUR1 2015 VCAA 3 MC

The plan shows the layout of a section of pipes, drawn in bold lines, that supplies water to nine houses in a new estate.
 

NETWORKS, FUR1 2015 VCAA 3 MC
 

Which one of the following types of graph could be used to represent the layout of water pipe connections to the water supply and these houses?

A.   a bipartite graph

B.   a complete graph

C.   a loop

D.   a Hamiltonian path

E.   a tree

Show Answers Only

`E`

Show Worked Solution

`=> E`