試題詳解

34. 下列有關圖形(graph)的敘述，何者錯誤？
(A)任何圖形的最小成本擴張樹(minimum cost spanning tree)只有一個
(B)擴張樹(spanning tree)的邊數(edge number)一定比其頂點數 (vertex number)少 1
(C)在 n 個頂點(vertices)、m 條邊(edges)的圖形上，計算某一頂點到另一頂點的最短路徑(shortest path)可在 O(m)時 間內完成
(D)n 個頂點的完全無向圖(complete undirected graph)有 n(n−1)/2 條邊。 − 共 3 頁，第 3 頁 −