試題詳解

10 若 G 為一非“多重圖形＂（Multigraph）、無“自身邊線＂（Self edge）之無向圖形（Undirected graph）結 構，並以 V(G)表示 G 之頂點（Vertex）所成之集合（Set），E(G)表示 G 之邊線（Edge）所成之集合（Set）。 下列為有關 G 之敘述： ①使用廣度優先走訪（BFS）可找出 G 之所有連結單元（Connected component）。 ②若 G 不為完整圖形（Complete graph），則 G 之頂點中必存在一關節點（Articulation point）。 ③若H1與H2為G之 2 個連結單元（Connected components），則V(H1)∩V(H2)=φ。 ④若連結 G 之頂點 u 與 v 之邊線（Edge）為 G 之一橋邊（Bridge），則頂點 u 與 v 均為 G 之關節點 （Articulation point）。 ⑤若T1與T2為基於G之生成樹（Spanning tree），則V(T₁)∩V(T₂)=V(G)且E(T₁)∪E(T₂)=E(G)。 請選出最適合之選項。
(A)①③正確；②⑤錯誤
(B)③④正確；①⑤錯誤
(C)③⑤正確；②④錯誤
(D)④⑤正確；②③錯誤