計概17-01圖形理論－公職試題

【選擇題】

【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中的元素(Elements)應該有幾個？ (A)n (B)n² (C)n+e (D)n*e。[110鐵路員級]

相鄰矩陣有n個頂點，陣列A有n²個元素。

 

【D】05.如圖所示之網路，其Minimal Cost Spanning Tree的總成本，為下列何者？ (A)47 (B)58 (C)52 (D)57。[111地方四等電子]

16+12+18+6+5=57

 

【D】06.下列何者是強連通圖(Strongly connected graph)？ [111地方四等電子]

強連通：有向圖中，圖的每一個頂點都可從其他任意一點到達。

 

【D】07.在圖形理論(Graph Theory)中，有一個理論叫做尤拉循環(Eulerian Cycle)。該理論表示，每一個圖(Graph)的頂點(Vertex)有邊(Edge)來連接頂點，若從其中某一個頂點出發，經過所有的邊，然後又回到原先出發的頂點，請問需要具備什麼條件？ (A)連接到每一個頂點的邊數必須是奇數 (B)該圖中所有的邊數總和必須可以讓頂點數總和整除 (C)該圖中所有的邊數總和必須是頂點數總和的偶數倍數 (D)連接到每一個頂點的邊數必須是偶數。[112初考資處]

 尤拉循環：

a.無向圖：圖形需連通，圖中連接到每一個頂點的邊數必須是偶數。

b.有向圖：圖形需連通，圖中每一個頂點進入邊的邊數等於出去邊的邊數。

【B】08.下圖中從節點a至節點h的最短路徑，其長度為何？ (A)11 (B)12 (C)13 (D)14。[113地方四等電子]

a到h的最短路徑為a>c>i>h，長度=4+4+4=12

 

【B】09.何者不是下圖的子圖(Subgraph)？

[113地方四等電子]

(B)①③連線，與原圖不符

 

【A】10.n個節點的完全圖(complete graph)中所有邊的數量為下列何者？ (A)n(n-1)/2 (B)n²/2 (C)n(n+1)/2 (D)(n+1)²/2。[113身心四等資處]

完全圖的每個節點都與其他(n-1)個節點相連，每條邊計算2次(無向圖)，總共有n(n-1)/2條邊。

 

【D】11.下圖所示為連接a到g共7個觀光景點的快速道路分布圖。若小明想請你幫忙規劃行車路線，讓他能從某一個景點出發，並瀏覽到每一個路段的景色，但每個路段只想走一次，以免欣賞到重複的景色。下列何者應為提供給小明的資訊？ (A)不可能規劃出滿足小明要求的路線 (B)從任一個景點出發皆可以規劃出滿足小明要求的路線 (C)可以規劃出從a出發，行經每個路段一次，並回到a作為終點的路線 (D)可以規劃出從a出發，行經每個路段一次，但終點不是a的路線。[113身心四等電子]

 

【B】12.10個城市之間彼此的距離如下圖所示，若您預計從a城市出發前往z城市，最短的路線長度為多少？ (A)14 (B)15 (C)16 (D)17。[113原民四等]

a-e-d-h-g-z → 3+2+3+5+2=15

 

【D】13.給定圖(Graph)G，它具有V個頂點(Vertices)和E個邊(Edges)，且以鄰接矩陣(Adjacency matrix)儲存。下列何者是計算該圖邊數演算法的時間複雜度？ (A)O(V) (B)O(E²) (C)O(E) (D)O(V²)。[113普考電子]

具有V個頂點和E個邊的給定圖，其鄰接矩陣是V×V的矩陣，時間複雜度為O(V²)。