基本介紹
嚴格定義,相關概念,性質,
嚴格定義
對一個圖G= (V,E)中的兩點x和y,若存在交替的頂點和邊的序列
(在有向圖中要求有向邊
屬於E),則兩點 x和y是連通的。
是一條x到y的連通路徑,x和y分別是起點和終點。當x=y時,
被稱為迴路。如果通路
中的邊兩兩不同,則
是一條簡單通路,否則為一條複雜通路。如果圖G中每兩點間皆連通,則G是連通圖。






相關概念
強連通圖:有向圖 G=(V,E) 中,若對於V中任意兩個不同的頂點 x和 y,都存在從x到 y以及從 y到 x的路徑,則稱 G是強連通圖。相應地有強連通分量的概念。強連通圖只有一個強連通分量,即是其自身;非強連通的有向圖有多個強連分量。
弱連通圖:將有向圖的所有的有向邊替換為無向邊,所得到的圖稱為原圖的基圖。如果一個有向圖的基圖是連通圖,則有向圖是弱連通圖。
初級通路:通路中所有的頂點互不相同。初級通路必為簡單通路,但反之不真。
性質
沒有迴路的無向圖是連通的若且唯若它是樹,即等價於:|E|=|V|-1。