3.14 Graph theory: definitions and representationIB Maths: Applications and Interpretation HL: Flashcards

Exam questions on 3.14 Graph theory: definitions and representation

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.
   Find the number of cables that must be added to $G$ so that every pair of computers is directly connected.2 marks
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.
   Show that the directed graph is strongly connected.2 marks
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.
   Write down the degree of each vertex, and show that the sum of the degrees is twice the number of edges.3 marks