Warum ist topologische Sortierung topologisch?

28

Warum heißt "topologische Sortierung" "topologisch"? Liegt es nur daran, dass eine Reihenfolge bestimmt wird, ohne dass Scheitelpunkte oder Kanten verändert werden - so wie ein Donut und eine Kaffeetasse topologisch gleichwertig sind? Warum heißt es nicht "Abhängigkeitssortierung" oder etwas anderes? Warum "topologisch"? Ich gebe zu, dass ich verwirrt bin.

graph-theory graph-algorithms directed-acyclic-graph topology Teilbestellung
quelle

Antworten:

13

Der früheste Hinweis, den ich für die topologische Sortierung finden konnte, stammt von [Lasser61]:

Es wird ein Netz gerichteter Liniensegmente ohne kreisförmige Elemente angenommen. Die Linien werden durch ihre Endknoten identifiziert, und es wird angenommen, dass die Knoten durch ein nicht-topologisches System nummeriert sind. Wenn eine Liste dieser Zeilen in numerischer Reihenfolge angegeben wird, kann mit einer einfachen Technik mit hoher Geschwindigkeit eine Liste in topologischer Reihenfolge erstellt werden.

Ich habe momentan keinen Zugang zu diesem Artikel, aber ich würde wetten, dass die "Topologie" in "topologischer Sortierung" nicht aus dem mathematischen Begriff der Topologie stammt (z. B. offene Mengen, Kompaktheit usw.), sondern aus der Sinn " Netzwerktopologie ".

[Lasser61] Lasser, Daniel J. " Topologische Anordnung einer Liste von zufällig nummerierten Elementen eines Netzwerks. " Mitteilungen der ACM 4, Nr. 4 (1961): 167 & ndash; 168.

mhum
quelle
Ich habe Zugriff darauf. Ich werde es lesen und über diese und andere Antworten nachdenken. Vielen Dank.
Teilbestellung
9
Ein weiterer Hinweis darauf, dass Netzwerktopologie und nicht die mathematische Bedeutung von Topologie gemeint ist, ist, dass der Begriff, der in der reinen Mathematik für fast dieselbe Idee verwendet wird (möglicherweise zuerst von Dushnik und Miller 1941 verwendet), "lineare Ausdehnung" und nicht "topologische Ordnung" ist.
David Eppstein
@mhum Es sieht so aus, als ob der Begriff möglicherweise von Jarnagin (1960) stammt. Automatische Maschinenmethoden zum Testen von PERT-Netzwerken auf Konsistenz (Anmerkung: "PERT-Netzwerke"). Es scheint nicht viele Exemplare davon zu geben, aber ich werde eine per Fernleihe anfordern und sehen, was darin steht.
Teilbestellung
-2

Die Topologie einer Reihe von Elementen ist, wie sie verbunden sind. Beim topologischen Sortieren werden Elemente nur nach ihrer Topologie sortiert.

reinierpost
quelle