A2 June 2023 Q1

EdexcelCurrent spec7 marksGraphs & NetworksShortest Path

1.

Figure 1: graph G on vertices A, B, C, D and E with edges EA, AB, AC, EB, ED, DB, DC and CB
Figure 1

Figure 1 shows the graph G.

(a) State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer. (1)
(b) Write down an example of a Hamiltonian cycle on G. (1)
(c) State whether or not G is planar, justifying your answer. (1)
(d) State the number of arcs that would need to be added to G to make the graph \(K_5\) (1)
Figure 2: the same graph with weights EA 5, AB 10, EB 4, ED 7, DB 8, AC 15, DC 2, CB 3
Figure 2

Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd’s algorithm is to be used to find the complete network of shortest times between the five villages.

(e) For the network represented in Figure 2, complete the initial time matrix in the answer book. (1)

Initial time matrix (answer book)

ABCDE
A–                
B    –            
C        –        
D            –    
E                –

The time matrix after four iterations of Floyd’s algorithm is shown in Table 1.

ABCDE
A–1013155
B10–354
C133–27
D1552–7
E5477–

Table 1

(f) Perform the final iteration of Floyd’s algorithm that follows from Table 1, showing the time matrix for this iteration. (2)
‹ Previous3 of 16 in Graphs & NetworksNext ›