Spanning Trees and Route Problems

Kruskal’s Algorithm for a Spanning Tree #

Cheapest edge first, unless it closes a cycle.

Kruskal takes the cheapest edge that closes no cycle, until every vertex is joined

Join every town at the lowest total cost. The answer is a minimum spanning tree.

Sort the edges by weight and take the cheapest: A to C, weight 2.

Next cheapest is C to E, weight 3. It reaches a new town, so keep it.

A to B, weight 4, brings in B. Keep that one too.

B to C, weight 5, would close the cycle A-B-C. Reject it and move on.

B to D, weight 6, brings in the last town, so the tree is finished.

Five towns need four edges, and the total weight is 2 + 3 + 4 + 6 = 15.

Prim’s Algorithm and the Matrix Method #

One tree, grown outward, on paper or in a table.

Prim grows one tree outward, always taking the cheapest edge that reaches a new vertex

Start anywhere. Take A, and look only at the edges leaving the tree so far.

The cheapest edge leaving A is A to C, weight 2, so C joins the tree.

Now scan every edge leaving A or C. The cheapest is C to E, weight 3.

Of the edges leaving the tree now, A to B at 4 is cheapest, so B joins.

Then B to D at 6, and every town is in. It is the same tree Kruskal found, with the same total of 15.

The matrix method does the same work. Cross out column A, then scan row A.

The smallest entry in row A is 2, in column C. Circle it, and C joins the tree.

Cross out column C, scan rows A and C together, and the smallest left is 3.

The Chinese Postman Problem #

Repeat just enough to make the degrees even.

The shortest closed route over every edge repeats just enough of them to make all degrees even

A postman walks every street and comes home. The streets total 5 + 3 + 4 + 6 + 2 = 20.

B and C have odd degree, so no closed trail can use every street exactly once.

Some street must be walked twice, so find the cheapest route joining the two odd vertices.

B to C direct costs 4, and going around by D costs 6 + 2 = 8, so take the direct street.

Walk that street twice and every degree is even, so a closed trail now exists.

The shortest closed route is every street once, plus that repeat: 20 + 4 = 24.

The Traveling Salesman Problem #

The cheapest cycle through every town.

The traveling salesman problem asks for the cheapest cycle that visits every vertex once

Visit every town once and come home, as cheaply as possible.

Any answer is a Hamiltonian cycle. This one costs 5 + 6 + 4 + 7 = 22.

A different order costs 5 + 8 + 4 + 9 = 26, so the problem is choosing the order of the towns.

Four towns give only 3 cycles, but ten towns give over 180 thousand, so listing them fails.

A real network has missing roads: there is no road at all from A to C here.

Replace each pair by its shortest route: A to C becomes 11, going around through B.

The Nearest-Neighbor Upper Bound #

A tour you can walk is a ceiling on the best.

Always moving to the nearest unvisited vertex gives a tour, whose length is an upper bound

Start at A and always move to the nearest town not yet visited.

From A the nearest is B, at 3.

From B the nearest town not yet visited is C, at 4.

From C the nearest town not yet visited is D, at 2.

Only E is left, so the tour has to take it, at a cost of 10.

Home to A costs 9, so the tour is 3 + 4 + 2 + 10 + 9 = 28.

Another tour costs only 22, so 28 is an upper bound and not the cheapest tour.

The Deleted-Vertex Lower Bound #

Take one town out, span the rest, put it back.

Deleting a vertex, spanning the rest, and adding back its two cheapest edges gives a lower bound

Delete one town, say A, together with every road that touches it.

What is left is a smaller network on B, C, D and E.

Its minimum spanning tree is C-D at 2, B-C at 4 and B-E at 5: total 11.

Put A back with its two cheapest roads only: 3 and 6.

Together that is 11 + 3 + 6 = 20.

Every tour uses two roads at A, and its other roads join B, C, D and E, which costs at least 11, so no tour can cost under 20.

With the tour of 28 found before, the cheapest tour lies between 20 and 28.