离散数学CH04图论基本概念.ppt
《离散数学CH04图论基本概念.ppt》由会员分享,可在线阅读,更多相关《离散数学CH04图论基本概念.ppt(67页珍藏版)》请在三一文库上搜索。
1、离散数学 Discrete Mathematics,计算机与信息工程学院,第4章 图 论,内容提要,图的基本概念,4.1,连通图,4.3,4.4,图的矩阵表示,路和回路,4.2,内容提要,欧拉图和哈密顿图,4.5,二部图及匹配,4.7,4.8,平面图,树,4.6,有趣的图论问题,能否从河岸或小岛出发,通过每一座桥,且仅通过一次回到原地?,问题,图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一篇论文,解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。以及在民间广为流传的一些游戏问题:例如 迷宫问题、棋盘上马的行走路线问题等等
2、。这些古老的问题当时吸引了许多学者的注意,从而在这些问题研究的基础上,又提出了著名的四色猜想和环游世界各国的问题。,有趣的图论问题,图,有趣的图论问题,一个人带着一只狼、一只羊和一捆草要渡河,由于船太小,人做摆渡者一次只能运送一个“乘客”,很显然,如果人不在,狼要吃羊,羊要吃草,问人怎样才能把它们平安地渡过河去?,有趣的图论问题,解 这是通路问题的一个典型实例。用f表示人,w表示狼,s表示羊,h表示草。 集合f,w,s,h中能平安在一起的子集有:f,w,s,h,f,w,s,f,s,h,f,w,h,f,w,f,s,f,h,w,h,f,w,s,h。用顶点表示渡河过程中的状态,状态是二元组:第一元素
3、是集合f,w,s,h在渡河过程中留在原岸的子集,第二元素是在彼岸的子集,将一次渡河后代表状态变化的顶点间连边,得图。容易看出,一条路径就是一种渡河方案。,有趣的图论问题,有趣的图论问题,图可直观地表示离散对象之间的相互关系,研究它们的共性和特性,以便解决具体问题。 一个图是由一些结点和连接两结点间的连线组成,至于连线的长短、曲直及结点的位置是无关紧要的.,4.1 图的基本概念,4.1 图的基本概念,下面表示的是同一个图,什么是图?可用一句话概括 图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。因为它显得太抽象,不便于理解,所以有必要给出另外的回答。下面便是把图作为代数结
4、构的一个定义。,4.1 图的基本概念,定义1 一个图G定义为一个三元组,记作G=。其中V是个非空有限集合,它的元素称为结点;E也是个有限集合,其元素称为边,而是从E到V中的有序对或无序对的映射。,4.1 图的基本概念,由定义可知,图G中的每条边都与图中的无序或有序结点对相联系的。若边eE与无序结点对(vi,vj)相联系,则(e)=(vi,vj),这时边e称为无向边,有时简称为边;若边eE与有序结点对相联系,则(e)=,此时边e称为有向边或弧,vi称为弧e的始结点,vj称为弧e的终结点。,4.1 图的基本概念,【例4.1】G=V(G),E(G),G 其中:V(G)=a,b,c,d E(G)=e1
5、,e2,e3,e4 G:G(e1)=(a,b) G(e2)=(b,c) G(e3)=(a,c) G(e4)=(a,a) 试画出G的图形。,4.1 图的基本概念,【例4.1】 解:G的图形如图所示。,4.1 图的基本概念,定义2 在图G=中,如果每条边都是弧,该图称为有向图;若每条边都是无向边,该图G称为无向图;如果有些边是有向边,另一些边是无向边,图G称为混合图。,4.1 图的基本概念,4.1 图的基本概念,有向图,无向图,混合图,定义3 在有向图G=中,对任意结点vV,以v为始结点的弧的条数,称为结点v的出度,记为d+(v);以v为终结点的弧的条数,称为v的入度,记作d-(v);结点v的出度
6、与入度之和,称为结点的度数(degree),记为d(v),显然d(v)=d+(v)+d-(v)。一个度数为0的结点称为孤立结点( isolated vertex )。,4.1 图的基本概念,对于无向图G=,结点vV的度数等于联结它的边数,也记为d(v)。 注意:若v点有环,规定该点度因环而增加2。,4.1 图的基本概念,对于无向图G=, 记(G)或=maxd(v)|vV (G)或=mind(v)|vV 它们分别称为图G的最大度和最小度。,4.1 图的基本概念,例,4.1 图的基本概念,关于无向图中的结点的度,欧拉给出一个定理,这是图论中的第一个定理。 定理4.1.1 握手定理:图中结点度数的总
7、和等于边数的两倍.,一个图中有10个结点,每个结点的度数为6, 图中有多少条边?,?,结点度数总和:6 10=60 因为 2e = 60,所以 e = 30.,解:,4.1 图的基本概念,推论:在任何图中,度数为奇数的结点必定是偶数个.,下面哪些可以作为一个图的度数列 (或称为可图化的),?,V=v1, v2, , vn为无向图G的顶点集,称d(v1), d(v2), , d(vn)为G的度数列,4.1 图的基本概念,在任何有向图中,所有结点入度之和等于出度之和.,定理14.1.2,4.1 图的基本概念,证明:在有向图中每一条边对应一个入度和一个出度,为图的入度和出度各增加1。所以,所有结点入
8、度的和等于边数,所有结点出度的和也等于边数。,【例】 求解下列各题: (1)图G的度数列为2,2,3,5,6,则边数m为多少? (2)图G有12条边,度数为3的顶点有6个,余者度数均小于3,问G至少由几个顶点? (3) (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗?,4.1 图的基本概念,【例】证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.,4.1 图的基本概念,证:用反证法. 假设存在这样的多面体, 作无向图G=, 其中V=v | v为多面体的面, E=(u,v) | u,vV u与v有公共的棱 uv. 根据假设, |V|为奇数且vV, d(v)为奇数. 这与握手定
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 CH04 基本概念
链接地址:https://www.31doc.com/p-2281295.html