离散图的通路回路.ppt

. -吴扬扬制- * 主要内容： 图同构 图的通路回路 基本概念 性质 一个应用实例 . -吴扬扬制- * §11.1 图的基本概念 5. 图的同构 图同构：设G1=V1,E1,G2=V2,E2,若存在双射函数f:V1→V2, 使得?u,v?V1,[u,v]?E1 iff [f(u),f(v)]?E2,且[u,v]与[f(u),f(v)] 的重数相等，则称G1与G2同构，记作G1?G2. 指(u,v)或u,v 例6：下列两个图同构： b c d e a 5 4 2 1 3 ∵ 有f:{a,b,c,d,e}→{1,2,3,4,5}, f(a)=1,f(b)=3,f(c)=5,f(d)=2,f(e)=4 显然，f双射且（a,b)与(f(a),f(b))=(1,3)重数相等,… 同构的必要条件： (2)|E1|=|E2|; (1)|V1|=|V2|; P223 例题 * §11.2 通路回路和连通性 1.通路和回路(1) 定义:设G=V,E,v0,v1,…,vn?V,e1,e2,…,en?E, 其中ei关联于vi-1和vi(i=1,2,…,n), 称v0e1v1e2…envn为顶点v0到顶点vn的通路， 称v0和vn分别为该通路的起点和终点， 称通路上边的数目为该通路的长度， 若v0=vn,则称该通路为回路。 若通路(回路)的所有边各不相同，则称之为简单通路(回路)。 若通路(回路)的所有顶点各不相同，则称之为基本通路(回路)。 例1： v2cv3dv4 V2cv3dv4ev2 通路性质 连通定义 连通性质 V1 V2 V3 V5 V4 a b c d e f v2cv3dv4 v4dv3cv2 v2cv3dv4ev2 基本通(回)路一定是 简单通(回)路, 反之不一定成立。 V1 V2 V3 V5 V4 a b c d e f g . -吴扬扬制- * 性质: 定理11.2.1 设G=V,E,|V|=n,u,v?V,若存在从u到v的通路， 则存在一条从u到v的长度不超过n-1的通路。 证明: 设v0e1v1e2…emvm为顶点u到顶点v的通路(v0=u,vm=v),长度为m, 若m≤n-1,则v0 e1 v1 e2…emvm为长度不超过n-1的从u到v的通路； 若mn-1,则m+1n,v0e1v1e2…emvm中至少有一个顶点出现两次以上， 不妨设vi=vj(0≤i?j≤m),从上述通路中删去vi到ej这段循环， §11.2 通路回路和连通性 1. 通路和回路(2) v0 v1 … vi vi+1 … vj-1 … vj 则v0e1v1e2…viej+1…emvm是长度为m-(j-i)的从u到v的通路, 重复上述过程可得到 长度不超过n-1的u到v的通路。 如例1 … e1 e2 ej ej+1 ei . -吴扬扬制- * §11.2 通路回路和连通性 1. 通路和回路(3) 推论11.2.1 设G=V,E,|V|=n,u,v?V,若存在从u到v的通路， 则存在一条从u到v的长度不超过n-1的基本通路。 定理11.2.2 设G=V, E, |V|=n, u?V, 若存在从u到u的回路， 则存在一条从u到u的长度不超过n的回路。 推论11.2.2 设G=V, E, |V|=n, u?V, 若存在从u到u的回路， 则存在一条从u到u的长度不超过n的基本回路。 设G=V,E,|V|=n,则 (1)任何基本通路的长度均不大于n-1。 (2)任何基本回路的长度均不大于n。 对简单通路(回路)是否也成立,为什么? . -吴扬扬制- * §11.2 通路回路和连通性 1. 通路和回路(4) 例2：过河问题(P225). 限定：每次只能带一样“东西”； 不能把狗和羊、羊和菜、狗和羊和菜单独留在一边。 解：V—原岸的状态集,E—状态变化. M-Man,D-Dog,S-Sheep,C-Cabbage； V={{M,D,S,C},{M,D,S},{M,D,C},{M,S,C},{M,S},{D,C},{D},{S},{C},?} {M,D,S,C} {D,C} {M,D,C} {D} {C} {M