- Question 4 20 Marks Suppose That There Are 5 Intersections In A Road Network Which Are A B C D And E Below Are The 1 (142.54 KiB) Viewed 12 times
QUESTION 4 (20 Marks) Suppose that there are 5 intersections in a road network which are A, B, C, D and E. Below are the pair of intersections that are connected by the one-way road. A to B B to C C to D D to E E to B E to C Draw a directed graph to represent the situation above where vertices represent the intersections, and the directed edges represent the one-way road. (3 marks) Find the adjacency matrix for graph drawn in part (i). (2 marks) (b) Level 1 (c) (i) (d) (ii) Given an undirected graph in Figure 2 as follows: R 0 AQ010-3-1-MCFC Figure 2 Explain whether Euler circuit or Euler path exists in Figure 2. Asia Pacific University of Technology and Innovation a E b a Final Exam Refer to part (b)(i), list the vertices of the Euler circuit or Euler path exists. Show that the Hamilton circuit exists in Figure 2. (5 marks) Figure 3 is an undirected graph represents the meetings that will be attended by the staff in a company within the first week of next month. The vertices of the graph represent the meetings and the edges connect the meetings that require to attend by the same staff. Find the minimum number of slots that can be scheduled for the meeting so that all staff can attend the meeting. e (2 marks) Figure 4 20220704 Figure 3 (2 marks) Show that the graph in Figure 4 is a planar graph by drawing it without any crossing of the edges. b с Page 4 of 6 (3 marks) (3 marks)