Practice: Laying Fibre Between Village Halls

Seven halls and the cost of trenching between pairs: connect them all for the least money, and justify one choice.

Kruskal's algorithm and the cut property are practised here on a graph you have not seen: trace the algorithm, then name a cut that proves one of its choices safe. A rural council wants fibre broadband between seven village halls. Fibre runs both ways, so the graph is undirected, and any hall can relay to any other it is connected to. The cost of trenching each possible link, in thousands of pounds, is in the table below; links that are not listed cannot be dug.

The eleven links the council could dig, with their cost in thousands of pounds
Link	Cost
Ashby to Barton	12
Ashby to Cleeve	4
Barton to Cleeve	9
Barton to Denby	6
Cleeve to Denby	11
Cleeve to Elton	7
Denby to Elton	3
Denby to Felling	14
Elton to Felling	10
Elton to Grange	13
Felling to Grange	5

Run Kruskal's algorithm. Which links does the council dig, which does it skip, and what is the total cost?
Elton to Felling is the most expensive link in the answer. Name a cut whose lightest crossing edge is Elton to Felling, and so show that it belongs in the cheapest network.

Answer both parts, then compare with the run.

Kruskal's algorithm on the eleven links, cheapest first
Link	Cost	Taken	Reason
Denby to Elton	3	Yes	Joins Denby and Elton
Ashby to Cleeve	4	Yes	Joins Ashby and Cleeve
Felling to Grange	5	Yes	Joins Felling and Grange
Barton to Denby	6	Yes	Joins Barton to Denby and Elton
Cleeve to Elton	7	Yes	Joins Ashby and Cleeve to Barton, Denby and Elton
Barton to Cleeve	9	No	Barton and Cleeve are already connected, so it would close a cycle
Elton to Felling	10	Yes	Joins Felling and Grange to the other five; six links connect seven halls
Cleeve to Denby	11	Not reached	Every hall is connected
Ashby to Barton	12	Not reached	Every hall is connected
Elton to Grange	13	Not reached	Every hall is connected
Denby to Felling	14	Not reached	Every hall is connected

The council digs six links, Denby to Elton, Ashby to Cleeve, Felling to Grange, Barton to Denby, Cleeve to Elton and Elton to Felling, for 35 thousand pounds. It skips Barton to Cleeve, the only link examined that would close a cycle: Barton reaches Cleeve through Denby and Elton. The run also checked all 144 ways of connecting the halls, and 35 is the least, held by this network alone.
Put Felling and Grange on one side and the other five halls on the other. Three links cross: Elton to Felling at 10, Elton to Grange at 13 and Denby to Felling at 14. Elton to Felling is the lightest, so by the cut property it belongs in the cheapest network, even though it costs more than any other link the council digs. Every network has to cross that cut somewhere, and 10 is the least it can pay to do so.

fibre.pypy

import itertools

HALLS = ["Ashby", "Barton", "Cleeve", "Denby", "Elton", "Felling", "Grange"]
COSTS = [
    ("Ashby", "Barton", 12), ("Ashby", "Cleeve", 4), ("Barton", "Cleeve", 9), ("Barton", "Denby", 6),
    ("Cleeve", "Denby", 11), ("Cleeve", "Elton", 7), ("Denby", "Elton", 3), ("Denby", "Felling", 14),
    ("Elton", "Felling", 10), ("Elton", "Grange", 13), ("Felling", "Grange", 5),
]


def kruskal(halls, costs):
    groups = {h: frozenset([h]) for h in halls}
    tree = []
    for u, v, cost in sorted(costs, key=lambda c: c[2]):
        if len(tree) == len(halls) - 1:
            print(f"{u}-{v} {cost}: not considered, every hall connected")
            continue
        if groups[u] == groups[v]:
            print(f"{u}-{v} {cost}: skip, closes a cycle")
            continue
        merged = groups[u] | groups[v]
        print(f"{u}-{v} {cost}: take, joins {sorted(groups[u])} and {sorted(groups[v])}")
        for h in merged:
            groups[h] = merged
        tree.append((u, v, cost))
    return tree


def connects(halls, edges):
    reach, frontier = {halls[0]}, [halls[0]]
    while frontier:
        h = frontier.pop()
        for u, v, _ in edges:
            for a, b in ((u, v), (v, u)):
                if a == h and b not in reach:
                    reach.add(b)
                    frontier.append(b)
    return len(reach) == len(halls)


tree = kruskal(HALLS, COSTS)
print("total:", sum(c for *_, c in tree))
trees = [t for t in itertools.combinations(COSTS, len(HALLS) - 1) if connects(HALLS, t)]
least = min(sum(c for *_, c in t) for t in trees)
print("spanning trees:", len(trees), "least:", least, "with it:", sum(1 for t in trees if sum(c for *_, c in t) == least))
side = {"Felling", "Grange"}
print("cut Felling Grange | rest:", ", ".join(f"{u}-{v} {c}" for u, v, c in COSTS if (u in side) != (v in side)))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

Denby-Elton 3: take, joins ['Denby'] and ['Elton']
Ashby-Cleeve 4: take, joins ['Ashby'] and ['Cleeve']
Felling-Grange 5: take, joins ['Felling'] and ['Grange']
Barton-Denby 6: take, joins ['Barton'] and ['Denby', 'Elton']
Cleeve-Elton 7: take, joins ['Ashby', 'Cleeve'] and ['Barton', 'Denby', 'Elton']
Barton-Cleeve 9: skip, closes a cycle
Elton-Felling 10: take, joins ['Ashby', 'Barton', 'Cleeve', 'Denby', 'Elton'] and ['Felling', 'Grange']
Cleeve-Denby 11: not considered, every hall connected
Ashby-Barton 12: not considered, every hall connected
Elton-Grange 13: not considered, every hall connected
Denby-Felling 14: not considered, every hall connected
total: 35
spanning trees: 144 least: 35 with it: 1
cut Felling Grange | rest: Denby-Felling 14, Elton-Felling 10, Elton-Grange 13

← → move through sections and cards