Edexcel D1 2001 June — Question 2 7 marks

Exam BoardEdexcel
ModuleD1 (Decision Mathematics 1)
Year2001
SessionJune
Marks7
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicMinimum Spanning Trees
TypeApply Kruskal's algorithm
DifficultyEasy -1.2 This is a straightforward application of Kruskal's algorithm to a small network with 7 nodes. The question requires only direct execution of a standard algorithm with no problem-solving insight, followed by drawing the result and summing costs. Decision Maths D1 content is generally more procedural and less conceptually demanding than pure maths topics.
Spec7.04b Minimum spanning tree: Prim's and Kruskal's algorithms
2. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-3_708_1096_360_408}
\end{figure} Figure 1 shows 7 locations \(A , B , C , D , E , F\) and \(G\) which are to be connected by pipelines. The arcs show the possible routes. The number on each arc gives the cost, in thousands of pounds, of laying that particular section.
  1. Use Kruskal's algorithm to obtain a minimum spanning tree for the network, giving the order in which you selected the arcs.
    (4)
  2. Draw your minimum spanning tree and find the least cost of the pipelines.
    (3)
Question 2 (Prim's Algorithm):
Part (a):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
First 4 arcs correctM1 Tree growing in a connected manner
Correct answerA1 c.a.o.
Starting at \(A\): \(AG, GC, GF, FD\) for M1
Starting at \(B\): \(BC, CG, GF, FD\) for M1
Starting at \(C\): \(CG, GF, FD, DE\) for M1
Starting at \(D\): \(DF, FG, GC, DE\) for M1
Starting at \(E\): \(ED, DF, FG, GC\) for M1
Starting at \(F\): \(FD, FG, GC, DE\) for M1
Starting at \(G\): \(GC, GF, FD, DE\) for M1
Part (a) worth 4 marks; if using Prim's get 2 marks maximum Put S.C. in margin
Q5a Ascending
Mark As MISREAD - unless they reverse in (a)
AnswerMarks
## Left to RightRight to Left
Question 5a (Left to Right sequence):
AnswerMarks Guidance
AnswerMark Guidance
\(90, 50\) circledB1 First two values identified
\(90, 55\) circledB1
\(90, 40\) circledB1
\(90, 20\) circledB1
\(90, 33\) circledB1
\(90, 30\) circledB1
\(90, 25\) circledB1
\(90, 45\) circledB1
\(55, 40\) circled → (MIA) Median In Answer noted
\(55, 20\) circledB1
\(55, 35\) circledB1 (AIN) noted
\(55, 30\) circledB1
\(55, 25\) circledB1
\(55, 45\) circledB1
\(50, 20\) circledB1 (AIN)
\(50, 35\) circledB1
\(50, 30\) circledB1
\(50, 25\) circledB1
\(50, 45\) circledB1
\(40, 20\) circled → (AIN)
\(42, 35\) circledB1
\(40, 30\) circledB1
\(40, 25\) circledB1
\(35, 30\) circledB1
\(35, 25\) circledB1
\(30, 25\) circledB1
Stop Now select (a) LAs
Question 5a (Right to Left sequence):
AnswerMarks Guidance
AnswerMark Guidance
\(30, 25\) circledB1 (MIA) noted
\(35, 25\) circledB1
\(40, 20\) circledB1
\(55, 20\) circledB1
\(50, 20\) circledB1
\(90, 22\) circledB1 (AIN) noted
\(40, 30\) circledB1
\(55, 30\) circledB1
\(50, 30\) circledB1
\(90, 30\) circledB1
\(40, 33\) circled → (AIN)
\(55, 33\) circledB1
\(50, 33\) circledB1
\(90, 33\) circledB1
\(55, 40\) circledB1
\(50, 40\) circledB1
\(90, 40\) circledB1
\(55, 45\) circledB1
\(50, 45\) circledB1
\(90, 45\) circledB1
\(90, 50\) circledB1
\(90, 55\) circledB1
Stop Now select (a) LAs
> Note: Now subject (a) 2A's indicated at bottom of both columns
## Question 2 (Prim's Algorithm):

### Part (a):

| Answer/Working | Marks | Guidance |
|---|---|---|
| First 4 arcs correct | M1 | Tree growing in a connected manner |
| Correct answer | A1 | c.a.o. |
| Starting at $A$: $AG, GC, GF, FD$ | | for M1 |
| Starting at $B$: $BC, CG, GF, FD$ | | for M1 |
| Starting at $C$: $CG, GF, FD, DE$ | | for M1 |
| Starting at $D$: $DF, FG, GC, DE$ | | for M1 |
| Starting at $E$: $ED, DF, FG, GC$ | | for M1 |
| Starting at $F$: $FD, FG, GC, DE$ | | for M1 |
| Starting at $G$: $GC, GF, FD, DE$ | | for M1 |
| Part (a) worth 4 marks; if using Prim's get 2 marks maximum | | Put S.C. in margin |

# Q5a Ascending

**Mark As MISREAD** - unless they reverse in (a)

## Left to Right | Right to Left

---

### Question 5a (Left to Right sequence):

| Answer | Mark | Guidance |
|--------|------|----------|
| $90, 50$ circled | B1 | First two values identified |
| $90, 55$ circled | B1 | |
| $90, 40$ circled | B1 | |
| $90, 20$ circled | B1 | |
| $90, 33$ circled | B1 | |
| $90, 30$ circled | B1 | |
| $90, 25$ circled | B1 | |
| $90, 45$ circled | B1 | |
| $55, 40$ circled → **(MIA)** | | Median In Answer noted |
| $55, 20$ circled | B1 | |
| $55, 35$ circled | B1 | **(AIN)** noted |
| $55, 30$ circled | B1 | |
| $55, 25$ circled | B1 | |
| $55, 45$ circled | B1 | |
| $50, 20$ circled | B1 | **(AIN)** |
| $50, 35$ circled | B1 | |
| $50, 30$ circled | B1 | |
| $50, 25$ circled | B1 | |
| $50, 45$ circled | B1 | |
| $40, 20$ circled → **(AIN)** | | |
| $42, 35$ circled | B1 | |
| $40, 30$ circled | B1 | |
| $40, 25$ circled | B1 | |
| $35, 30$ circled | B1 | |
| $35, 25$ circled | B1 | |
| $30, 25$ circled | B1 | |
| **Stop** | | Now select **(a) LAs** |

---

### Question 5a (Right to Left sequence):

| Answer | Mark | Guidance |
|--------|------|----------|
| $30, 25$ circled | B1 | **(MIA)** noted |
| $35, 25$ circled | B1 | |
| $40, 20$ circled | B1 | |
| $55, 20$ circled | B1 | |
| $50, 20$ circled | B1 | |
| $90, 22$ circled | B1 | **(AIN)** noted |
| $40, 30$ circled | B1 | |
| $55, 30$ circled | B1 | |
| $50, 30$ circled | B1 | |
| $90, 30$ circled | B1 | |
| $40, 33$ circled → **(AIN)** | | |
| $55, 33$ circled | B1 | |
| $50, 33$ circled | B1 | |
| $90, 33$ circled | B1 | |
| $55, 40$ circled | B1 | |
| $50, 40$ circled | B1 | |
| $90, 40$ circled | B1 | |
| $55, 45$ circled | B1 | |
| $50, 45$ circled | B1 | |
| $90, 45$ circled | B1 | |
| $90, 50$ circled | B1 | |
| $90, 55$ circled | B1 | |
| **Stop** | | Now select **(a) LAs** |

> **Note:** Now subject **(a) 2A's** indicated at bottom of both columns
2.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
  \includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-3_708_1096_360_408}
\end{center}
\end{figure}

Figure 1 shows 7 locations $A , B , C , D , E , F$ and $G$ which are to be connected by pipelines. The arcs show the possible routes. The number on each arc gives the cost, in thousands of pounds, of laying that particular section.
\begin{enumerate}[label=(\alph*)]
\item Use Kruskal's algorithm to obtain a minimum spanning tree for the network, giving the order in which you selected the arcs.\\
(4)
\item Draw your minimum spanning tree and find the least cost of the pipelines.\\
(3)
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2001 Q2 [7]}}
This paper (7 questions)
View full paper
Q1 5 Q2 7 Q3 7 Q4 11 Q5 12 Q6 16 Q7 17