《离散数学》课件-第5章 图的基本概念.pptx

第5章 图的基本概念5.1 无向图与有向图5.2 通路、回路、图的连通性5.3 图的矩阵表示5.4 最短路径和关键路径昆明理工大学津桥学院《离散数学》5.1 无向图及有向图无序对两个体x，y的无序序列称为无序对，记为(x,y)。 (x,y)=(y,x)无序积: A?B={(x,y) | x?A ? y?B} 如A={a,b},B={c,d} 则A?B={(a,c),(a,d),(b,c),(b,d)}= B?A A?A={(a,a),(a,b),(b,b)}多重集合: 元素可以重复出现的集合。无向图无向图G=V,E, 其中(1) V是非空有穷集合，其元素称为顶点。(2) E为V?V的多重子集，其元素称为无向边，简称边.如 G=V,E如图所示, 其中V={v1, v2, …,v5}, E={(v1,v1), (v1,v2), (v1,v5), (v2,v5), (v2,v3), (v2,v3), (v4,v5)} 有向图有向图D=V,E, 其中(1) V是非空有穷集合, 其元素称为顶点。(2) E为V?V的多重子集，其元素称为有向边，简称边.D的基图：用无向边代替所有有向边所得到的图如 D=V,E如图所示, V = {a, b, c, d}E = {a,a,a,b,a,b,a,d, b,c,c,d,d,c}注意：图的数学定义与图形表示,在 同构(待叙)的意义下是一一对应的 无向图与有向图的表示通常用G表示无向图，V(G)—— G的顶点集E(G)—— G的边集. ek表示无向边通常用D表示有向图,V(D)—— D的顶点集E(D)—— D的边集. ek表示有向边n 阶图—— n个顶点的图。有限图—— V, E都是有穷集合的图。 零 图—— E=?（即无边的图）。平凡图—— 1 阶零图（|V|=1，E= ?，只有一个顶点的图） 空 图—— V=?（无顶点的图） 常用G 泛指无向图和有向图.无向图顶点和边的关联设ek=(vi, vj)是无向图G=V,E的一条边,称vi, vj为ek的端点, ek与vi ( vj)关联. 若vi ? vj, 则称ek与vi ( vj)的关联次数为1;若vi = vj, 则称ek为环, 此时称ek与vi 的关联次数为2; 若vi不是ek端点, 则称 ek与vi 的关联次数为0. 如右图：v2, v5为e4的端点, e4与v2(v5)关联.e1为环, e1与v1 的关联次数为2e7与v4(v5)的关联次数为1、与v2关联次数为0无向图顶点和边的相邻设ek=(vi, vj)是无向图G=V,E的一条边,无边关联的顶点称作孤立点.若(vi,vj) ?E, 则称vi,vj相邻; 若ek,el至少有一个公共端点, 则称ek,el相邻.如右图：孤立点：v6顶点间的相邻：v4,v5相邻; 边之间的相邻：e2,e5相邻.有向图顶点和边的相邻设有向图D=V,E,设ek=vi, vj是有向图的一条边,又称vi是ek的始点,vj是ek的终点, vi邻接到vj, vj邻接于vi.如右图：a是e2的始点，b是e2的终点，a邻接到b, b邻接于a。无向图顶点的度数 设G=V,E为无向图, v?V, v的度数(度) d(v): v作为边的端点次数之和 悬挂顶点: 度数为1的顶点 悬挂边: 与悬挂顶点关联的边 G的最大度?(G)=max{d(v)| v?V} G的最小度?(G)=min{d(v)| v?V}如右图 d(v1)=4, d(v4)=1, ?(G)=4, ? (G)=1, v4是悬挂顶点, e7是悬挂边, e1是环 有向图顶点的度数设D=V,E为有向图, v?V, v的出度d+(v): v作为边的始点次数之和 v的入度d?(v): v作为边的终点次数之和 v的度数(度) d(v): v作为边的端点次数之和 d(v)= d+(v)+ d-(v)最大出度? +(D), 最小出度? +(D)最大入度? ?(D), 最小入度? ?(D)最大度?(D), 最小度?(D) 例如 d+(a)=4, d-(a)=1, d(a)=5,d+(b)=0, d-(b)=3, d(b)=3,?+(D)=4, ?+(D)=0, ??(D)=3, ??(D)=1, ?(D)=5,?(D)=3. 握手定理 定理 设图G=V,E无向图或有向图，|V|=n，|E|=m则图中所有顶点度数之和都等于边数的2倍。有向图的所有顶点入度之和等于出度之和等于边数.证 : 因为G中每条边（包括环）均有两个端点， 所以在计算G中各顶点度数之和时，每条边均 提供2度，m条边共提供2m度. 有向图的每条边提供一个入度和一个出度, 故所有顶点入度之和等于出度之和，且等于边数. 握手定理(续)推论 任何无向图和有向图中奇度顶点的个数必为偶数.证 : 设G=V,E为任意图