第8章 图论
定义8.2―2 ：路径P中所含边的条数称为路径P的
长度。长度为0的路径定义为单独一个顶点。(但注意习惯上 不定义长度为0的回路。) 定义8.2―3：在图G=〈V,E〉中,从结点vi到vj最短路径的 长度叫从vi到vj的距离,记为d(vi,vj)。若从vi到vj不存在路径,则 d(vi,vj)=∞。 注意,在有向图中,d(vi,vj)不一定等于d(vj,vi),但一般地满足 以下性质: (1) d(vi,vj)≥0; (2) d(vi,vi)=0; (3) d(vi,vj)+d(vj,vk)≥d(vi,vk)。
个图是混合图。
我们仅讨论有向图和无向图,且V(G)和E(G)限于有限集合。
第8章 图论
图 8.1―2
第8章 图论
【约定】：用〈a,b〉表示有向边，(a,b)表示无向边, 既表示有向边又表示无向边时用［a,b］。 于是,图8.1―1中的G和图8.1―2中的G′可分别简记为 G=〈V,E〉=〈{a,b,c,d},{(a,b),(a,c),(b,d),(b,c),(d,c),(a,d),(b,b)}〉
边的方向)和边的重数；
则这两个图是同构的,两个同构的图除了顶点和边的名称不 同外实际上代表同样的组合结构。
第8章 图论
例8.1-2
(1) 图8.1―6所示的(a)、(b)两图是同构的。因为可 作映射:g(1)=v3,g(2)=v1,g(3)=v4,g(4)=v2。在这映射下,边 〈1,3〉,〈1,2〉,〈2,4〉和〈3,4〉分别映射到〈v3,v4〉, 〈v3,v1〉,〈v1,v2〉和〈v4,v2〉,而后面这些边又是(b)中 仅有的边。
在V上的函数，g是定义在E上的函数。
第8章 图论
图 8.1―4
