題組內容

二、給定一個權重圖(weighted graph),G =(V, E, w),假設 V = {1, 2,...,n}, 且每個邊(edge)e 的權重 w(e)都是正整數。令 l(v)為以 v 為端點的所有 邊中權重最小的邊。將這些邊集合起來稱作 L,也就是 5c19e6e44dc4d.jpg(每小題 5 分,共 20 分)

⑵G[L]是否一定是 G 的擴張樹(spanning tree)?若是請證明之,若不 一定是請給一個反例。

詳解 (共 2 筆)

33
33
詳解 #4790637
2021/06/10
G[L]不一定會是G的擴張樹,如下圖 :...


(共 126 字,隱藏中)
前往觀看
111年警特高普中鋼調查皆上榜
111年警特高普中鋼調查皆上榜
詳解 #5376308
2022/03/12
不一定是,G[L]一定是沒有迴圈,但不代...

(共 35 字,隱藏中)
前往觀看