what does a topological ordering have to do with a topology?

62 Views Asked by At

I just read about topological orderings:

"A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering."

Why is this called a "Topological" ordering? What does it have to do with a topology on a set? It is not obvious to me.

1

There are 1 best solutions below

0
On

My intuition for this has always been the following: "Topology" means something more general than the word as it is used for topological spaces. When talking about a graph, its topological properties refer to something like the 'shape' of the graph, in vague terms. You might have come across this as the phrase "network topology". (Note that a lot of the shape of a graph can actually be interpreted topologically: every graph can be turned into a CW-complex with zero-cells for nodes and 1-cells for edges -- but directedness is not something that carries over directly.)

This is (arguably non-conclusively) backed up by this answer to the same question on tcs.se.