3.14 Graph theory: definitions and representationIB Maths: Applications and Interpretation HL: Subtopic test

1. 1
   A small office network has five computers $A$, $B$, $C$, $D$ and $E$, joined by the cables $AB$, $AC$, $BC$, $CD$ and $DE$. The network is modelled as a graph $G$ with the computers as vertices and the cables as edges.

   (a)

   Write down the degree of vertex $C$.

   [1 mark]

   • A$2$
   • B$5$
   • C$4$
   • D$3$

   (b)

   Which statement about $G$ is correct?

   [1 mark]

   • A$G$ is connected and simple but is not a tree.
   • B$G$ is a tree.
   • C$G$ is a complete graph.
   • D$G$ is not connected.

   (c)

   Find the number of cables that must be added to $G$ so that every pair of computers is directly connected.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   In a town centre, four junctions $W$, $X$, $Y$ and $Z$ are joined by one-way streets: $W$ to $X$, $X$ to $Y$, $Y$ to $Z$, $Z$ to $W$ and $X$ to $Z$. The street system is modelled as a directed graph, with the junctions as vertices and the one-way streets as directed edges.

   (a)

   Find the out-degree of $X$.

   [1 mark]

   • A$1$
   • B$2$
   • C$3$
   • D$0$

   (b)

   Which junction has in-degree 2?

   [1 mark]

   • A$W$
   • B$X$
   • C$Z$
   • D$Y$

   (c)

   Show that the directed graph is strongly connected.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A phone company plans to link five towns $A$, $B$, $C$, $D$ and $E$. The possible cables and their lengths in km are $AB$ (6), $AC$ (9), $BC$ (4), $BD$ (7), $CD$ (5), $CE$ (8) and $DE$ (3). This is modelled as a weighted graph with the towns as vertices and the cable lengths as weights.

   (a)

   Write down the degree of each vertex, and show that the sum of the degrees is twice the number of edges.

   [3 marks]

   (b)

   The company chooses the subgraph with edges $AB$, $BC$, $CD$ and $DE$.
   (i) Show that this subgraph is a tree.
   (ii) Find the total length of cable it uses.
   (iii) State how many edges any tree on five vertices has.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A wireless sensor network has five sensors $P$, $Q$, $R$, $S$ and $T$. Two sensors can communicate directly if they are joined by a link: the links are $PQ$, $PR$, $QR$, $QS$, $RS$ and $ST$. The network is modelled as a graph $G$ with the sensors as vertices and the links as edges.

   (a)

   (i) State, with a reason, whether $G$ is a simple graph.
   (ii) Find the number of links that must be added to $G$ to make it a complete graph.
   (iii) Show that $G$ is connected but is not a tree.
   (iv) Write down the edges of a subgraph of $G$, using all five vertices, that is a tree.

   [6 marks]

   (b)

   Sensor $S$ fails. The subgraph $H$ is formed by deleting vertex $S$ and every edge joined to it.
   (i) Write down the edges of $H$.
   (ii) State, with a reason, whether $H$ is connected.
   (iii) Find how many edges $H$ would have if it were a complete graph, and how many more it needs.
   (iv) The edge $PT$ is added to $H$. Determine whether the new graph is a tree.

   [6 marks]

   Total for question 4: 12 marks

End of questions