Question

柚子

這兩題

第5頁
共3 頁
10 12
(A17)
DE 繁體中文(台灣)
12、13. 為題組。閱讀下文,回答12、13題
C
在圖論中,如果一個有向圖從任意頂點出發無法經過若干條邊回到該點,則這個圖是一個
有向無環圖。因為有向無環圖中從一個點到另一個點有可能存在兩種路線,因此有向無環圖未
必能轉化成樹,但任何有向樹均為有向無環圖 圖由頂點和連接這些頂點的邊所構成。每條
邊都帶有從一個頂點指向另一個頂點的方向的圖為有向圖。有向圖中的道路為一系列的邊,系
列中每條邊的終點都是下一條邊的起點:如果一條路徑的起點是這條路徑的終點,那麼這條路
徑就是一個環。有向無環圖即為沒有環出現的有向圖 -4
當存在一條從頂點甲到頂點乙的路徑時,頂點乙被稱作是從頂點甲可達的。每個頂點都是
從自身可達的,通過一條沒有邊的路径,如果一個頂點可以從一個非平凡路徑,一條由一個或
更多邊組成的路徑到達自身,那麼這條路徑就是一個環-因此,有向無環圖也可以被定義為沒
2
16 18 20 22 24 26 28 30
有頂點可以通過非平凡路徑到達自身的圈:(維基百科(有向無環圖〉)。
12. 依據本文與下圖,試分析有向無環圖(DAG)在頂點7到其他頂點的最長路徑:
5
8
2
z 協助工具: 無法使用
6
N
12
7
6
。
3
34 30 38
5
國語文綜合能力測驗
I

13 頁
有頂點可以通過非平凡路徑到達自身的圖(維基百科〈有向無環圖〉)。
12. 依據本文與下圖,試分析有向無環(DAG)在頂點7到其他頂點的最長路徑:
A 74
B8
C94
D10
12278 個字
J
1
2
5.
AD、②皆正確
B、2錯誤
C①正確,②錯誤H
DD錯誤,②正確
8
2
0
2
区 繁體中文(台灣) 李協助工具:無法使用,
7
6
3.
13. 若依據上文進行1、2兩項推論,最適當的研判是:-
①给定一個加權有向無環圖和一個源頂點,找出從源頂點到圖中所有其他頂點的最長路徑
7
,若無法從給定的源頂點到達頂點,則將其距離打印為無窮大一
②有向樹可以是一個有像無環圖,但是有向無環圖並非直接等於有向樹,其中原因在於有
向樹中無法經過兩種路線到達同一頂點形成圈環
P
國語又际合刀最
I