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阶子图