离散11图的通路回路.ppt

《离散11图的通路回路.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.-吴扬扬制-1主要内容：图同构图的通路回路基本概念性质一个应用实例.-吴扬扬制-2§11.1图的基本概念5.图的同构图同构：设G1=,G2=,若存在双射函数f:V1→V2,使得u,vV1,[u,v]E1iff[f(u),f(v)]E2,且[u,v]与[f(u),f(v)]的重数相等，则称G1与G2同构，记作G1G2.指(u,v)或例6：下列两个图同构：bcdea54213∵有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显然

2、，f双射且（a,b)与(f(a),f(b))=(1,3)重数相等,…同构的必要条件：(2)

3、E1

4、=

5、E2

6、;(1)

7、V1

8、=

9、V2

10、;P223例题3§11.2通路回路和连通性1.通路和回路(1)定义:设G=,v0,v1,…,vnV,e1,e2,…,enE,其中ei关联于vi-1和vi(i=1,2,…,n),称v0e1v1e2…envn为顶点v0到顶点vn的通路，称v0和vn分别为该通路的起点和终点，称通路上边的数目为该通路的长度，若v0=vn,则称该通路为回路。若通路(回路)的所有边各不相同，则称之为简单通路(回路)。若通路(回路

11、)的所有顶点各不相同，则称之为基本通路(回路)。例1：v2cv3dv4V2cv3dv4ev2通路性质连通定义连通性质V1V2V3V5V4abcdefv2cv3dv4v4dv3cv2v2cv3dv4ev2基本通(回)路一定是简单通(回)路,反之不一定成立。V1V2V3V5V4abcdefg.-吴扬扬制-4性质:定理11.2.1设G=,

12、V

13、=n,u,vV,若存在从u到v的通路，则存在一条从u到v的长度不超过n-1的通路。证明:设v0e1v1e2…emvm为顶点u到顶点v的通路(v0=u,vm=v),长度为m,若m≤n-1,则v0e1v1

14、e2…emvm为长度不超过n-1的从u到v的通路；若m>n-1,则m+1>n,v0e1v1e2…emvm中至少有一个顶点出现两次以上，不妨设vi=vj(0≤ij≤m),从上述通路中删去vi到ej这段循环，§11.2通路回路和连通性1.通路和回路(2)v0v1…vivi+1…vj-1…vj则v0e1v1e2…viej+1…emvm是长度为m-(j-i)的从u到v的通路,重复上述过程可得到长度不超过n-1的u到v的通路。如例1…e1e2ejej+1ei.-吴扬扬制-5§11.2通路回路和连通性1.通路和回路(3)推论11.2.1设G=,

15、

16、V

17、=n,u,vV,若存在从u到v的通路，则存在一条从u到v的长度不超过n-1的基本通路。定理11.2.2设G=,

18、V

19、=n,uV,若存在从u到u的回路，则存在一条从u到u的长度不超过n的回路。推论11.2.2设G=,

20、V

21、=n,uV,若存在从u到u的回路，则存在一条从u到u的长度不超过n的基本回路。设G=,

22、V

23、=n,则(1)任何基本通路的长度均不大于n-1。(2)任何基本回路的长度均不大于n。对简单通路(回路)是否也成立,为什么?.-吴扬扬制-6§11.2通路回路和连通性1.通路和回路(4)例2：过河问题(

24、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,D,S}{M,S,C}{S}{M,S}{}从结点{M,D,S,C}到结点的通路就是安全的运送方案.MDSCD,CM,SD,C,MSDS,M,CM,S,DCSC,M,DM,SC,

25、DMSCD7§11.2通路回路和连通性2.图的连通性(1)定义：设G=,

26、V

27、=n,u,vV,若存在u到v的通路，则称u到v是可达的。如果u可达v，从u到v最短通路的长度称为u到v的距离，记作d(u，v)。设G=为无向图，若G的任何两个顶点是可达的，则称G是连通图。设G=为有向图，若u,vV，(1)u和v相互可达，则称G是强连通图；(2)u和v至少有一个可达另一个，则称G是单向连通图；(3)G的底图是连通的，则称G是弱连通图。例3：（a)（b)(c)(d)(e)有向图的极大强(单向、弱)连通子图，称为强(单向

28、、弱)连通分图.如例1中…连通性质8性质无向图G，结点间的可达性是结点集合上的等价关系，因此它决定了结点集合的一个划分。每个划分块导出的