第章图论 设G是图914。结点集V上的连通关系为R,以下验证 R是Ⅳ上的等价关系,并找出所有等价类 R=<a.a>sa bx <ac>. <ba<bb>. < b.c>. <C a>. <c b <C,C>,<d,d,<ee><ef>,<8>,<e,h>,,e>,<f, f8>,<h>,ge>,gf>,<g8>,<g,小>,<h,e><hf, <hg>,<h,h> ab,c}×{a,b,c%Ud×dU1e/g,h}×1eJg,h 根据定义,RaQ e o -o h 是V上的等价关 系。等价类有三 个,分别是 od Ra.bcs, ds h ,h7 g (b) 图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
第章图论 定义932若无向图G中的任何两个结点都是连通的, 则称G为连通图。规定,平凡图是连通图。 定义93.3设G=<VE>是图 (1)V1c阻且V掷,E1是G中两个端点都在V中的边组 成的集合,图G=<VE1>叫做G的由V导出的子图,记为 (2)E2CE且E2,V2是由E2中的边所关联的结点组成 的集合,图G2=<V2E2>叫做G的由E2导出的子图,记为 GlE, 在图915中,设图G为(a),取a,b,c},则G的由 V导出的子图G1是(b)。取E2=(a,b)(dc)},G的由E2导 出的子图GE2]是(c)
第9章 图论 定义9.3.2 若无向图G中的任何两个结点都是连通的， 则称G为连通图。规定，平凡图是连通图。 定义9.3.3 设G=V,E是图 ⑴V1V且V1 ≠，E1是G中两个端点都在V1中的边组 成的集合，图G1 =V1 ,E1 叫做G的由V1导出的子图，记为 G[V1 ]。 ⑵E2E且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)
第章图论 ob a b o b ○c 图9.15
第9章 图论
第章图论 定义934设G=<V,E>是无向图,R是V上的连通关系 VR=v是R的等价类,=1…k}是关于R的商集, O[是V导出的子图,称((=13…1)为G的连通分支 G的连通分支数记为W(G) 设图914为G,在G中,连通关系R的三个等价类是 1a,b,c,1d},e,g,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=ViVi是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)都是最大的连通子图
第章图论 定义93.5设u,是无向图G中的任意两个结点,若u 和ν连通,则v和ν之间最短路的长叫做结点u与结点v的距 离,记为d(l,)。若l4和v不连通,规定,u与v的距离为∞ 即d(l,v)=∞ 设G=<V,E>是无向图,、yp和形是T中的任意结点,G 的结点间的距离有以下的性质 ①d(l,v)20 ②d(l,)=0 8d(u, v )+d(vy)≥d(lw) ④d(lv)=d(v,l 在n阶无向完全图K中,每两个不同结点间都有一条 边,它们的距离是1。在零图中,每两个不同结点间都没 有路,它们的距离都是∞ 在图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中删除一个结点，就是将这个结点与它的所有 关联边全部删除。删除一个边，则仅去掉这个边