Wikipedista:Kolarp/Topological sorting

Topologické třídění nebo topologické řazení (anglicky topological sort, resp. topological ordering) orientovaného grafu je lineární uspořádání jeho vrcholů tak, aby vrchol u byl v řazení před v, pokud graf obsahuje orientovanou hranu uv z vrcholu u do vrcholu v

Topologické třídění má mnoho praktických aplikací. Vrcholy grafu mohou reprezentovat například úlohy, které mají být provedeny a jeho hrany mohou reprezentovat omezení, že určitý úkol musí být proveden před jiným úkolem nebo úkoly; v toto aplikace, topologické řazení je pouze povolený posloupnost pro úlohy. Topologické řazení je možné právě tehdy, když graf neobsahuje orientovaný cyklus, tj., jestliže se jedná o acyklický orientovaný graf. Lze dokázat, že pro každý acyklický orientovaný graf existuje alespoň jedno jeho topologické setřídění, a jsou známé algoritmy pro zkonstruování topologického řazení jakékoli acyklického orientovaného grafu v lineárním čase.