計概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.有向圖：圖形需連通，圖中每一個頂點進入邊的邊數等於出去邊的邊數。