T3T4 Review — Networks and Graphs — Grade 10

Graph terminology. Fluency

A graph has vertices A, B, C, D, E with edges AB, AC, BC, BD, CD, DE.

(a) How many vertices and edges does the graph have?
(b) State the degree of each vertex.
(c) Verify the handshaking lemma.
(d) Does an Euler circuit exist? Explain.

Handshaking lemma and degree sequences. Fluency

(a) A graph has 9 edges. What is the sum of all vertex degrees?
(b) Can a graph have degree sequence (5, 4, 3, 2, 2)? Why or why not?
(c) A complete graph K₅ has how many edges?
(d) A tree with 10 vertices has how many edges?

Kruskal's MST algorithm. Fluency

A weighted graph has edges: P–Q=6, P–R=9, Q–R=4, Q–S=8, R–S=5, R–T=7, S–T=3.

(a) Sort the edges in increasing order of weight.
(b) Apply Kruskal's algorithm to find the MST.
(c) What is the total MST weight?
(d) How many edges does any spanning tree of this graph contain?

Dijkstra's shortest path. Fluency

Edge weights: A–B=7, A–C=3, B–D=2, C–B=1, C–D=8, B–E=5, D–E=4.

(a) Set up the initial distance table for Dijkstra's algorithm from A.
(b) Complete Dijkstra's algorithm to find shortest distances from A to all vertices.
(c) What is the shortest path from A to E?
(d) Which vertex is closest to A (excluding A itself)?

Reading a weighted network. Understanding

The diagram shows a weighted network of 6 nodes.

Weighted network (node 6 is the destination).

(a) Find all paths from node 1 to node 6 and their total weights.
(b) What is the shortest path from node 1 to node 6?
(c) Apply Kruskal's algorithm to find the MST of this network.
(d) What is the degree of node 3 in the original network, and in the MST?

Euler paths and circuits in context. Understanding

A mail carrier must deliver to every street in a suburb. The street network has 8 intersections with degrees: 4, 4, 2, 3, 3, 2, 4, 2.

(a) How many edges (streets) does the network have?
(b) Can the mail carrier complete a route that covers every street exactly once and returns to the starting point? Explain.
(c) What is the minimum number of streets the carrier must repeat?
(d) If the council adds one new street connecting the two odd-degree intersections, what happens?

Spanning trees. Understanding

(a) A graph has 12 vertices. How many edges does its spanning tree have?
(b) True or false: A minimum spanning tree always contains the shortest edge in the graph.
(c) A spanning tree has 15 edges. How many vertices does the original graph have?
(d) Explain why adding any edge to a spanning tree creates a cycle.

Critical path analysis. Understanding

A construction project has activities: Start→A(5), Start→B(3), A→C(4), A→D(6), B→D(8), C→End(2), D→End(1).

(a) List all paths from Start to End and find their durations.
(b) Identify the critical path(s).
(c) What is the float for activity C?
(d) Activity B is delayed by 2 days. Does this delay the project? Explain.

Comparing network algorithms. Problem Solving

A logistics company has 5 distribution centres (A–E) with road distances (km): A–B=50, A–C=30, B–C=20, B–D=40, C–D=35, C–E=25, D–E=15.

(a) The company wants to build a private road network connecting all 5 centres at minimum cost. Find the MST using Kruskal's algorithm.
(b) A driver at A must reach D as quickly as possible. Use Dijkstra's to find the shortest route.
(c) Is the MST the same as the shortest-path tree from A? Explain any differences.
(d) The company inspects every private road monthly. What type of route does the inspector need, and does one exist for the MST?

Network robustness and bridges. Problem Solving

A telecommunications network connects 7 cities. The MST for the network has total cost $84 000. Two extra redundant cables are added at $12 000 and $15 000 each.

(a) What is the total network cost after adding the redundant cables?
(b) A “bridge” in a graph is an edge whose removal disconnects the graph. In the MST of a connected graph, how many bridges are there?
(c) After adding the 2 redundant cables, how many bridges remain?
(d) The company wants zero bridges (every edge can fail without disconnecting the network). What is the minimum number of redundant cables that must be added to the MST?

Full algorithm application. Problem Solving

A theme park has 6 attractions (A–F) with walking times (minutes): A–B=4, A–C=7, B–C=3, B–D=6, C–D=5, C–E=8, D–E=2, D–F=9, E–F=4.

(a) A visitor starts at A and wants to reach F as fast as possible. Find the shortest route using Dijkstra's algorithm.
(b) The park wants to install a monorail connecting all 6 attractions at minimum track length. Find the MST.
(c) A cleaner must inspect every path in the park. Does an Euler circuit exist for the original network?
(d) The park adds a direct path D–A = 11 minutes. Does this change the shortest route A to F?

Networks in the real world. Problem Solving

A city council is planning infrastructure for a new suburb with 8 zones (numbered 1–8). They have three separate goals.

(a) Goal 1: Connect all zones with water pipes at minimum cost. Which algorithm should they use, and what key property does the result have?
(b) Goal 2: Position an emergency services depot so response time to any zone is minimised. How should the council model this?
(c) Goal 3: Rubbish trucks must collect from every street. The zone network has exactly 4 odd-degree intersections. How many extra street passes are required at minimum?
(d) The council's project manager builds an activity network for the suburb construction. The critical path is 18 months. Two non-critical activities have floats of 3 months and 5 months. If the project must finish in 16 months, by how much must the critical path be shortened, and which activities are candidates for acceleration?