myUASARevision for UASA
More
My progress
Mathematics questions, chapter 5
Nama / NameKelas / ClassTarikh / Date

Network in Graph Theory

45 marks. Use Practice to check each answer as you go, or Exam to answer everything first. Show your working for Section B.

Section A: objective questions

12 marks
Choose the correct answer. Each question carries 1 mark.
1

Question 1

In a graph, a line that joins two vertices is called a(n)
Show answerHide answer
B
The dots are vertices and the lines joining them are edges. A loop is a special edge that starts and ends at the same vertex.
For the teacher: Remembering, low difficulty, standard 5.1.1
Textbook p. 130
2

Question 2

A social network is drawn as a graph. What do the edges represent?
Show answerHide answer
B
In a social network the vertices are individuals, groups or organisations, and the edges are the relationships between them.
For the teacher: Understanding, low difficulty, standard 5.1.1
Textbook p. 130
3

Question 3

Diagram 1 shows a simple graph. What is the sum of the degrees of all the vertices?
Simple graph with vertices A to F and eight edges AB, AC, BC, BD, CE, DE, DF, EF
Diagram 1
Show answerHide answer
C
There are 8 edges. Sum of degrees = 2 × 8 = 16. The number 8 is just the number of edges, and 6 is the number of vertices.
For the teacher: Applying, low difficulty, standard 5.1.1
Textbook p. 131
4

Question 4

The sum of the degrees of a simple graph is 18. How many edges does the graph have?
Show answerHide answer
B
Sum of degrees = 2 × number of edges, so the number of edges = 18 ÷ 2 = 9.
For the teacher: Applying, low difficulty, standard 5.1.1
Textbook p. 131
5

Question 5

Which set of vertex degrees can be the degrees of a graph?
Show answerHide answer
C
A graph needs an even sum of degrees. 3 + 3 + 3 + 2 + 1 = 12 is even. The other sets add to 13, 13 and 11, which are odd.
For the teacher: Analysing, medium difficulty, standard 5.1.1
Textbook p. 133
6

Question 6

Diagram 2 shows a graph with a loop at vertex R. What is the degree of vertex R?
Triangle P, Q, R with edges PQ, QR, PR and a loop at R
Diagram 2
Show answerHide answer
D
Edges QR and PR give 2. The loop adds 2 more. d(R) = 2 + 2 = 4. Counting the loop as 1 gives 3.
For the teacher: Understanding, medium difficulty, standard 5.1.1
Textbook p. 133
7

Question 7

Diagram 3 shows a directed graph. What is dout(B), the number of edges coming out of B?
Directed graph with arrows B to A, C to A, B to C and D to C
Diagram 3
Show answerHide answer
D
The arrows leaving B are B to A and B to C, so dout(B) = 2. No arrow goes into B.
For the teacher: Understanding, low difficulty, standard 5.1.2
Textbook p. 136
8

Question 8

Which of the following is a weighted graph?
Show answerHide answer
C
A weighted graph has a value on each edge, such as distance, time or cost. The other three only show relationships.
For the teacher: Remembering, low difficulty, standard 5.1.2
Textbook p. 137
9

Question 9

A tree has 9 vertices. How many edges does it have?
Show answerHide answer
A
A tree with n vertices has n − 1 edges, so 9 − 1 = 8.
For the teacher: Applying, low difficulty, standard 5.1.3
Textbook p. 139
10

Question 10

A connected graph has 7 vertices and 7 edges. Which statement is true?
Show answerHide answer
B
A tree with 7 vertices has 7 − 1 = 6 edges. With 7 edges there is a closed path, so two vertices can be joined in more than one way.
For the teacher: Analysing, medium difficulty, standard 5.1.3
Textbook p. 140
11

Question 11

Diagram 4 shows an undirected weighted graph. What is the minimum total weight of a tree from this graph?
Weighted graph: AB 7, AC 5, BC 8, BD 6, CD 9, CE 4, DE 10
Diagram 4
Show answerHide answer
C
5 vertices need 4 edges. Choose the smallest weights that do not form a closed path: 4 (CE), 5 (AC), 6 (BD), 7 (AB). Total = 4 + 5 + 6 + 7 = 22. Weight 8 is skipped because B and C are already linked.
For the teacher: Applying, high difficulty, standard 5.1.3
Textbook p. 141
12

Question 12

Graph G has V = {P, Q, R, S} and E = {(P, Q), (Q, R), (R, S), (S, P)}. Which of these is a subgraph of G?
Show answerHide answer
A
The vertices and the edges must come from G. (P, R) is not an edge of G, (Q, S) is not an edge of G, and T is not a vertex of G.
For the teacher: Understanding, low difficulty, standard 5.1.3
Textbook p. 139

Section B: structured questions

33 marks
Answer all questions. Show your working.
13

Question 13

A graph has V = {P, Q, R, S, T} and E = {(P, Q), (P, Q), (Q, R), (R, S), (S, T), (T, T)}.
[1 mark] (a)State n(V) and n(E).
Show answerHide answer
Tick each point you got.
[3 marks] (b)Find the degree of each vertex and the sum of the degrees.
Show answerHide answer
Tick each point you got.
[1 mark] (c)Explain why this is not a simple graph.
Show answerHide answer
Tick each point you got.
For the teacher: Applying, low difficulty, standard 5.1.1
Textbook p. 132
14

Question 14

Diagram 5 shows a directed graph.
Directed graph with arrows P to Q, Q to R, R to S, S to P, P to R and a loop at S
Diagram 5
[2 marks] (a)State din(S) and dout(S).
Show answerHide answer
Tick each point you got.
[2 marks] (b)Find the sum of the degrees of all the vertices.
Show answerHide answer
Tick each point you got.
[1 mark] (c)The edge (S, S) is a
Show answerHide answer
loop
An edge that starts and ends at the same vertex is a loop.
For the teacher: Understanding, medium difficulty, standard 5.1.2
Textbook p. 135
15

Question 15

Diagram 6 shows the one-way cycling routes, in km, from the school hall H to the stadium S. A, B and C are junctions.
Directed weighted graph: H to A 3.2, H to B 2.5, A to B 1.1, A to C 2.4, B to C 3.0, B to S 4.2, C to S 1.8
Diagram 6
[2 marks] (a)Find the shortest route from H to S and its distance.
Show answerHide answer
Tick each point you got.
[2 marks] (b)Find the longest route from H to S and its distance.
Show answerHide answer
Tick each point you got.
[2 marks] (c)A cyclist wants a route of more than 7 km but less than 8 km. State the routes that can be chosen.
Show answerHide answer
Tick each point you got.
For the teacher: Applying, medium difficulty, standard 5.1.2
Textbook p. 138
16

Question 16

Diagram 7 shows an undirected weighted graph of five villages. The weights are distances in km.
Weighted graph: AB 4, BC 6, CD 3, DE 5, EA 7, BE 2
Diagram 7
[1 mark] (a)How many edges must be removed to form a tree?
Show answerHide answer
Tick each point you got.
[2 marks] (b)State the edges that are removed to give a tree with minimum total weight.
Show answerHide answer
Tick each point you got.
[1 mark] (c)Find the minimum total weight.
Show answerHide answer
Tick each point you got.
For the teacher: Applying, medium difficulty, standard 5.1.3
Textbook p. 141
17

Question 17

Table 1 shows the two clubs each pupil has joined.
PupilClubs
HanaChess, Drama
IqbalChess, Robotics
JiaDrama, Robotics
KumarRobotics, Music
LinaMusic, Chess
The information is shown as a graph. The vertices are the clubs and the edges are the pupils.
[2 marks] (a)Write the set of edges E as pairs of clubs.
Show answerHide answer
Tick each point you got.
[1 mark] (b)State the degree of the vertex Robotics and what it means.
Show answerHide answer
Tick each point you got.
[2 marks] (c)State the sum of the degrees of the graph and explain how it is related to the number of pupils.
Show answerHide answer
Tick each point you got.
For the teacher: Analysing, medium difficulty, standard 5.1.4
Textbook p. 144
18

Question 18

A family of 4 adults travels from town X to town Y. The bus fare is RM42 per adult and takes 4 hours. The train fare is RM28 per adult and takes 6 hours. A shared car costs RM90 for the whole car and takes 3.5 hours.
[3 marks] (a)Calculate the total cost of each choice for the 4 adults.
Show answerHide answer
Tick each point you got.
[2 marks] (b)The family must arrive in less than 4 hours. Which choice should they take? Give a reason.
Show answerHide answer
Tick each point you got.
For the teacher: Evaluating, high difficulty, standard 5.1.5
Textbook p. 146
19

Question 19

Draw a simple graph with 5 vertices whose degrees are 1, 1, 2, 3 and 3.
[1 mark] (a)Show that such a graph can exist.
Show answerHide answer
Tick each point you got.
[2 marks] (b)Draw the graph, with no loops and no multiple edges.
Show answerHide answer
For example A-B, B-C, C-D, D-E and B-D: d(A) = 1, d(B) = 3, d(C) = 2, d(D) = 3, d(E) = 1.
Tick each point you got.
For the teacher: Creating, high difficulty, standard 5.1.1
Textbook p. 133