D2 June 2008 Q2
2. Explain what is meant, in a network, by
| Scheme | Marks |
|---|---|
| A walk is a finite sequence of arcs such that the end vertex of one arc is the start vertex of the next. | B2, 1, 0 |
| (2) |
Notes
1B1: Probably one of the two below but accept correct relevant statement – bod gets B1, generous.
2B1: A good clear complete answer: End vertex = start vertex + finite.
| Scheme | Marks |
|---|---|
| A tour is a walk that visits every vertex, returning to its starting vertex. | B2, 1, 0 |
| (2) | |
| (4 marks) |
Notes
1B1: Probably one of the two below but accept correct relevant statement – bod gets B1, generous.
2B1: A good clear complete answer: Every vertex + return to start.
From the D1 and D2 glossaries
D1
A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.
A cycle (circuit) is a closed path, ie the end vertex of the last edge is the start vertex of the first edge.
D2
A walk in a network is a finite sequence of edges such that the end vertex of one edge is the start vertex of the next.
A walk which visits every vertex, returning to its starting vertex, is called a tour.