离散数学第十四章图论基本概念.ppt
《离散数学第十四章图论基本概念.ppt》由会员分享,可在线阅读,更多相关《离散数学第十四章图论基本概念.ppt(51页珍藏版)》请在三一文库上搜索。
1、1,第五部分 图论,本部分主要内容 图的基本概念 欧拉图、哈密顿图 树 平面图 支配集、覆盖集、独立集、匹配与着色,2,第十四章 图的基本概念,主要内容 图 通路与回路 图的连通性 图的矩阵表示 图的运算 预备知识 多重集合元素可以重复出现的集合 无序集AB=(x,y) | xAyB,3,14.1 图,定义14.1 无向图G = , 其中 (1) V 为顶点集,元素称为顶点 (2) E为VV 的多重集,其元素称为无向边,简称边 实例 设 V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,
2、v5) 则 G = 为一无向图,4,有向图,定义14.2 有向图D=, 只需注意E是VV 的多重子集 图2表示的是一个有向图,试写出它的V 和 E 注意:图的数学定义与图形表示,在同构(待叙)的意义下 是一一对应的,5,相关概念,1. 图 可用G泛指图(无向的或有向的) V(G), E(G), V(D), E(D) n阶图 2. 有限图 3. n 阶零图与平凡图 4. 空图 5. 用 ek 表示无向边或有向边 6. 顶点与边的关联关系 关联、关联次数 环 孤立点 7. 顶点之间的相邻与邻接关系,6,8. 邻域与关联集 vV(G) (G为无向图),v 的关联集, vV(D) (D为有向图),9.
3、 标定图与非标定图 10. 基图,相关概念,7,多重图与简单图,定义14.3 (1) 无向图中的平行边及重数 (2) 有向图中的平行边及重数(注意方向性) (3) 多重图 (4) 简单图 在定义14.3中定义的简单图是极其重要的概念,8,顶点的度数,定义14.4 (1) 设G=为无向图, vV, d(v)v的度数, 简称度 (2) 设D=为有向图, vV, d+(v)v的出度 d(v)v的入度 d(v)v的度或度数 (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇顶点度与偶度顶点,9,定理14.1 设G=为任意无向图,V=v1,v2,v
4、n, |E|=m, 则,证 G中每条边 (包括环) 均有两个端点,所以在计算G中各顶点度数之和时,每条边均提供2度,m 条边共提供 2m 度.,本定理的证明类似于定理14.1,握手定理,定理14.2 设D=为任意有向图,V=v1,v2,vn, |E|=m, 则,10,握手定理推论,推论 任何图 (无向或有向) 中,奇度顶点的个数是偶数. 证 设G=为任意图,令 V1=v | vV d(v)为奇数 V2=v | vV d(v)为偶数 则V1V2=V, V1V2=,由握手定理可知 由于2m, 均为偶数,所以 为偶数,但因为V1中 顶点度数为奇数,所以|V1|必为偶数.,11,例1 无向图G有16条
5、边,3个4度顶点,4个3度顶点,其余顶点度数均小于3,问G的阶数n为几?,解 本题的关键是应用握手定理. 设除3度与4度顶点外,还有x个顶点v1, v2, , vx, 则 d(vi) 2,i =1, 2, , x, 于是得不等式 32 24+2x 得 x 4, 阶数 n 4+4+3=11.,握手定理应用,12,图的度数列,1 . V=v1, v2, , vn为无向图G的顶点集,称d(v1), d(v2), , d(vn)为G的度数列 2. V=v1, v2, , vn为有向图D的顶点集, D的度数列:d(v1), d(v2), , d(vn) D的出度列:d+(v1), d+(v2), , d
6、+(vn) D的入度列:d(v1), d(v2), , d(vn) 3. 非负整数列d=(d1, d2, , dn)是可图化的,是可简单图化的. 易知:(2, 4, 6, 8, 10),(1, 3, 3, 3, 4) 是可图化的,后者又是可 简单图化的,而(2, 2, 3, 4, 5),(3, 3, 3, 4) 都不是可简单图化 的,特别是后者也不是可图化的,13,图的同构,定义14.5 设G1=, G2=为两个无向图(两个有向 图),若存在双射函数f:V1V2, 对于vi,vjV1, (vi,vj)E1 当且仅当 (f(vi),f(vj)E2 (E1 当且仅当 E2 ) 并且, (vi,vj
7、)()与 (f(vi),f(vj)()的重数相 同,则称G1与G2是同构的,记作G1G2.,图之间的同构关系具有自反性、对称性和传递性. 能找到多条同构的必要条件,但它们全不是充分条件: 边数相同,顶点数相同; 度数列相同; 对应顶点的关联集及邻域的元素个数相同,等等 若破坏必要条件,则两图不同构 判断两个图同构是个难题,14,图同构的实例,图中(1)与(2)的度数列相同,它们同构吗?为什么?,(1) (2) (3) (4),图中,(1)与(2)不同构(度数列不同),(3)与(4)也不同构.,(1) (2),15,n 阶完全图与竞赛图,定义14.6 (1) n (n1) 阶无向完全图每个顶点与
8、其余顶点均相邻的无向简单图,记作 Kn. 简单性质:边数 (2) n (n1)阶有向完全图每对顶点之间均有两条方向相反的有向边的有向简单图. 简单性质: (3) n (n1) 阶竞赛图基图为Kn的有向简单图. 简单性质:边数,16,n 阶 k 正则图,(1)为K5,(2)为3阶有向完全图,(3)为4阶竞赛图.,(1) (2) (3),定义14.7 n 阶k正则图=k 的无向简单图 简单性质:边数(由握手定理得) Kn是 n1正则图, 彼得松图(见书上图14.3(1) 所示,记住它),17,子图,定义14.8 G=, G= (1) GG G为G的子图,G为G的母图 (2) 若GG且V=V,则称G
9、为G的生成子图 (3) 若VV或EE,称G为G的真子图 (4) V(VV且V)的导出子图,记作GV (5) E(EE且E)的导出子图,记作GE,18,例2 画出K4的所有非同构的生成子图,实例,19,补图,定义14.9 设G=为n阶无向简单图,以V为顶点集,以所有使G成为完全图Kn的添加边组成的集合为边集的图,称为G的补图,记作 . 若G , 则称G是自补图. 相对于K4, 求上面图中所有图的补图,并指出哪些是自补图. 问:互为自补图的两个图的边数有何关系?,20,14.2 通路与回路,定义14.11 给定图G=(无向或有向的),G中顶点与 边的交替序列 = v0e1v1e2elvl, vi1
10、, vi 是 ei 的端点. (1) 通路与回路: 为通路;若 v0=vl, 为回路,l 为回路长 度. (2) 简单通路与回路:所有边各异, 为简单通路,又若v0=vl, 为简单回路 (3) 初级通路(路径)与初级回路(圈): 中所有顶点各异,则称 为初级通路(路径),又若除v0=vl,所有的顶点各不相同且所有的边各异,则称 为初级回路(圈) (4) 复杂通路与回路:有边重复出现,21,几点说明,表示法 定义表示法 只用边表示法 只用顶点表示法(在简单图中) 混合表示法 环(长为1的圈)的长度为1,两条平行边构成的圈长度为 2,无向简单图中,圈长3,有向简单图中圈的长度2. 不同的圈(以长度
11、3的为例) 定义意义下 无向图:图中长度为l(l3)的圈,定义意义下为2l个 有向图:图中长度为l(l3)的圈,定义意义下为l个 同构意义下:长度相同的圈均为1个 试讨论l=3和l=4的情况,22,通路与回路的长度,定理14.5 在n 阶图G中,若从顶点vi 到vj(vivj)存在通路, 则从vi 到 vj 存在长度小于或等于n1 的通路. 推论 在 n 阶图G中,若从顶点vi 到 vj(vivj)存在通路,则 从vi 到vj 存在长度小于或等于n1的初级通路(路径). 定理14.6 在一个n 阶图G中,若存在 vi 到自身的回路,则一 定存在vi 到自身长度小于或等于 n 的回路. 推论 在
12、一个n 阶图G中,若存在 vi 到自身的简单回路,则一 定存在长度小于或等于n 的初级回路.,23,14.3 图的连通性,无向图的连通性 (1) 顶点之间的连通关系:G=为无向图 若 vi 与 vj 之间有通路,则 vivj 是V上的等价关系 R=| u,v V且uv (2) G的连通性与连通分支 若u,vV,uv,则称G连通 V/R=V1,V2,Vk,称GV1, GV2, ,GVk为连通分 支,其个数 p(G)=k (k1); k=1,G连通,24,短程线与距离,(3) 短程线与距离 u与v之间的短程线:uv,u与v之间长度最短的通路 u与v之间的距离:d(u,v)短程线的长度 d(u,v)
13、的性质: d(u,v)0, uv时d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w),25,无向图的连通度,1. 删除顶点及删除边 Gv 从G中将v及关联的边去掉 GV从G中删除V中所有的顶点 Ge 将e从G中去掉 GE删除E中所有边 2. 点割集与边割集 点割集与割点 定义14.16 G=, VV V为点割集p(GV)p(G)且有极小性 v为割点v为点割集 定义14.17 G=, EE E是边割集p(GE)p(G)且有极小性 e是割边(桥)e为边割集,26,点割集与割点,例3 v1,v4,v6是点 割集,v6是割点. v2,v5 是点割集吗? e1,e2,e1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第十四 章图论 基本概念
链接地址:https://www.31doc.com/p-2252363.html