Topološko uređenje — разлика између измена

Kanonska aplikacija topološkog sortiranja(topološkog uređenja) je u [http://en.wikipedia.org/wiki/Job_shop_scheduling planiranju] rasporeda poslova ili zadata na osnovu njihove zavisnosti; algoritmi topološkog sortiranja su prvi put proučavani ranih 1960-ih godina u kontekstu [http://en.wikipedia.org/wiki/Program_Evaluation_and_Review_Technique PERT] tehnike planiranja [http://en.wikipedia.org/wiki/Project_management upravljanja projektima] (<ref>{{harvnb|Jarnagin|1960}}</ref>).Poslovi su predstavljeni čvorovima i postoji grana od ''A'' ka ''B'' ako posao ''A'' mora biti izvršen pre nego što se posao ''B'' može zapoceti(primer: kod pranja veš mašine, mašina mora da završi sa pranjem veša da bi ga mi satvili na sušenje).Dakle, topološko sortiranje nam daje redosled kojim treba da izvršavamo poslove.

* [http://en.wikipedia.org/wiki/Computational_complexity Računarska kompleksnost] izračunavanja topološkog uređenja u usmerenom grafu je [http://en.wikipedia.org/wiki/NC_(complexity) '''NC''']²; što znači da se može izračunati za ''O''(log² ''n'') vremena na [http://en.wikipedia.org/wiki/Parallel_computer paralelnom računaru] pomoću polinomijalnog broja od ''O''(''n^k'')procesora, za istu konstantu ''k''<ref>{{harvnb|Cook|1985}}</ref>.

Kada bi topološko sortiranje imalo osobinu da sve parove uzastopnih čvorova u sortiranom poretku poveže granama, dobili bismo usmeren [http://en.wikipedia.org/wiki/Hamiltonian_path Hamiltonov put] u [http://en.wikipedia.org/wiki/Directed_acyclic_graph UAG].Ako Hamiltonov put postoji, topološki poredak je jedinstven;nijedan drugi poredak ne zadovoljava ivice puta.Obrnuto, ako topološko sortiranje ne formira Hamiltonov put, UAG će imati dva ili više validna topološka poretka, jer je u ovom slučaju uvek moguće formirati drugi ispravan poredak zamenom dva uzastopna čvora koji nisu povezani granom.Dakle, moguće je proveriti u linearnom vremenu da li postoji jedinstveni poredak, i da li postoji Hamiltonov put, uprkos [http://en.wikipedia.org/wiki/NP-hard NP-težini] problema Hamiltonovog puta za neke opštije usmerene grafove<ref>{{harvnb|Vernet|Markenzon|1997}}</ref>.