离散数学6——8章ppt.ppt
《离散数学6——8章ppt.ppt》由会员分享,可在线阅读,更多相关《离散数学6——8章ppt.ppt(148页珍藏版)》请在三一文库上搜索。
1、图论简介,图论是一个古老的数学分支,它起源于游戏难题的研究。图论的内容十分丰富,应用得相当广泛,许多学科,诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等,都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展,图论在以上各学科中的作用越来越大,同时图论本身也得到了充分的发展。,第八章 图论,第一节 图的基本概念,内容:有向图,无向图的基本概念。,重点:1、有向图,无向图的定义,,内容:有向图,无向图的基本概念。,5、图的同构的定义。,2、图的表示法。,有向图,无向图的顶点都用小圆圈表示。,图形表示如右:,图形表示如右:,3、相关概念。,
2、3、相关概念。,(2),3、相关概念。,(2),孤立点无边关联的点。,3、相关概念。,多重图含有平行边的图。,简单图不含平行边和环的图。,如例1的(1)中,,为孤立点,,为悬挂点,,为悬挂边,,为环,,为平行边,重数2,,为多重图。,4、完全图,例如:,二、顶点的度数,握手定理。,1、顶点的度数 (简称度)。,二、顶点的度数,握手定理。,1、顶点的度数 (简称度)。,最大度,最小度,如例1的(2)中,,,,。,2、握手定理。,定理1:,定理2:,三、子图,补图。,1、子图定义:,三、子图,补图。,导出子图,例3、,上图中,(1)(6)都是(1)的子图,,其中(2)(6)为真子图,,(1)(5)
3、为生成子图。,2、补图定义。,如例3中,,四、图的同构。,定义:,例4、,解:只有如下3个图:,解:只有如下4个图:,第二节 路径和回路(1),内容:图的通路,回路,连通性。,2、图的连通性的概念,,3、短程线,距离的概念。,一、路径,回路。,1、路径 (回路),一、路径,回路。,2、简单路径,简单回路。,简单路径 (迹):同一条边不出现两次 基本路径(链):同一顶点不出现两次,简单回路 (闭迹):没有相同边的回路 基本回路:通过各顶点不超过一次的回路,一、路径,回路。,例1、(1),长度3,长度6,长度6,例1、(1),基本路径,简单路径,复杂通路,例1、(2),长度3,长度4,长度7,例1
4、、(2),基本回路(圈),基本回路(圈),复杂回路,4、性质。,定理1:,4、性质。,定理2:,二、图的连通度。,1、连通,可达。,2、短程线,距离。,距离短程线的长度,,3、无向图的连通。,3、无向图的连通。,4、有向图的连通。,例2、,强连通,单向连通,例2、,单向连通,弱连通,非连通图,8.2 路径与回路(2),内容:欧拉、哈密尔顿路径、赋权图中的最短路径。,重点:1、欧拉图的定义,无向图是否具有 欧拉回路的判定,了解:无向图是否具有哈密尔顿回路的判定。,一、欧拉回路问题的提出。,1736年,瑞士数学家欧拉,哥尼斯堡七桥问题,二、定义。,欧拉通路 (欧拉迹),欧拉回路 (欧拉闭迹),欧拉
5、图,存在欧拉回路的图。,注意:,(1) 欧拉通路与欧拉回路不同。,(2) 欧拉图指具有欧拉回路(并非通路)的图。,(3) 欧拉通路(回路)必是简单通路(回路)。,(4) 连通是具有欧拉通路(回路)的必要条件。,三、无向图是否具有欧拉通路或回路的判定。,例1、以下图形能否一笔画成?,例1、以下图形能否一笔画成?,例2、两只蚂蚁比赛问题。,四、有向图是否具有欧拉通路或回路的判定。,例3、判断以下有向图是否欧拉图。,二、哈密尔顿图,一、问题的提出。,1859年,英国数学家哈密尔顿,周游世界游戏。,二、哈密尔顿图。,哈密尔顿通路,哈密尔顿回路,哈密尔顿图,存在哈密尔顿回路的图。,注意:,(1) 哈密尔
6、顿通路与哈密尔顿回路不同。,(3) 哈密尔顿通路(回路)必是初级通路(回路)。,(4) 连通是具有哈密尔顿通路(回路)的必要条件。,注意:,三、判定。,采用尝试的办法。,例1、判断下图是否具有哈密尔顿回路,通路。,例1、判断下图是否具有哈密尔顿回路,通路。,例1、判断下图是否具有哈密尔顿回路,通路。,哈密尔顿回路存在的两件个充分条件,定理8.2-13 设 是具有 个顶点的简单无向图,若在G中每一对顶点的次数之和大于n,则在G中存在一条哈密尔顿回路。,推论8.2-13 在简单无向图中,若每一顶点的次数 则在G中存在一条哈密尔顿回路。,70,三、最短路径,定义 设G=(V,E)是无向简单图,如果对
7、E中每条边e都有一个实数w(e)附着其上,则称G为权图,称w(e)为边e的权。设P是G的一条路,P上所带权的总和称为路P的权。有时记为G=(V,E,W),71,设权图G中每条边的权均大于等于0,u,v为G中任意的两个顶点,从u到v的所有路中权最小的路称为u到v的最短路径,求给定的两顶点之间的最短路径问题称为最短路径问题。,最短路径算法:由E.W.Dijkstra(迪克斯特拉)于1959年给出的标号法(Dijkstra算法)。,三、最短路径,72,问题:图G=(V,E,W),1V,求1到V其它点的最短距离。 设S为最短距离已经确定的集合,T为最短距离未确定的集合。 算法描述如下: (1) 初始话
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 ppt
链接地址:https://www.31doc.com/p-2281292.html