作者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
推 trovadores:Strongly connected 的定義是有向圖中任兩點均有path 01/30 00:08
→ trovadores:使得x可以到y and y可以到x 01/30 00:10
→ trovadores:SCC為圖中的最大強連通子圖(如果G'<V',E'>是G中的SCC 01/30 00:14
→ trovadores:在G'中加任何一點均使得G'不再為強連通 01/30 00:16
→ trovadores:則G'為G中的最大強連通子圖) 01/30 00:17