计算机类本科规划教材：《离散数学》课程配套电子教案（PPT课件讲稿）第9章 图论

第9章图论 设G是图9.14。结点集V上的连通关系为R,以下验证 R是V上的等价关系，并找出所有等价类。 R=<a,a心，<a,b>,<a,c>,<b,a心，<b,b>,<b,c>,<c,a>,<c,b>, <c,c>,<d,,<e,e>,<ef,<eg>,<e,h>,fe>,ff, fg>,f,h>,<g,e>,<gf,<8g,<g,h>,<h,e>,<hf <hg>,<h,h> =a,b,ct×a,b,cUd}×dUe,fg,h}×efg,h} 根据定义，R a 是V上的等价关 系。等价类有三 个，分别是： od Rabci,idr, e,fg,ht。 8 (a) (b) (c) 图9.14

第9章 图论 设G是图9.14。结点集V上的连通关系为R，以下验证 R是V上的等价关系，并找出所有等价类。 R=a,a,a,b,a,c,b,a,b,b,b,c,c,a,c,b, c,c,d,d,e,e,e,f,e,g,e,h,f,e, f,f, f,g,f,h,g,e,g,f,g,g,g,h,h,e,h,f, h,g,h,h =a,b,c×a,b,c∪d×d∪e,f,g,h×e,f,g,h 根据定义，R 是V上的等价关 系。等价类有三 个，分别是： a,b,c，d， e,f,g,h

第9章图论 定义9.3.2若无向图G中的任何两个结点都是连通的， 则称G为连通图。规定，平凡图是连通图。 定义9.3.3设G=<V,E>是图 (I)VcV且V,E,是G中两个端点都在V,中的边组 成的集合，图G<V,E>叫做G的由V导出的子图，记为 G[V]. (2)E,E且E,☑，V,是由E,中的边所关联的结点组成 的集合，图G2<V2,E2>叫做G的由E2导出的子图，记为 G[E2 在图9.15中，设图G为(a),取Va,b,c},则G的由 V导出的子图G[V]是(b)。取E2(a,b),(d,c)},G的由E,导 出的子图G[E,]是(c)

第9章 图论 定义9.3.2 若无向图G中的任何两个结点都是连通的， 则称G为连通图。规定，平凡图是连通图。 定义9.3.3 设G=V,E是图 ⑴V1V且V1 ≠，E1是G中两个端点都在V1中的边组 成的集合，图G1 =V1 ,E1 叫做G的由V1导出的子图，记为 G[V1 ]。 ⑵E2E且E2 ≠，V2是由E2中的边所关联的结点组成 的集合，图G2 =V2 ,E2 叫做G的由E2导出的子图，记为 G[E2 ]。 在图9.15中，设图G为(a)，取V1 =a,b,c，则G的由 V1导出的子图G[V1 ]是(b)。取E2 =(a,b),(d,c)，G的由E2导 出的子图G[E2 ]是(c)

第9章图论 a O b do do (a) (b) (c) 图9.15

第9章 图论

第9章图论 定义9.3.4设G=<V,E>是无向图，R是V上的连通关系， IR=V,V是R的等价类，=1，…，k}是关于R的商集， G[阴是导出的子图，称G[(=1,…,)为G的连通分支。 G的连通分支数记为W(G)。 设图9.14为G,在G中，连通关系R的三个等价类是 {a,b,c},d},e,fg,h},它们导出的G的子图分别是图 9.14中的(a),(b),(c)。它们都是G的连通分支。G的连通 分支数W(G)=3。 每一个连通分支中任何两个结点是连通的，而位于不 同连通分支中的任何两个结点是不连通的。即每一个连通 分支都是原图的最大的连通子图。在图9.14中，(a),(b), (c)都是最大的连通子图

第9章 图论 定义9.3.4 设G=V,E是无向图， R是V上的连通关系， V/R=ViVi是R的等价类，i=1,…,k 是V关于R的商集， G[Vi ]是Vi导出的子图，称G[Vi ]( i=1,…, k)为G的连通分支。 G的连通分支数记为W(G)。 设图9.14为G，在G中，连通关系R的三个等价类是 a,b,c，d，e,f,g,h ，它们导出的G的子图分别是图 9.14中的(a)，(b)，(c)。它们都是G的连通分支。G的连通 分支数W(G)=3。 每一个连通分支中任何两个结点是连通的，而位于不 同连通分支中的任何两个结点是不连通的。即每一个连通 分支都是原图的最大的连通子图。在图9.14中，(a)，(b)， (c)都是最大的连通子图

第9章图论 定义9.3.5设u,v是无向图G中的任意两个结点，若u 和v连通，则u和v之间最短路的长叫做结点u与结点v的距 离，记为d(u,y)。若u和v不连通，规定，u与v的距离为o。 即d(u,v)=0。 设G=<V,E>是无向图，u、v和w是V中的任意结点，G 的结点间的距离有以下的性质： ①d(u,)≥0 ②d(u,w)=0 ③d(w,)+d(v,w)≥d(u,w) ④d(u,v)=d(y,wW 在n阶无向完全图K,中，每两个不同结点间都有一条 边，它们的距离是1。在零图中，每两个不同结点间都没 有路，它们的距离都是o。 在图G中删除一个结点，就是将这个结点与它的所有 关联边全部删除。删除一个边，则仅去掉这个边

第9章 图论 定义9.3.5 设u，v是无向图G中的任意两个结点，若u 和v连通，则u和v之间最短路的长叫做结点u与结点v的距 离，记为d(u,v)。若u和v不连通，规定，u与v的距离为∞。 即d(u,v)=∞。 设G=V,E是无向图，u、v和w是V中的任意结点，G 的结点间的距离有以下的性质： ① d(u,v)≥0 ② d(u,u)=0 ③ d(u,v)＋d(v,w)≥d(u,w) ④ d(u,v)=d(v,u) 在n阶无向完全图Kn中，每两个不同结点间都有一条 边，它们的距离是1。在零图中，每两个不同结点间都没 有路，它们的距离都是∞。 在图G中删除一个结点，就是将这个结点与它的所有 关联边全部删除。删除一个边，则仅去掉这个边