作者lovefo (lovefo)
看板Grad-ProbAsk
标题[理工] [资结]-97成大资结
时间Fri Jan 29 22:39:11 2010
最後一题
How many strongly connected components in a path with n-vertices
老实说 我还搞不太懂
strongly connected components是什麽意思?
我看定义很像是 complete graph
有没有大大可以帮忙解答 XD
--
一切....
似乎都不再那麽重要....
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.46.163.237
1F：推 trovadores:Strongly connected 的定义是有向图中任两点均有path 01/30 00:08
2F：→ trovadores:使得x可以到y and y可以到x 01/30 00:10
3F：→ trovadores:SCC为图中的最大强连通子图(如果G'<V',E'>是G中的SCC 01/30 00:14
4F：→ trovadores:在G'中加任何一点均使得G'不再为强连通 01/30 00:16
5F：→ trovadores:则G'为G中的最大强连通子图) 01/30 00:17