擁有 3 個端點（vertices）v0, v1, v2 的圖形（graph）可用下列的相鄰矩陣（adjacency matrix）表示：v0 v1 v2 / v0 [0 1 0] / v1 [0 1 0] / v2 [1 0 0]。下列敘述何者正確？

A該圖形為無向圖形（undirected graph）

B該圖形為完全圖形（complete graph）

C端點 v2 的分支度（degree；為入分支度（in-degree）與出分支度（out-degree）之和）為 0

D端點 v1 的分支度為 3正確答案

答案與詳解

正確答案

相鄰矩陣不對稱→有向圖；v1 的 in-degree=2、out-degree=1，合計 3。

A該圖形為無向圖形（undirected graph）對稱性判斷✕ 易錯陷阱

無向圖的相鄰矩陣必為對稱矩陣。此矩陣 M[1][0]=0 但 M[0][1]=1、M[2][0]=1 但 M[0][2]=0，不對稱，故為有向圖。

B該圖形為完全圖形（complete graph）完全圖定義✕ 錯誤

完全圖需任兩頂點間都有邊（對角線外全為 1）。此矩陣多處為 0，且含自迴路 v1→v1，明顯非完全圖。

C端點 v2 的分支度（degree；為入分支度（in-degree）與出分支度（out-degree）之和）為 0✕ 易錯陷阱

D端點 v1 的分支度為 3✓ 正確

這題的完整詳解,註冊就能看 · 每天 2 題免費

精選詳解