Networks and graphsIB MYP Maths Extended: Flashcards

Exam questions on Networks and graphs

1. A network has four vertices $A$, $B$, $C$ and $D$. The edges are $AB$, $AC$, $AD$ and $BC$. Each edge joins two different vertices, and no two vertices are joined by more than one edge.
   Write down the adjacency matrix of the network, with the vertices in the order $A$, $B$, $C$, $D$.2 marks
2. Five towns $P$, $Q$, $R$, $S$ and $T$ are joined by roads. The road lengths in km are $PQ=4$, $PR=7$, $QR=2$, $QS=6$, $RS=3$, $RT=9$ and $ST=5$. There are no other roads, and a route may not visit the same town twice.
   Find the shortest route from $P$ to $T$ and state its length.2 marks
3. A complete network $K_n$ has $n$ vertices, with every pair of vertices joined by exactly one edge. $K_3$ has 3 edges, $K_4$ has 6 edges and $K_5$ has 10 edges. An Euler circuit is a route that starts and ends at the same vertex and uses every edge exactly once. A connected network has an Euler circuit if and only if every vertex has even degree.
   Describe the pattern in the number of edges of $K_n$ and write a general rule for the number of edges in terms of $n$. Check your rule using $K_5$ and predict the number of edges of $K_6$.3 marks