Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Introducing a complete order on a set endows it with order topology... –  Sasha Feb 25 '12 at 17:46
add comment

3 Answers 3

up vote 11 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".

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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