Pourquoi le «tri topologique» est-il topologique?

28

Pourquoi le "tri topologique" est-il appelé "topologique"? Est-ce simplement parce qu'il détermine une commande sans altérer les sommets ou les bords - comme un beignet et une tasse de café sont topologiquement équivalents? Pourquoi n'est-il pas appelé "tri par dépendance" ou autre chose? Pourquoi "topologique"? J'avoue que je suis mystifié.

graph-theory graph-algorithms directed-acyclic-graph topology Ordre partiel
la source

Réponses:

13

La première référence que j'ai pu trouver pour le tri topologique est de [Lasser61]:

On suppose un réseau de segments de ligne dirigés exempts d'éléments circulaires. Les lignes sont identifiées par leurs nœuds terminaux et les nœuds sont supposés numérotés par un système non topologique. Étant donné une liste de ces lignes par ordre numérique, une technique simple peut être utilisée pour créer à grande vitesse une liste par ordre topologique.

Je n'ai pas accès à cet article pour le moment mais je parierais que la "topologie" en "tri topologique" ne vient pas de la notion mathématique de topologie (ex: ensembles ouverts, compacité, etc ...) mais plutôt de le sens de " topologie de réseau ".

[Lasser61] Lasser, Daniel J. "Ordre topologique d'une liste d'éléments numérotés de façon aléatoire d'un réseau. " Communications de l'ACM 4, no. 4 (1961): 167-168.

mhum
la source
J'y ai accès. Je vais lui donner une lecture et réfléchir à cela et à d'autres réponses. Merci.
PartialOrder
9
Une autre indication que la topologie de réseau plutôt que la signification mathématique de la topologie est voulue est que le terme utilisé en mathématiques pures pour presque la même idée (peut-être utilisé pour la première fois par Dushnik et Miller 1941) est "extension linéaire" plutôt que "ordre topologique".
David Eppstein
@mhum Il semble que le terme puisse provenir de Jarnagin (1960) Méthodes automatiques de machine pour tester la cohérence des réseaux PERT (note: "Réseaux PERT"). Il ne semble pas y avoir beaucoup d'exemplaires de ce document, mais je vais en demander un via un prêt entre bibliothèques et voir ce qu'il dit.
PartialOrder
-2

La topologie d'un ensemble d'éléments est de savoir comment ils sont connectés. Le tri topologique consiste à trier les éléments uniquement en fonction de leur topologie.

reinierpost
la source