|
Topološka sortiranja su usko povezana sa konceptom [[Linear extension|lineanog istezanja]] [[Partial order#Formal definition|relacije poretka]] u matematici.
Parcijalno uredjen skup je skup objekata sa definicijom relacije manje ili jednako "≤", zadovoljavajući aksiome refleksivnosti(''x'' ≤ ''x''), antisimetričnosti(ako je ''x'' ≤ ''y'' i ''y'' ≤''x'' onda je ''x'' = ''y''), i [[Transitive relation|tranzitivnosti]] (ako je ''x'' ≤ ''y'' i ''y'' ≤ ''z'', onda je ''x'' ≤ ''z'').[[Total order|Relacija totalnog poretka]] je relacija poretka u kojoj su svaka dva objekta ''x'' i ''y'' iz skupa uporedivi, ili je ''x'' ≤ ''y'' ili je ''y'' ≤ ''x''.Totalna uređenja se koriste u informatici kako bi operatori poređenja mogli da izedu upoređivanje kod [[Сортирање поређењем|algoritama za sortiranje]].Za konačne skupove, totalna uređenja se mogu identifikovati kao linearan niz objekata gde je "≤" relacija tačna kad god prvi objekat prethodi drugom u redu;algoritmi za sortiranje upoređivanjem se mogu iskoristiti za pretvaranje totalnog uređenja u niz na ovaj način. Linearno istezanje relacije poretka je totalni poredak koji je usaglašen sa njim, u smislu ako je ''x'' ≤ ''y'' u relaciji poretka onda je i ''x'' ≤ ''y'' u totalnom poretku takođe.
Može se definisati relacija poretka iz bilo kog DAL-a tako što ćemo postaviti da skup objekata budu čvorovi DAL-a i definišemo da je ''x'' ≤ ''y'' tačno za bilo koja dva čvora ''x'' i ''y', kad god postoji [[Directed path|usmeren put]] od ''x'' ka ''y'',tj. kad god iz ''x'' [[Reachability|možemo da stignemo do]] ''y''. Ovako definisano, topološko uređenje DAL-a je isto što i linearno istezanje ove relacije poretka. Obrnuto, svaka relacija poretka može biti definisana kao relacija domašaja u DAL-u. Jedan način da se ovo izvede je da se definiše DAL koje ima čvor za svaki objekat iz skupa relacije poretka i granu ''xy'' za svaki par objekata za koje važi ''x'' ≤ ''y''. Alternativan način da se uradi ovo je da se koristi [[Tranzitivni završeci|tranzitivno zatvorenje]] relacije poretka;u celini, ovako dobijamo DAL-ove sa manje grana ali je relacija domašaja i dalje ista relacija poretka. Ovako se algoritmi za topološko sortiranje mogu koristiti za nalaženje linearnih istezanja relacije poretka.
== Vidi još ==
== Literatura ==
{{refbegin|2}}
* {{Cite book |ref= harv|last=Cook | first = Stephen A. | authorlink = Stephen Cook| title = A Taxonomy of Problems with Fast Parallel Algorithms | journal = Information and Control | volume = 64 | issue = 1–3|year=1985 | pages=2-22 | doi = 10.1016/S0019-9958(85)80041-3|pages=2-22}}.
* {{Cite book |ref= harv|last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen| last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson | last3 = Rivest | first3 = Ronald L. | author3-link = Ronald L. Rivest| last4 = Stein | first4 = Clifford | author4-link = Clifford Stein | contribution = Section 22.4: Topological sort| edition = 2nd |id=ISBN 0-262-03293-7| pages=549-552 | publisher = MIT Press and McGraw-Hill| title = [[Introduction to Algorithms]] |year=2001|pages=549-552}}.
* {{Cite book |ref= harv|last=Jarnagin | first = M. P.| title = Automatic machine methods of testing PERT networks for consistency |year=1960| series = Technical Memorandum No. K-24/60 | publisher = U. S. Naval Weapons Laboratory| location = Dahlgren, Virginia}}.
* {{Cite book |ref= harv|last=Kahn | first = Arthur B.| title = Topological sorting of large networks | journal = Communications of the ACM| volume = 5 | issue = 11 |year=1962 | pages=558-562 | doi = 10.1145/368996.369025|pages=558-562}}.
* {{Cite book |ref= harv|last=Tarjan | first = Robert E. | authorlink = Robert Tarjan| title = Edge-disjoint spanning trees and depth-first search | journal = Acta Informatica | volume = 6 | issue = 2 |year=1976 | pages=171-185| doi = 10.1007/BF00268499|pages=171-185}}.
* {{Cite book |ref= harv|last1 = Vernet | first1 = Oswaldo| last2 = Markenzon | first2 = Lilian | contribution = Hamiltonian problems for reducible flowgraphs| title = Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97) |year=1997| pages=264-267 | doi = 10.1109/SCCC.1997.637099|pages=264-267}}.
{{refend}}
| 