《离散11图的通路回路.ppt》由会员分享，可在线阅读，更多相关《离散11图的通路回路.ppt（11页珍藏版）》请在三一办公上搜索。
1、.-吴扬扬制-,1,主要内容：,图同构图的通路回路基本概念性质一个应用实例,.-吴扬扬制-,2,11.1 图的基本概念 5.图的同构,图同构：设G1=,G2=,若存在双射函数f:V1V2,使得u,vV1,u,vE1 iff f(u),f(v)E2,且u,v与f(u),f(v)的重数相等，则称G1与G2同构，记作G1G2.,指(u,v)或,例6：下列两个图同构：,有f:a,b,c,d,e1,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)|
2、V1|=|V2|;,P223 例题,3,11.2 通路回路和连通性 1.通路和回路(1),定义:设G=,v0,v1,vnV,e1,e2,enE,其中ei关联于vi-1和vi(i=1,2,n),称v0e1v1e2envn为顶点v0到顶点vn的通路，称v0和vn分别为该通路的起点和终点，称通路上边的数目为该通路的长度，若v0=vn,则称该通路为回路。若通路(回路)的所有边各不相同，则称之为简单通路(回路)。若通路(回路)的所有顶点各不相同，则称之为基本通路(回路)。例1：,v2cv3dv4,V2cv3dv4ev2,通路性质连通定义连通性质,v2cv3dv4,v4dv3cv2,v2cv3dv4ev2
3、,基本通(回)路一定是简单通(回)路,反之不一定成立。,.-吴扬扬制-,4,性质:定理11.2.1 设G=,|V|=n,u,vV,若存在从u到v的通路，则存在一条从u到v的长度不超过n-1的通路。证明:设v0e1v1e2emvm为顶点u到顶点v的通路(v0=u,vm=v),长度为m,若mn-1,则v0 e1 v1 e2emvm为长度不超过n-1的从u到v的通路；若mn-1,则m+1n,v0e1v1e2emvm中至少有一个顶点出现两次以上，不妨设vi=vj(0ijm),从上述通路中删去vi到ej这段循环，,11.2 通路回路和连通性 1.通路和回路(2),vj,则v0e1v1e2viej+1em
4、vm是长度为m-(j-i)的从u到v的通路,重复上述过程可得到长度不超过n-1的u到v的通路。如例1,e1,e2,ej,ej+1,ei,.-吴扬扬制-,5,11.2 通路回路和连通性 1.通路和回路(3),推论11.2.1 设G=,|V|=n,u,vV,若存在从u到v的通路，则存在一条从u到v的长度不超过n-1的基本通路。定理11.2.2 设G=,|V|=n,uV,若存在从u到u的回路，则存在一条从u到u的长度不超过n的回路。推论11.2.2 设G=,|V|=n,uV,若存在从u到u的回路，则存在一条从u到u的长度不超过n的基本回路。设G=,|V|=n,则(1)任何基本通路的长度均不大于n-1
5、。(2)任何基本回路的长度均不大于n。对简单通路(回路)是否也成立,为什么?,.-吴扬扬制-,6,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到结点的通路就是安全的运送方案.,MDSC,D,C,M,S,D,C,M,S,D,S,M,C,M,S,D,C,S,C,M,D,M,S,C,D,MSCD,7
6、,11.2 通路回路和连通性 2.图的连通性(1),定义：设G=,|V|=n,u,vV,若存在u到v的通路，则称u到v是可达的。如果u可达v，从u到v最短通路的长度称为u到v的距离，记作d(u，v)。设G=为无向图，若G的任何两个顶点是可达的，则称G是连通图。设G=为有向图，若u,vV，(1)u和v相互可达，则称G是强连通图；(2)u和v至少有一个可达另一个，则称G是单向连通图；(3)G的底图是连通的，则称G是弱连通图。例3：,有向图的极大强(单向、弱)连通子图，称为强(单向、弱)连通分图.如例1中,连通性质,8,性质无向图G，结点间的可达性是结点集合上的等价关系，因此它决定了 结点集合的一个
7、划分。每个划分块导出的子图称为G的连通分图，G的连通分图的个数记为p(G)。如例3(b)定理11.2.3 有向图强连通 iff 存在经过每个顶点至少一次的回路。如例3,(证明P227)设G=为有向图，定义V上的二元关系Ri(i=1,2,3),u,vV，uR1v iff 在G中u和v相互可达；uR2v iff 在G中u可达v或v可达u；uR3v iff 在G的底图中u可达v，则(1)R1和R3是等价关系;(2)R2是相容关系，但不是等价关系。,11.2 通路回路和连通性 2.图的连通性(2),R1的等价类是什么子图？分析例1,.-吴扬扬制-,9,资源分配图-有向图的一个应用实例(1),资源分配问
8、题计算机系统中的程序共享系统资源，如磁盘、CPU、主存贮器等，当一个程序要求使用某种资源，它需向操作系统发出请求。对资源的请求可能发生冲突，如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。资源分配图 令Pt=p1，pm为计算机系统在时间t的程序集合，Rt=r1，r2，rn为计算机系统在时刻t的资源集合，资源分配图Gt=是有向图，其中 E iff 程序pk已分配到资源ri且等待资源rj。,时刻t计算机系统处于死锁状态 iff 资源分配图Gt中包含强连通分图。,例,.-吴扬扬制-,10,资源分配图-有向图的一个应用实例(2),例:设Rt=r1,r2,r3,r4，Pt=p1,p2,p3,p4。资源分配状态是：p1占用资源r4且请求资源r1；p2占用资源r1且请求资源r2和r3；p3占用资源r2且请求资源r3；p4占用资源r3且请求资源r1和r4。资源分配图Gt=为：,此时系统是否处于死锁状态？,资源图,.-吴扬扬制-,11,作业：P230 1,4,
