Content deleted Content added
→Incorrect claim in algo description: new section |
|||
Line 21:
That actually gives a ''better'' description of the algorithm than the text currently in the article.[[Special:Contributions/130.243.83.63|130.243.83.63]] ([[User talk:130.243.83.63|talk]]) 15:58, 26 November 2015 (UTC)
== Incorrect claim in algo description ==
The article states: "so if there is a forward path from ''u'' to ''v'' then ''u'' will appear before ''v'' on the final list ''L'' (unless ''u'' and ''v'' both belong to the same strong component, in which case their relative order in ''L'' is arbitrary)."
This is not true. There is a weaker claim which is both true and sufficient to justify the algorithm correctness: If there is a path from ''u'' to ''v'' and ''u'' and ''v'' belong to different strongly connected components then there is some vertex from ''u''{{'}}s strongly connected component that appears on the final list L before all vertices in ''v''{{'}}s strongly connected component. Importantly, not all vertices from ''u''{{'}}s SCC need to appear on L before all vertices from ''v''{{'}}s SCC, which is implied by the original claim.
[[User:Pilloff|Pilloff]] ([[User talk:Pilloff|talk]]) 19:13, 21 April 2022 (UTC)
| |||