計概17.圖形理論

【選擇題】 【 B 】 01. 下圖表示一個具有權重 (weight) 的無向圖 (undirected graph) 。假設我們針對該圖求取最小生成樹 (minimum spanning tree) ，則該樹的權重總和為下列何者？ (A)1 (B)6 (C)8 (D)10 。 [109 鐵路員級 ] 1 + 2 + 3 = 6   【 B 】 02. 關於無向圖 (Undirected graph) 頂點的分支度 (Degree) ，下列敘述何者正確？ (A) 具有奇數分支度的頂點個數是奇數 (B) 所有頂點的分支度的總和是偶數 (C) 具有偶數分支度的頂點個數是奇數 (D) 偶數分支度的頂點個數多於奇數分支度的頂點個數。 [110 地方四等電子 ] (A)(D) 線段不是。 (C) 正方形不是。   【 B 】 03. 若一個無向圖 (Undirected Graph)G 由 n 個點 (Vertices) 與 m 條邊 (Edges) 所組成，且 G 為一個樹 (Tree) ，則有關點與邊的敘述，下列何者正確？ (A)m = n - 2 (B)m = n - 1 (C)m = n (D)m = n + 1 。 [110 身心四等 ] 生成樹 (Spanning Tree) 的邊為節點數 - 1   【 C 】 04. 一個具有 6 個頂點 (Vertices) 的無向完整圖形 (Undirected Complete Graph) ，應有多少個邊 (Edges) ？ (A)36 (B)18 (C)15 (D)6 。 [110 普考電子 ] 無向圖具有 n 個頂點，應有邊數 =n*(n-1)/2=6*(6-1)/2=15   【 C 】 05. 樹 (Tree) 的定義為一個不包含簡單迴路 (Simple circuit) 的無向連結圖 (undirected connected graph) ，而葉子 (Leaves) 的定義為次數 (Degrees) 為 1 的節點 (Nodes) 。一棵樹若有 2 個以上的節點，最少會有幾個節點是葉子？ (A)0 (B)1 (C)2 (D)3 。 [111 地方四等電子 ]   【 B 】 06. 使用相鄰矩陣 (Adjacency matrix

【四技試題】 【 B 】 01. 考量旅遊時最少成本路徑規劃問題，其模型如圖的圖 (Graph) 資料結構所示，邊 (Edge) 所標數值為其成本 (Cost) ，節點 1 到節點 6 間最少成本路徑之總成本為何？ (A)8 (B)10 (C)11 (D)18 。 [112 管理 ] 最少成本路徑： ①→③→④→⑤→⑥ 總成本 = 4+2+1+3=10

【選擇題】 【 B 】 01. 給定 {v1, v2, v3, v4, v5} 鄰接矩陣 (adjacency matrix) 如下，則 v1 到其他各點 ( 可以經過別的點 ) 的最短路徑距離何者正確？ (A)v1→v3 ，最短路徑距離 =3 (B)v1→v4 ，最短路徑距離 =3 (C)v1→v5 ，最短路徑距離 =∞ (D)v1→v2 ，最短路徑距離 =4 。 [110 身心五 等 ] (A)v1 → v2 → v3 ，最短路徑距離 =1+1=2 (B)v1 → v2 → v3 → v4 ，最短路徑距離 =1+1+1=3 (C)v1 → v2 → v4 ，最短路徑距離 =1+2+1=4 (D)v1 → v2 ，最短路徑距離 =1   【 C 】 02. 如下圖有一位老師從學校 A 出發要對 3 名學生進行家庭訪問，而一條路只能經過一次，請問老師最少需多少時間，才能訪問完 3 位學生並回到學校？ (A)13 (B)14 (C)15 (D)16 。 [110 初考資處 ] A-B-C-D-A → 3 + 9 + 2 + 8 = 22 A-B-D-C-A → 3 + 4 + 2 + 6 = 15 A-C-B-D-A → 6 + 9 + 4 + 8 = 27 A-C-D-B-A → 6 + 2 + 4 + 3 = 15 A-D-B-C-A → 8 + 4 + 9 + 6 = 27 A-D-C-B-A → 8 + 2 + 9 + 3 = 22   【 B 】 03. 下圖所示之 AOE(Activities on Edge) 網路 ， 其關鍵路徑 (Critical Path) 包含下列何者 ？ ( 表示由 X 到 Y 的有向邊 ) (A)<F,G> (B)<E,G> (C)<E,H> (D)<A,D> 。 [110 普考 電子 ] 關鍵路徑： A → B → C → E → G → J = 4+3+1+7+5=20     【 B 】 04. 一圖 (Graph)G 有 n 個節點 (Vertices) 以及 e 個邊 (Edges) ， 若用相鄰矩陣 (Adjacency matrix)A 來表示 G ， 則 A 中的元素 (Ele