トポロジカルソート
もしトポロジカルソートされたノードのすべてのノードが隣接する次のノードへの辺を持つなら、元の有向非巡回グラフはハミルトン路を含む。もしハミルトン路が含まれるなら、トポロジカルソートの結果は一意、つまり2つ以上の解は存在しない。逆に、トポロジカルソートがハミルトン路を作らないなら、元の有向非巡回グラフは2つ以上のトポロジカルソート結果を持つ。その場合、ある結果のうち直接辺によってつながっていないノードを交換することで2番目のトポロジカルソート結果を得ることができる。従って、一意なトポロジカルソート結果が存在するかどうか、あるいはハミルトン路が存在するかどうかは多項式時間で決定することができる。これに対し、一般のグラフにおけるハミルトン路の問題はNP困難である。
↑ Jarnagin, M. P. (1960). Automatic machine methods of testing PERT networks for consistency. Technical Memorandum No. K-24/60. Dahlgren, Virginia: U. S. Naval Weapons Laboratory.
↑ Kahn, A. B. (1962). “Topological sorting of large networks”. Communications of the ACM 5 (11): 558–562. doi:10.1145/368996.369025.
↑ T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン『アルゴリズムイントロダクション』(第3版)近代科学社、2013年12月17日(原著2009-7-31)。