Graph theory problems

Questions about graph properties, Eulerian paths, spanning trees, network algorithms (Kruskal's, etc.), or graph construction with specified vertex orders and arcs. These are pure graph theory questions not involving assignment or matching of people to tasks.

3 questions · Moderate -0.3

Sort by: Default | Easiest first | Hardest first
OCR D1 2006 June Q12
Moderate -0.5
12 JUNE 2006
Afternoon
1 hour 30 minutes
  • This insert should be used to answer Question 6.
  • Write your name, centre number and candidate number in the spaces provided at the top of this page.
  • Write your answers to Question 6 in the spaces provided in this insert, and attach it to your answer booklet.
6

  1. Key: \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_193_949_214_712} Do not cross out your working values (temporary labels) \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_1157_1600_648_303} Route of shortest path from \(A\) to \(J =\) \(\_\_\_\_\) Length of shortest path from \(A\) to \(J =\) \(\_\_\_\_\) metres
    1. \(\_\_\_\_\) Shortest distance \(=\) \(\_\_\_\_\) metres
    2. \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-11_979_1429_276_440}
      Shortest distance = \(\_\_\_\_\) metres
OCR D1 2010 June Q8
Moderate -0.8
8
4 (ii)
4 (iii)
4 (iv)
\(B\)\(C\)\(D\)\(F\)\(G\)
\(B\)-0.20.10.30.75
\(C\)0.2-0.30.50.95
\(D\)0.10.3-0.20.65
\(F\)0.30.50.2-0.45
\(G\)0.750.950.650.45-
4 (v)
\(B\)\(C\)\(D\)\(F\)
\(B\)-0.20.10.3
\(C\)0.2-0.30.5
\(D\)0.10.3-0.2
\(F\)0.30.50.2-
\(B\)
\(\bullet { } ^ { D }\)
- \({ } ^ { F }\)
\(C _ { \bullet }\)
5 (i)
5 (ii)
\multirow[t]{12}{*}{5 (ii)}(continued)
\multirow{19}{*}{5 (iii)}
\section*{PLEASE DO NOT WRITE ON THIS PAGE} RECOGNISING ACHIEVEMENT
OCR Further Discrete AS Specimen Q2
7 marks Standard +0.3
2 Some of the activities that may be involved in making a cup of tea are listed below. A: Boil water.
B: Put teabag in teapot, pour on boiled water and let tea brew.
C: Get cup from cupboard.
D: Pour tea into cup.
E: Add milk to cup.
F: Add sugar to cup. Activity A must happen before activity B.
Activities B and C must happen before activity D .
Activities E and F cannot happen until after activity C.
Other than that, the activities can happen in any order.
  1. Lisa does not take milk or sugar in her tea, so she only needs to use activities \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . In how many different orders can activities \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D be arranged, subject to the restrictions above?
  2. Mick takes milk but no sugar, so he needs to use activities \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E . Explain carefully why there are exactly nine different orders for these activities, subject to the restrictions above.
  3. Find the number of different orders for all six activities, subject to the restrictions above. Explain your reasoning carefully.