1.1.3 子圖與路徑

若圖G'=（V'，E'）的頂點集和邊集分別是另一個圖G=（V，E）的頂點集的子集和邊集的子集，即V'?V，且E'?E，則稱圖G'是圖G的子圖（Subgraph）。

在圖G=（V，E）中，若從頂點vi出發，沿著一些邊經過一些頂點，到達頂點vj，則稱邊序列為從頂點vi到頂點vj的一條路徑（Path，也可稱為通路），其中為圖G中的邊。

路徑的長度：路徑中邊的數目通常稱為路徑的長度L（Pij）=|Pij|。

頂點的距離：若存在至少一條路徑由頂點vi到達頂點vj，則定義vi到vj的距離為：

也即兩個頂點之間的距離由它們的最短路徑的長度決定。我們設d（vi，vj）=0，節點到自身的距離為0。

k階鄰居：若d（vi，vj）=k，我們稱vj為vi的k階鄰居。

k階子圖（k-subgraph）：我們稱一個頂點vi的k階子圖為：

有時，我們也稱k階子圖為k-hop。圖1-6中的陰影部分就是頂點V1的2階子圖。

圖1-6 圖G的2階子圖