Mengapa "topological sorting" topologi?

28

Mengapa "penyortiran topologis" disebut "topologis"? Apakah hanya karena itu menentukan pesanan tanpa mengubah simpul atau tepi - seperti donat dan cangkir kopi secara topologi setara? Mengapa tidak disebut "semacam ketergantungan" atau yang lainnya? Mengapa "topologis"? Saya akui saya bingung.

graph-theory graph-algorithms directed-acyclic-graph topology Pesanan Sebagian
sumber

Jawaban:

13

Referensi paling awal yang bisa saya temukan untuk jenis topologi adalah dari [Lasser61]:

Sebuah jaringan segmen garis terarah bebas dari elemen lingkaran diasumsikan. Garis diidentifikasi oleh node terminal mereka dan node diasumsikan diberi nomor oleh sistem non-topologi. Diberikan daftar garis-garis ini dalam urutan numerik, teknik sederhana dapat digunakan untuk membuat daftar dengan kecepatan tinggi dalam urutan topologi.

Saya tidak memiliki akses ke artikel ini sekarang tetapi saya akan bertaruh bahwa "topologi" dalam "semacam topologi" tidak berasal dari gagasan matematika tentang topologi (misalnya: set terbuka, kekompakan, dll ...) melainkan dari arti " topologi jaringan ".

[Lasser61] Lasser, Daniel J. " Pemesanan topologi dari daftar elemen-elemen jaringan yang acak. " Komunikasi dari ACM 4, no. 4 (1961): 167-168.

mhum
sumber
Saya memiliki akses ke ini. Saya akan membacanya dan merenungkan ini dan jawaban lainnya. Terima kasih.
PartialOrder
9
Petunjuk lain bahwa topologi jaringan daripada makna matematis dari topologi yang dimaksudkan adalah bahwa istilah yang digunakan dalam matematika murni untuk ide yang hampir sama (mungkin pertama kali digunakan oleh Dushnik dan Miller 1941) adalah "ekstensi linear" daripada "urutan topologis".
David Eppstein
@mhum Sepertinya istilah ini mungkin berasal dari Jarnagin (1960) Metode mesin otomatis untuk menguji jaringan PERT untuk konsistensi (catatan: "jaringan PERT"). Sepertinya tidak ada banyak salinan ini beredar tetapi saya akan meminta satu melalui pinjaman antar-perpustakaan dan melihat apa yang dikatakannya.
PartialOrder
-2

Topologi dari serangkaian item adalah bagaimana mereka terhubung. Penyortiran topologi adalah penyortiran item hanya berdasarkan topologi mereka.

reinierpost
sumber