Dlaczego topologiczne „sortowanie topologiczne”?


28

Dlaczego „sortowanie topologiczne” nazywa się „topologicznym”? Czy tylko dlatego, że określa kolejność bez zmiany wierzchołków lub krawędzi - jak pączek i filiżanka kawy są topologicznie równoważne? Dlaczego nie nazywa się to „sortowaniem zależności” lub czymś innym? Dlaczego „topologiczny”? Przyznaję, że jestem zdziwiony.

Odpowiedzi:


13

Najwcześniejsze odniesienie, jakie mogłem znaleźć dla sortowania topologicznego, pochodzi z [Lasser61]:

Zakłada się sieć kierowanych odcinków linii wolnych od okrągłych elementów. Linie są identyfikowane przez ich węzły końcowe i zakłada się, że węzły są ponumerowane przez system nie-topologiczny. Biorąc pod uwagę listę tych linii w kolejności numerycznej, można zastosować prostą technikę, aby utworzyć z dużą prędkością listę w kolejności topologicznej.

Nie mam teraz dostępu do tego artykułu, ale chciałbym się założyć, że „topologia” w „rodzaju topologicznym” nie pochodzi z matematycznego pojęcia topologii (np. Zestawy otwarte, zwartość itp.), Ale raczej z W „ topologia sieci ” sens.

[Lasser61] Lasser, Daniel J. „ Topologiczne uporządkowanie listy losowo numerowanych elementów sieci. ” Komunikacja ACM 4, nr. 4 (1961): 167-168.


Mam do tego dostęp. Przeczytam to i rozważę tę i inne odpowiedzi. Dzięki.
PartialOrder

9
Inną wskazówką, że topologia sieci zamiast matematycznego znaczenia topologii jest zamierzona, jest to, że termin używany w czystej matematyce dla prawie tego samego pomysłu (być może po raz pierwszy użyty przez Dushnika i Millera 1941) jest „rozszerzeniem liniowym”, a nie „porządkiem topologicznym”.
David Eppstein,

@mhum Wygląda na to, że termin ten wywodził się z Jarnagin (1960). Automatyczne maszynowe metody testowania sieci PERT pod kątem spójności (uwaga: „sieci PERT”). Wydaje się, że nie ma zbyt wielu kopii tego krążącego, ale zamierzam poprosić o pożyczkę międzybiblioteczną i zobaczyć, co mówi.
PartialOrder

-2

Topologia zestawu elementów polega na sposobie ich łączenia. Sortowanie topologiczne polega na sortowaniu elementów wyłącznie na podstawie ich topologii.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.