Worksheet Chapter 5: Network Theory

1. A graph has vertices V = {A, B, C, D, E}. The degrees of vertices are d(A) = 2, d(B) = k, d(C) = 3, d(D) = 1, d(E) = 4. Given that the graph has 7 edges, find the value of k.

2. The diagram of a computer network consists of 5 servers (P, Q, R, S, T). The bandwidth cost (in RM) between connected servers is given as follows: PQ = 25, PR = 18, PS = 30, QR = 12, QS = 20, RS = 15, ST = 22, RT = 28. (a) What is the minimum number of connections needed to ensure all 5 servers are interconnected? (b) Construct the minimum spanning tree connections and determine the minimum total cost to link all 5 servers.

3. Fill in the blank: The sum of degrees of all vertices in any graph is equal to ________ times the number of edges.

4. True or False: A tree with 12 vertices has exactly 11 edges.

5. The table below shows the distances (in km) between four towns A, B, C, and D: AB = 12 km, AC = 15 km, AD = 8 km, BC = 10 km, CD = 14 km. (a) Draw or list the edges required to form a minimum spanning tree. (b) Calculate the minimum total distance to connect all four towns.

6. Given a directed graph with vertices V = {P, Q, R, S} and edges E = {(P, Q), (P, R), (Q, R), (R, S), (S, P)}. (a) Determine the in-degree and out-degree of vertex R. (b) State the total degree of vertex R.

7. A simple graph has 6 vertices. The degree of each vertex is 3. (a) Calculate the sum of degrees of the graph. (b) Find the total number of edges in this graph.

8. True or False: A graph can contain an odd sum of degrees if it has a directed loop.

9. State two differences between a simple graph and a graph that contains loops and multiple edges.

10. Which of the following conditions guarantees that a graph G is a tree?