School Network Cabling: Networks
A school is planning to install network cables between five buildings: A, B, C, D, and E. The distances (in metres) between possible connections are: A-B: 100, A-C: 150, A-D: 200, B-C: 120, B-D: 180, B-E: 250, C-D: 100, C-E: 200, D-E: 150. The school wants to connect all buildings with the minimum total length of cable. They also want to ensure there is a backup path between the two main buildings, A and E, so that if one cable fails, there is an alternative route. The school has a budget of $5,000 for cabling, and cable costs $10 per metre plus a fixed installation cost of $500 per connection.
1. Find the minimum spanning tree (MST) for the network and calculate the total cable length and total cost (cable + installation).
Read the worked answer
List edges sorted by length: C-D (100), A-B (100), B-C (120), A-C (150), D-E (150), B-D (180), A-D (200), C-E (200), B-E (250). Kruskal's algorithm:
- Add C-D (100)
- Add A-B (100)
- Add B-C (120) (connects A,B to C,D)
- Next A-C (150) would create cycle A-B-C-A, skip.
- Add D-E (150) (connects E) Now all 5 vertices connected? Vertices: A,B,C,D,E. Edges: C-D, A-B, B-C, D-E. That's 4 edges, connected. MST edges: C-D, A-B, B-C, D-E. Total length = 100+100+120+150 = 470 m. Check if any cheaper? Could we use A-C instead of B-C? A-C=150 >120, so no. Could we use B-D instead of D-E? B-D=180 >150, so no. So MST length = 470 m. Cost: Cable cost = 470 × $10 = $4,700. Installation: 4 connections × $500 = $2,000. Total = $6,700. This exceeds the $5,000 budget, so the school cannot afford this MST within budget.
2. The school wants a backup path between A and E. Using the MST, what is the additional cable length and cost to add a direct connection between A and E? Is this within the budget? If not, suggest an alternative that provides a backup path between A and E with minimal additional cost, and calculate the new total cost.
Read the worked answer
Direct A-E connection is not listed in the possible connections, so cannot add direct. To provide a backup path between A and E, we need to add an edge that creates a cycle containing A and E. In the MST, the path between A and E is A-B-C-D-E (edges A-B, B-C, C-D, D-E). To create a cycle, we can add any edge that connects two vertices already connected, but must not be already in MST. The possible edges not in MST: A-C (150), B-D (180), A-D (200), C-E (200), B-E (250). Adding any of these creates a cycle. The cheapest is A-C (150) or D-E? D-E already in MST. So cheapest is A-C (150). Adding A-C creates cycle A-B-C-A, which includes A and C, but does it provide backup between A and E? The backup path between A and E would be A-C-D-E, using A-C, C-D, D-E. Yes, that works. Additional cable length = 150 m. Additional cost = 150×$10 + $500 = $1,500 + $500 = $2,000. New total cost = $6,700 + $2,000 = $8,700, exceeding budget. Alternative: Add C-E (200) creates cycle C-D-E-C, backup path A-B-C-E. Additional cost = 200×$10 + $500 = $2,500, total $9,200. Add B-D (180): backup path A-B-D-E, additional cost = 180×$10 + $500 = $2,300, total $9,000. Add A-D (200): backup path A-D-E, additional cost $2,500, total $9,200. Add B-E (250): backup path A-B-E, additional cost $3,000, total $9,700. The cheapest additional edge is A-C (150) with additional cost $2,000. However, even the cheapest backup exceeds budget. To stay within $5,000, the school would need to reduce costs, e.g., by negotiating installation or using cheaper cable, but with given costs, it's not possible. The minimal additional cost to provide backup is $2,000, making total $8,700, which is over budget by $3,700.