This may be a dumb question, but what's "topological" about topological sorting in graph theory?

I thought topology was related to geometry and deformations.

  • 2
    Introducing a complete order on a set endows it with order topology... – Sasha Feb 25 '12 at 17:46
  • @Sasha Is the order topology not only defined for total orders? And according to this math SE post there is no canonical induced topolgy for partial orders? – bianchira Dec 1 '14 at 0:21
up vote 12 down vote accepted

Graph theory was originally (and still sometimes is, depending on who you ask) considered a branch of topology.

This may sound strange to people with a modern education, where "topology" means more or less "the part of mathematics that deals abstractly with continuity and limits, without using real numbers" -- or at least without giving the real numbers any central position in the theory. However, earlier on, "topology" appears to have been a catch-all term for "the part of mathematics that isn't about numbers or geometric magnitudes". (This was before algebraists stopped pretending that algebra is necessarily about numbers). Only later did a distinction between what we now call topology and discrete mathematics become common.

In this old usage, "topological sorting" simply means "the kind of sorting you can define without reference to comparison of numbers".

The use of "topological" in "topological sorting" and "topological order" appears to stem from the use of the word "topology" to describe the structure of networks in computer science literature. Indeed, if you look at the early papers on topological sorting (Lassser, CACM, 1961; Kahn, CACM, 1962) you will see they are motivated by topological sorting of PERT charts (project management). A quick google books search shows even earlier analogous uses of "topology" in computer science, e.g. to describe the structure of electrical circuit networks.

Most likely the terminology became widely known after it was employed in Knuth's influential book The art of Computer Programming, vol. 1, 1967. Of course the phrase "network topology" is still in wide use today.

More general mathematical results go back to at least to 1930, see the Szpilrajn extension theorem.

I can only guess, but knowing that topos means place in Greek, I imagine it is because we are sorting elements based on their place in a partial order, rather than on magnitude. If I am right, there is no connection at all with topology in the mathematical sense.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.