图和子图1课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《图和子图1课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 课件
- 资源描述:
-
1、1.1 基本概念v现实世界的许多现象可以用一类图形来描述,这种图形由一个点集和连接这个点集中某些点对的线所构成例如用点表示车站,线表示连接车站与车站的道路;或者用点表示人,连线表示一对朋友在这种图形中,人们主要感兴趣的是:两点是否被一条线所连接,而连线的长短曲直则无关紧要大量的这类事实的数学抽象,产生了图的概念图的概念v有序三元组GV(G),E(G),G称为一个图,其中:v) V(G) 称为顶点集合;v) E(G)V(G)=,E(G)称为边集合;v) G是E(G)到(a,b)|a,bV(G)的映射,称为关联函数vV(G)中的元素称为顶点,E(G)中的元素称为边V(G)所含元素的个数即顶点个数称
2、为图的阶,用|V(G)|表示E(G)所含元素的个数称为G的边数,用|E(G)|表示我们用G(p,q)表添一个阶为p、边数为q的图G,这时也说G是一个(p,q)图例题vGV(G), E(G),G,其中: V(G)=v1,v2,v3,v4,E(G)=e1,e2,e3,e4,e5,e6, G定义为: vG(e1)=v2v3,G(e2)=v3v4 G(e3)=v4v4,G(e4)=v2v4 G(e5)=v2v3,G(e6)=v1v3v1v3v2v4e1e6e5e4e3e2v2v3v4v1e1e6e5e4e3e2相关概念v在图G V(G), E(G),G中,若eE(G),u,vV(G),而G(e)=(u
3、,v) ,则称u和v是e的端点,或e和u,v关联,此时称u和v是邻接的。若两条不同的边ei和ej有一个公共端点,则称是邻接的,不与任何边邻接的边称为孤立边,不与任何边关联的顶点称为孤立点。两端重合的边称为环,端点不同的边称为杆。v若V(G) 和E(G)都是有限集,则称G为有限图。G(0,0)称为空图, E(G)=即G是由孤立点所组成,称为零图。G(1,0)称为平凡图。简单图和完全图v图中若连接两个相同顶点的边的条数大于1,则说这对顶点间有重边相连同一对顶点间边的条数称为边的重数,既没有环也没有重边的图称为简单图,否则称为伪图,没有环的伪图称为多重图v每对不同的顶点均有边相连的简单图称为完全图n
4、阶完全图记为Knv定理定理1.1:Kn有) 1(212nnCn条边二分图v图G的顶点集V(G)若能分成两个子集V1和V2,使得G的每条边有一个端点在V1 ,另一个端点在V2中,则G称为二分图或偶图这样一个把V(G)分成两个集合V1 、V2的分划(V1,V2)称为G的一个二分划v 设简单二分图G的二分划为(V1 ,V2),如果V1的每个顶点与V2的每一个顶点都邻接,则G称为完全二分图若| V1 |=m,| V2 |=n,则这样的图记为Km,nv定理定理1.2 Km,n有mn条边。补图vG是简单图,如果简单图GC满足,v) V(GC)= V(G)v) V(GC)中两点当且仅当它们在G中不邻接时在G
5、C中邻接v那么GC称为G的补图v1v2v3v4v5v1v2v3v4v5G:GC :平面图v在保持图的顶点和边的关联关系不变的情况下,一个图可以作出许多图形如果一个图具有这样的图形,它的边仅在顶点处相交,则称它为平面图v判断图1是否为平面图?v1v2v3v4v5v1v2v3v4v5图1:图2:恒同和同构v两个图H和G,如果V(H)V(G),E(H)E(G)且H G,那么H和G就称为是恒同的,恒同的图当然可以用一个图形来表示vGV(G),E(G),G 和HV(H),E(H),H,若存在1-1对应偶(,),:V(G) V(H);:E(G) E(H),使得当且仅当H(e)=(u) (v)时, G(e)
6、=uv,则说这两个图同构,记为G Hbcfeade1e2e6e5e3e41234度与正则图v设vV(G),G中与顶点v关联的边的数目称为v在G中的度(次),记为dG(v)或d(v)v一个环的端点的度数计为2v如果d(v)是奇数,就说v是奇顶点;如果d(v)是偶数,就说v是偶顶点v如果一个图的每一个顶点都具有相同的度,则称这个图是正则图。每个顶点的度均为k的正则图,称为k-正则图v1v2v3v4v5有关度的定理v定理定理1.3 图G中各顶点度数之和等于边数的2倍。v推论推论1.4 任意一个图奇顶点的个数是偶数v推论推论1.5 正则图的阶与各顶点度数不全为奇数子图v设H和G是两个图,如果V(H)是
展开阅读全文