Worksheet Ch 5: Network in Graph Theory

Section A • Bahagian A [12 Marks]

Question 1 [4 Marks]

A graph $G = (V, E)$ has vertices $V = \{P, Q, R, S, T\}$. The degrees of the vertices are given as $d(P) = 3$, $d(Q) = 4$, $d(R) = 2$, $d(S) = 3$, and $d(T) = 2$.

(a) Calculate the sum of degrees, $\sum d(v)$. [1 mark]
(b) Determine the number of edges, $E$, in this graph. [2 marks]
(c) State whether this graph can be a tree. Give your reason. [1 mark]

(a) $\sum d(v) = 3 + 4 + 2 + 3 + 2$

$= 14$

(b) $\sum d(v) = 2E \implies 14 = 2E$

$$E = 7\text{ edges}$$

K1 N1

No, because $E = 7 \neq 4$.

Question 2 [4 Marks]

A graph has 4 vertices with degrees $3, 3, 2, 2$.

(a) Determine if such a graph can be drawn. Justify your answer using Euler's theorem. [2 marks]
(b) If a loop is added to one of the vertices of degree 2, what is its new degree? [2 marks]

(a) $\sum d(v) = 3 + 3 + 2 + 2 = 10$ (Even number). Number of vertices with odd degrees is 2 (even).

Yes, the graph can be drawn because the sum of degrees is an even number.

K1 N1

(b) A loop adds 2 to the degree of the vertex

$$\text{New degree} = 2 + 2 = 4$$

K1 N1

Question 3 [4 Marks]

State TWO conditions that must be fulfilled for a subgraph to be classified as a tree. [4 marks]

Any two of the following:

The graph is connected with no loops or multiple edges.
The number of edges is exactly one less than the number of vertices ($E = V - 1$).
There are no closed circuits / cycles.

Section B • Bahagian B (HOTS / KBAT) [18 Marks]

Question 4 (Fiber Optic Cable Minimum Spanning Tree) [9 Marks]

Telekom Malaysia plans to lay underground high-speed fiber-optic cables connecting six towns: $A, B, C, D, E, F$. The distances between connected towns in kilometers are given below:

$AB = 15\text{ km}$, $AC = 12\text{ km}$, $BC = 10\text{ km}$, $BD = 20\text{ km}$

$CD = 18\text{ km}$, $CE = 25\text{ km}$, $DE = 14\text{ km}$, $DF = 22\text{ km}$, $EF = 16\text{ km}$

(a) State the number of edges required to form a tree connecting all 6 towns. [2 marks]
(b) Determine the minimum total length of fiber optic cable needed by constructing a minimum spanning tree. [5 marks]
(c) If the cost of laying cable is RM8,000 per km, calculate the total minimum expenditure. [2 marks]

(a) Edges in tree: $E = V - 1 = 6 - 1$

$= 5\text{ edges}$

(b) Select 5 shortest edges avoiding cycles (Kruskal's algorithm):

1. $BC = 10\text{ km}$
2. $AC = 12\text{ km}$
3. $DE = 14\text{ km}$
4. $EF = 16\text{ km}$
5. $CD = 18\text{ km}$ (connects $\{A,B,C\}$ with $\{D,E,F\}$ without forming a cycle)

$$\text{Total Length} = 10 + 12 + 14 + 16 + 18 = \mathbf{70}\text{ km}$$

K3 N2

$$\text{Cost} = 70 \times \text{RM } 8,000 = \mathbf{RM\ 560,000}$$

K1 N1

Question 5 (Directed Highway Network & Shortest Route) [9 Marks]

A courier van departs from Depot $O$ to delivery point $Z$ through a directed highway network with toll costs shown below:

$O \to A: \text{RM } 4$, $O \to B: \text{RM } 7$

$A \to B: \text{RM } 2$, $A \to C: \text{RM } 8$

$B \to C: \text{RM } 5$, $B \to D: \text{RM } 9$

$C \to Z: \text{RM } 6$, $D \to Z: \text{RM } 3$

(a) List all possible valid routes from Depot $O$ to delivery point $Z$. [4 marks]
(b) Determine the cheapest route and its minimum total toll cost. [3 marks]
(c) If route $B \to C$ is closed for maintenance, state the best alternative route and the additional cost incurred. [2 marks]

(a) Valid routes and costs:

Route 1: $O \to A \to C \to Z = 4 + 8 + 6 = \text{RM } 18$
Route 2: $O \to A \to B \to C \to Z = 4 + 2 + 5 + 6 = \text{RM } 17$
Route 3: $O \to A \to B \to D \to Z = 4 + 2 + 9 + 3 = \text{RM } 18$
Route 4: $O \to B \to C \to Z = 7 + 5 + 6 = \text{RM } 18$
Route 5: $O \to B \to D \to Z = 7 + 9 + 3 = \text{RM } 19$

(b) Minimum cost route:

Route $O \to A \to B \to C \to Z$ with cost $\mathbf{RM\ 17}$

K1 N2

Additional cost $= 18 - 17 = \mathbf{RM\ 1}$

K1 N1