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:
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.
Topologia zestawu elementów polega na sposobie ich łączenia. Sortowanie topologiczne polega na sortowaniu elementów wyłącznie na podstawie ich topologii.