Timeline for How to mathematically prove that a topological ordering on a cyclic graph will topologically sort its Strongly Connected Components?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2021 at 18:04 | history | undeleted | AlessandroF | ||
| Dec 20, 2021 at 15:42 | history | deleted | AlessandroF | via Vote | |
| Dec 19, 2021 at 14:48 | comment | added | nir shahar | I don't think this will produce a topological ordering of the SCCs, since jothing is preventing the DFS from first leaving the current SCC and going to the next one - and afterwards to continue work on the current SCC. Also the example stack configuration you wrote cannot be achieved - one cannot have 4 immediately after 3 in the stack since they are not connected together in a direct edge. | |
| Dec 19, 2021 at 8:22 | comment | added | D.W.♦ | You say "How to prove this mathematically?" - what do you want to prove? What does "this" refer to? Please provide in the question a precise mathematical statement that you are looking to prove. Then, show us what progress you've made on trying to prove it yourself. What textbooks have you consulted? I suspect what you're asking for is a standard fact that is already proven in good textbooks. | |
| Dec 19, 2021 at 0:44 | history | asked | AlessandroF | CC BY-SA 4.0 |