3 Fairy Tales from Topology & Graph Theory

Click images for larger.

You might want to print the Konigsberg diagram and the uncolored map to play around with them.

Top image:

* an envelope from the mathematics department of the University of Illinois, whose postage meter announced:

FOUR COLORS
SUFFICE

* The zrëêéèũūŬŭůűs of the continent of Euforia, on Planet Hoon

* the states of Germany/Deutschland, awaiting proper coloring

==================

I had this book with me: "Introductory Graph Theory" by Gary Chartrand (Dover).

The doctor always likes to chat with me. He asked me about the book, and I tried to quickly give him the basics (to the pathetic extent that I grok them) of topology and graph theory.

He seemed pretty interested and said all this was new to him. So I cooked this up and sent it to him.

=========

These are three classic, very famous problems of Topology and Graph Theory.

The 7 Bridges of Königsberg

Königsberg was a prosperous city on the southern Baltic in East Prussia. The river Pregel runs through the city, with a central island called Kniephof. Seven bridges connected Kniephof with the opposite banks of the Pregel.

(Today it's an exclave of Russia -- a political zone of Russia, but seperated (by Lithuania, Latvia and Poland) from greater Russia. When the Soviet Army took it from Germany in 1945, they changed its name to Kaliningrad. Several bridges haven't survived World War II, and changes made during the Soviet era.)

In the 17th and 18th century, Königsbergers enjoyed strolling over the bridges, and a local puzzle arose:

Starting anywhere, was it possible to cross all 7 bridges, each only once, and return to your starting point?

No one could find such a path.

But no one could prove that no such path existed.

Eventually some students wrote Europe's leading mathematician, Leonhard Euler, who solved the problem in 1736.

In doing so, he founded the branch he called Analysis Situs -- Analysis of Place -- today called Topology. The solution also founded a rich tool called Graph Theory.

Like all the great problems, the Königsberg Bridges asks a strikingly simple question -- a child can grasp it. (The answer's not so simple.)

Print the image and stroll the bridges with a pencil to get a feel for the problem. Although the problem seems entirely mathematical in nature, you'll see that Numbers -- quantitative measurements of distances, for example -- are of little or no use as a tool to solve the problem.

The 4-Color Problem / 4-Color Conjecture (4CC)

Consider any geopolitical map printed with different colors so that no two neighboring zones which share a border are colored the same.

The counties of England and Scotland were cited as an example when the problem was first posed in 1862 (by Guthrie). Other examples might be the countries of Eurasia, the countries of Africa, the Lower 48 states of the USA.

Printers had learned from experience that 4 colors were all they ever needed to color all the maps they'd encountered.

But could a map exist that required more than 4 colors? No one could imagine or draw such a map, no matter how strangely or eccentrically the zones and borders were drawn.

But no one could prove that 4 colors would always be enough.

A map can be very large and have dozens, hundreds, thousands or millions of zones. (But it can't have an infinite number of zones.)

In 1976 two mathematicians at the University of Illinois Champaign/Urbana solved the problem.

Their solution is universally accepted and acknowledged -- but is also troublingly controversial.

Haken and Appel saw that the problem could be broken down into several million unique cases, and used the U-I supercomputer to analyze each case. Begging and stealing time on the supercomputer, it required more than a year of compute time.

They used a standard, ancient method of proof: Break the problem into all possible cases, and analyze every case.

But it was the first proof in mathematics to rely entirely on a computer. There were so many cases that no single human mind could analyze all the millions of cases.

And once done, no single human mind could go through the entire proof case by case and verify it. It required another computer to verify the result from the first computer.

So the 4-Color Problem is the first mathematical proof that an unaided human can't solve, verify or comprehend. Anyone can understand and analyze a few individual cases. But no one can possibly go through the whole proof without a computer.

But it's still a proof, accepted just as the proof of the Pythagorean Theorem (which one person can easily go through step by step) has been accepted for 2400 years.

But some critics argue that it's a uniquely new and troubling advance in mathematics -- removing mathematical truth from the human mind, and transfering it to a new realm that resides exclusively within computers. We must trust what the computers tell us.

You can print the uncolored map and experiment with colored pens. Can it be colored with 3 colors? 4? Or does it absolutely require 5 or more colors?

The solution relies on advances in Graph Theory made since Euler's day.

Arguably the problem has little significance by itself; but efforts to solve it for 114 years added great power and sophistication to Graph Theory, advances which are used to solve many highly practical problems.

the Traveling Salesman Problem (TSP)

A salesman at headquarters HQ must visit 5 cities A B C D E, each city only once, then return to HQ.

There's a specific cost to travel between any pair of cities. (But the cost is the same in either direction.)

What is the cheapest possible path?

Any path

[HQ] C A D B E [HQ]

costs the same as its mirror-image path

[HQ] E B D A C [HQ]

(A simpler scheme just measures the straight-line air distance between each pair of cities, and the salesman must find the shortest possible path.)

Again, note how simple the question is.

Again, the answer is not so simple.

With 2, 3, 4 or 5 cities, the cheapest (or shortest) path can be found with pencil, paper and calculator.

But as the number of cities gets larger, the number of possible paths grows dramatically, and the problem must be cranked out on a computer.

Eventually -- a tour of 20 or more cities -- there are so many possible paths that even a supercomputer would take weeks, months, years to find the minimum path.

The explosive growth of possible paths makes TSP a kind of problem known as NP-Hard (for Non-Polynomial).

TSP obviously has practical real-world value, and many other NP-Hard problems also have important practical applications.

Finding a computational shortcut to problems like TSP is one of the most important unsolved problems in mathematics and computer science research.

Though no significant shortcuts have yet been discovered, it's been proved that any shortcut to TSP would also apply to all NP-Hard problems.

If you're willing to settle for a Very Good Path (rather than the unique best path), there are techniques that will find a very good path in a short time, regardless of how many cities must be visited.

But the classic TSP requires finding the unique best path (or its mirror-image path).

........possible
cities.....paths
================
.2.............2
.3.............6
.4............24
.5...........120
.6...........720
.7.........5,040
.8........40,320
.9.......362,880
10.....3,628,800
...etc.

[Generally:

p = c!

although in TSP, the real number of possible paths is

p = c! / 2

because each path is equal (in cost or distance) to its mirror-image opposite-direction path, so only one of them has to be computed and compared to the other paths.]

I'm working on a 13-city TSP. I estimate that it may take my computer the better part of a month to find the best path.

What I'll probably do is carve the problem into several shorter blocks and let others run them on their computers, then e-mail the results of each block back to me.

This approach is called Distributed Computing and has become an extremely powerful and important New Thing in computing during the last decade.