Talk:Topological sorting

Talk:Topological sorting

Relation to linear extension?

Latest comment: 8 years ago2 comments2 people in discussion

This article currently contains this sentence:

Topological orderings are also closely related to the concept of a linear extension of a partial order in mathematics.

Well, duhh, of course, that's obvious. The question is: how do topological orderings differ from linear extensions? Is there any difference at all? Perhaps topological sorting is defined only for finite sets/dags/orders, while linear extensions are more general, defined for infinite sets/dags/orders? Is there anything else, besides this finite/countable divide? 67.198.37.16 (talk) 17:25, 26 February 2018 (UTC)Reply

Topological orderings are derived from directed acyclic graphs. Linear extensions are derived from partially ordered sets. Those are two different kinds of objects, and are not even in a one-to-one relation with each other (many different DAGs might correspond to a single partial order). I don't think finiteness or generality comes into it. But also it's a disciplinary divide: if you talk to a computer scientist, they will probably know what topological sorting is but not what a linear extension is, and if you talk to a mathematician it's the opposite. —David Eppstein (talk) 17:37, 26 February 2018 (UTC)Reply

Relationship to topology?

Latest comment: 8 years ago2 comments2 people in discussion

The name "topological sorting" strongly suggests a connection with the mathematical subject of topology; yet such a connection is neither acknowledged nor disclaimed anywhere in the article. (Nor, for that matter, is it addressed in the topology article.) I would appreciate it if somebody who understands the origin of the term "topological sorting" (in particular, whether it has anything to do with topology) could shed some light on this, preferably in the text of the article. — Preceding unsigned comment added by 198.0.200.174 (talk • contribs)

See http://cstheory.stackexchange.com/questions/30659/why-is-topological-sorting-topological — the likely origin is in the meaning of "topology" that refers to the connectivity structure of a network, not to topology as a branch of mathematics. But without a reliable source we can't add anything to the article, and cstheory.stackexchange.com is not a reliable source. —David Eppstein (talk) 02:40, 20 March 2015 (UTC)Reply
"Graph topology" refers to the connectivity of a graph, just as geometric topology refers to the connectivity of manifolds and solids. A topological sort takes a partial ordering and generates a total ordering such that all the arrows still point in one direction, so in a sense it is a total ordering embedding that preserves the (ordered) topology of the graph. — Preceding unsigned comment added by 66.60.126.246 (talk) 02:27, 15 June 2018 (UTC)Reply

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.