Почему «топологическая сортировка» топологическая?

28

Почему «топологическая сортировка» называется «топологической»? Только потому, что он определяет порядок без изменения каких-либо вершин или ребер - как пончик и кофейная чашка топологически эквивалентны? Почему это не называется "сортировка по зависимости" или что-то еще? Почему "топологический"? Я признаю, что я озадачен.

graph-theory graph-algorithms directed-acyclic-graph topology PartialOrder
источник

Ответы:

13

Самое раннее упоминание о топологической сортировке, которое я смог найти, было [Lasser61]:

Предполагается сеть направленных отрезков, свободных от круговых элементов. Линии идентифицируются их конечными узлами, и предполагается, что узлы пронумерованы нетопологической системой. Учитывая список этих строк в числовом порядке, можно использовать простую технику для создания с высокой скоростью списка в топологическом порядке.

У меня нет доступа к этой статье прямо сейчас, но я бы поспорил, что «топология» в «топологической сортировке» не исходит из математического понятия топологии (например: открытые множества, компактность и т. Д.), А скорее из смысл " топологии сети ".

[Lasser61] Лассер, Даниэль Дж. " Топологическое упорядочение списка случайно пронумерованных элементов сети". Сообщения ACM 4, нет. 4 (1961): 167-168.

mhum
источник
У меня есть доступ к этому. Я прочитаю и обдумаю этот и другие ответы. Спасибо.
PartialOrder
9
Еще один намек на то, что топология сети, а не математический смысл топологии, заключается в том, что термин, используемый в чистой математике для почти той же идеи (возможно, впервые использованной Душником и Миллером 1941), является «линейным расширением», а не «топологическим порядком».
Дэвид Эппштейн
@mhum Похоже, что термин, возможно, возник из Jarnagin (1960) Автоматические методы тестирования сетей PERT на согласованность (примечание: «Сети PERT»). Похоже, копий этого не так много, но я собираюсь запросить их через межбиблиотечный абонемент и посмотреть, что там написано.
PartialOrder
-2

Топология набора элементов - это то, как они связаны. Топологическая сортировка - это сортировка элементов, основанная только на их топологии.

reinierpost
источник