☰
WH
·
CSBank
首頁
題庫專區
模擬考專區
Pro 方案
聯絡我們
首頁
題庫
模擬考
Pro
聯絡
總覽
資料結構
388
演算法
212
作業系統
290
計算機組織與結構
266
離散數學
161
線性代數
182
演算法
›
Ch4 圖論演算法
第 71 題／共 111 題
◀
AL 71/111
錯題回報
00:00
71. Minimum Spanning Tree、Cut Property
#AL-04-071
中
Minimum Spanning Tree
Cut Property
📝
☆
Minimum Spanning trees: Which of the following statements is (or are) correct?
A
(A) If an edge is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph. (Definition: An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.)
B
(B) If a graph has a unique minimum spanning tree then, for every cut of the graph, there is a unique light edge crossing the cut.
C
(C) If, for every cut of the graph, there is a unique light edge crossing the cut, then the graph has a unique minimum spanning tree
D
(D) Let e be a maximum-weight edge on some cycle of the graph
G
=
(
V
,
E
)
G=(V,E)
G
=
(
V
,
E
)
, then there is a minimum spanning tree of
G
′
=
(
V
,
E
−
{
e
}
)
G'=(V,E-\{e\})
G
′
=
(
V
,
E
−
{
e
})
that is also a minimum spanning tree of
G
=
(
V
,
E
)
G=(V,E)
G
=
(
V
,
E
)
.
E
(E) If an edge is a light edge crossing some cut of the graph, then it is contained in every minimum spanning tree.
📝 寫筆記
📄 交大111
重做
跳轉到第
題
← 上一題
下一題 →
答案／解析
▤
完整推導請見《WH 資工筆記 · 演算法》Ch4 圖論演算法
‹
本章題號 · 61–80 / 111
›
全部 111
易 42
中 62
難 7
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
