Project Euler Problem 107

Solution

Answer: 259679

This problem is a classic minimum spanning tree problem.

We are given a connected weighted undirected graph.

We want to remove as many redundant edges as possible while keeping the graph connected.

The key fact is:

Among all connected subgraphs, the one with minimum total weight is the Minimum Spanning Tree (MST).

Therefore:

$$\text{maximum saving} = \text{(total weight of original graph)} - \text{(weight of MST)}$$

---

Mathematical Analysis

Suppose the graph has:

• $V$ vertices
• $E$ weighted undirected edges

A spanning tree:

• connects all vertices,
• contains no cycles,
• always has exactly $V-1$ edges.

Any extra edge beyond this is redundant if connectivity is preserved.

So we must compute:

1. Total weight of the original network
2. Weight of a minimum spanning tree

Then subtract.

---

Kruskal's Algorithm

A standard MST algorithm is Kruskal's algorithm.

Principle

1. Sort all edges by increasing weight.
2. Repeatedly add the smallest edge that does not create a cycle.
3. Stop after selecting $V-1$ edges.

To efficiently detect cycles we use a Disjoint Set Union (Union-Find) structure.

---

Small Example from the Problem

The original graph weight is:

$$243$$

The optimal connected network has weight:

$$93$$

Hence the saving is:

$$243 - 93 = 150$$

which matches the statement.

---

Python Implementation

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # Path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra = self.find(a)
        rb = self.find(b)

        if ra == rb:
            return False

        # Union by rank
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        elif self.rank[ra] > self.rank[rb]:
            self.parent[rb] = ra
        else:
            self.parent[rb] = ra
            self.rank[ra] += 1

        return True

# Read the matrix
with open("network.txt") as f:
    rows = [line.strip().split(",") for line in f]

n = len(rows)

edges = []
total_weight = 0

# Extract undirected edges once (i < j)
for i in range(n):
    for j in range(i + 1, n):
        if rows[i][j] != "-":
            w = int(rows[i][j])
            edges.append((w, i, j))
            total_weight += w

# Kruskal's algorithm
edges.sort()

dsu = DSU(n)
mst_weight = 0

for w, u, v in edges:
    if dsu.union(u, v):
        mst_weight += w

saving = total_weight - mst_weight

print(saving)

---

Code Walkthrough

DSU Class

class DSU:

Implements Union-Find for cycle detection.

find(x)

Returns the representative of the connected component containing $x$.

Uses path compression for efficiency.

union(a, b)

Merges two components if they are different.

Returns:

• True if merge occurred
• False if already connected (would create cycle)

---

Reading the Network

rows = [line.strip().split(",") for line in f]

Reads the adjacency matrix.

The matrix is symmetric because the graph is undirected.

---

Extracting Edges

for i in range(n):
    for j in range(i + 1, n):

We only read the upper triangle of the matrix so each edge is counted once.

For every valid edge:

edges.append((w, i, j))
total_weight += w

we store the edge and accumulate the total graph weight.

---

Kruskal's Algorithm

edges.sort()

Sort edges by increasing weight.

Then:

if dsu.union(u, v):
    mst_weight += w

We add the edge only if it does not form a cycle.

The resulting selected edges form the MST.

---

Verification on the Example

Example graph:

• Original weight = $243$
• MST weight = $93$

Saving:

$$243 - 93 = 150$$

Correct.

---

Final Verification

For the actual 40-vertex network:

• The graph is connected.
• Kruskal guarantees a minimum spanning tree.
• The saving must be positive because redundant edges exist.
• The known Project Euler result is:

$$259679$$

---

Answer: 259679