路径与连通性
一、路徑
相鄰頂點之間的邊稱為路徑。
回路：起點和終點相同的路徑稱為回路。
簡單路徑：各個頂點都互不相同的路徑稱為簡單路徑。
圈：從一個起點出發，經過互不相同的頂點后，然后再回到起點的一條路徑成為圈。
二、連通性
如果一個無向圖每一對頂點之間都至少存在一條路徑，則稱為是連通的，否則就稱該圖是不連通的。一個不連通圖是由多個連通片組成。連通片是滿足如下兩個條件的子圖：
（1）連通性：子圖中任意兩個頂點之間都存在路徑。
（2）孤立性：不屬于該子圖的任意頂點與子圖中的任意頂點之間都不存在路徑。
包含頂點數最多的連通片稱為最大連通片。下圖為包含兩個連通片的一個不連通圖。
不連通網絡的鄰接矩陣可以通過對節點適當編號寫為如下的塊對角的形式。
三、路徑與連通性的鄰接矩陣表示
1、用鄰接矩陣表示兩點之間的路徑數量
我們用鄰接矩陣A=（aij_{ij}ij?）N?N_{N*N}N?N?來表示一個網絡中兩個節點之間的路徑數量。
如果節點i到節點j之間有1條邊，那么就存在一條長度為1的路徑。若存在長度為2的路徑，意味著中間還有一個節點k，k到i和j的路徑都為1。所以，兩個節點之間長度為2的不同路徑數量為：
當且僅當(A2^22)ij_{ij}ij?>0時存在長度為2的路徑。
同理，可以推得兩個節點i和j之間長度r>=1的不同路徑數量為：
我們定義兩個節點的距離為這兩個節點之間的最短路徑長度。節點i到節點j之間的距離不超過r>=1當且僅當
從而得到如下判據：
一個網絡是連通的當且僅當I+A+A2^22+…+AN?1^{N-1}N?1是正矩陣，即所有元素都為正數。
2、可約與不可約
若存在順列矩陣(即每行只有一個元素為1,其他元素均為0的正交矩陣)U,使得以下等式成立
則稱矩陣A可約；若不存在這樣的矩陣U，則稱矩陣A不可約。
因為節點i到j之間存在路徑等價于鄰接矩陣的元素不為0，由此可推得如下結論：一個網絡是連通的當且僅當其鄰接矩陣不可約。
四、割集與Menger定理
1、Menger定理
（1）點形式：設頂點s和頂點t為圖G中兩個不相鄰的頂點,則使頂點s和頂點t分別屬于不同的連通片所需去除的頂點的最少數目等于連接頂點s和頂點t的獨立的簡單路徑的最大數目。
（2）邊形式：設頂點s和頂點t為圖G中兩個不同的頂點，則使頂點s和頂點t分別屬于不同的連通片所需去除的邊的最少數目等于連接頂點s和頂點t的不相交的簡單路徑的最大數目。
注意：連接頂點s和頂點t的兩條簡單路徑是獨立的，是指這兩條路徑的公共頂點只有頂點s和頂點t。連接兩個頂點的簡單路徑稱為是不相交的是指這兩條路徑沒有經過一條相同的邊。
2、割集
（1）點割集：使得一對頂點分屬于不同的連通片所需去除的一組頂點稱為這對頂點的點割集。
（2）邊割集：使得一對頂點分屬于不同的連通片所需取出的一組邊稱為這對頂點的邊割集。
（3）極小割集：包含頂點數或邊數最少的割集稱為極小割集。
五、有向圖的連通性
在一個有向圖中采取如下操作:如果兩個頂點之間只有一條單向邊，那么就忝加一條反方向的邊。如果經過這樣添加邊的操作之后所得到的新的有向圖是強連通的，那么就稱原來的有向圖是弱連通的。
給定一個有向圖的一對頂點A和B,我們可以按以下方法確定是否存在從節點A到節點B的路徑：首先確定節點A和節點B所在的強連通片。如果節點A和B屬于同一強連通片，那么從節點A到B和從節點B到A的路徑都是存在的;否則的話,我們就看是否存在從節點A所在的強連通片指向節點B所在的強連通片的邊：如果存在,那么就存在從節點A到節點B的路徑；否則就肯定不存在這樣的路徑。
總結
