19在一 n 個節點的連通無向圖（Connected Undirected Graph）中，找出一展開樹（Spanning Tree），則此展開樹中有幾個邊（edge）？ (A) n-1(B)n(C)

問題詳情

19在一 n 個節點的連通無向圖（Connected Undirected Graph）中，找出一展開樹（Spanning Tree），則此展開樹中有幾個邊（edge）？
(A) n-1
(B)n
(C) n 或 n+1
(D) n-1 或 n

參考答案

答案：A
難度：簡單0.633
書單：沒有書單，新增

用户評論

【柯韋安】評論

在圖論中，無向圖 G 的展開樹（英語：Spanning Tree）是具有 G 的全部頂點，但邊數最少的連通子圖。因為不管展開樹有幾個節點，皆只需要用比節點數少一的邊數，就能把所有節點連結起來，因此展開樹中邊的數量為 n - 1。故答案為(A)。