Let G=(V,E) be a directed graph. Answer the following questions with respect to the Strongly Connected Components(SCCs) of G.
1.What is an upper bound on the number of SCCs of G in the terms of n?
2.Suppose that an edge e=(u,v) is added to G. What is an upper bound on the change in the number of SCCs of G?
3.Suppose now that an edge e=(u,v) in G is deleted from G. What is an upper bound on the change in the number of SCCs of G?
4. Find a directed gragh G'' that has the same SCCs as that of G but G'' has the least possible number of edges. In other words, the SCCs of G and G'' have the same set of vertices. You may describe the structure of G'' to start with Design an algorithm to output such a G'' and also mention the run time of your algorithm. Is G'' always a subgraph of G''?
uj5u.com熱心網友回復：
哪位大神可以幫忙解答，在線等。轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/66719.html
標籤：數據結構與算法
上一篇：在 Flutter 中使用 TensorFlow Lite 插件實作文字分類
下一篇：推薦系統（一）