ImageVerifierCode 换一换
格式:PPT , 页数:26 ,大小:255.50KB ,
资源ID:353125      下载积分:120 文钱
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,省得不是一点点
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-353125.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: QQ登录   微博登录 

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(计算机数学基础(上)第3编图论.ppt)为本站会员(ga****84)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!

计算机数学基础(上)第3编图论.ppt

1、 计算机数学基础(上)第3编 图 论第六章 几种特殊的图本章主要内容:1.欧拉图2.哈密顿图3.平面图4.树重点:欧拉图、哈密顿图、平面图、欧拉公式、生成树难点:哈密顿图、平面图、最小生成树6.1 拉 和中 路欧 图 国邮 问题 一、欧拉图的定义在无向图中,从某一个结点出发,经过每边一次并且经过图中所有的结点(不一定一次)到达终点。如果终点与起点重合,则称为存在欧拉回路,如果终点与起点不重合,则称为存在欧拉通路。存在欧拉回路的图称为欧拉图。直观地说,一个无向图如果可以从一点出发,笔不离纸地一笔画出,就存在欧拉回路或欧拉通路,如果还能回到起点,就是欧拉图。二、欧拉图的判定1。无向连通图是欧拉图的

2、充分必要条件是图中不含有奇数度的结点。2001年1月选择题4。无向图G是欧拉图,当且仅当 。A) G中所有的结点的度数全为偶数B) G中所有的结点的度数全为奇数C) G连通且所有的结点的度数全为偶数D) G连通且所有的结点的度数全为偶数C2000年1月化简解答题14(1)。设G是无向图如右(彼得森图),说明G不是欧拉图。解:因为无向图G中所有的结点的度数全为奇数,所以G不是欧拉图。2。无向连通图存在欧拉通路的充分必要条件是图中只有两个奇数度的结点。3。当n为奇数时,完全无向图Kn是欧拉图。例如,K3、K5等。4。当n为偶数时,完全无向图Kn不是欧拉图,也不存在欧拉通路。2001年7月化简解答题

3、13。试问n为何 时,无向完全图Kn存在一条欧拉回路 解:因为无向连通图存在欧拉回路的充分必要条件是图中不含有奇数度结点。所以,无向完全图Kn的结点度数 为偶数, n-1为偶数,则n为奇数。、中国邮路问题邮 从邮 出发, 所有的 一次(可以重 ),最 回到邮 。要 的路 全最 , 一问题就称为中国邮路问题。中国邮路问题可以 化成图的问题 解。以 为边, 的 度为边的 ,以邮 的 点为结点,得到 图G。如G中不含有奇数度结点,则G是欧拉图。以邮 为起点的欧拉回路就是问题的解。如G中含有奇数度结点,则可在 奇数度结点的边,currency1有的某边成为边,并且的边的 数“ 最小。 一 G的结点就成

4、为偶数度的结点,G就成欧拉图,从fi出问题的解。因fl,fi中国邮路问题的解就是在G中一边,图中所有的结点的度数 成偶数。fi的边的 数“ 最小的。6.2 哈密 和 担顿图 问题一、哈密顿图的定义从图中的某一结点出发,如果存在一条只经过每个结点一次(不必经过所有的边)的通路,则fl通路称为哈密顿通路。如果还能回到起点,则称为哈密顿回路。存在哈密顿回路的图称为哈密顿图。哈密顿图不仅可以是无向图,也可以是有向图。 ,连通图一定不是哈密顿图。哈密顿通路与欧拉通路的 是:欧拉通路是经过每一边一次且仅一次,可以经过某结点次的通路,哈密顿通路是经过每一结点一次且仅一次,可以不经过某边的通路。二、哈密顿图的判定1。在哈密顿图G中”结点V1 ,GV1的连通分 数 。不 一条件的图一定不是哈密顿图。2。如果无向简图G中何一结点的度数“等结点数,则G中存在一条哈密顿回路。2001年1月题9设图G=是简图, 图中每结点的度数“ ,则G一定是哈密顿图。3。有n个结点的有向图D中边的向 ,如果中含图Kn,则D中存在哈密顿通路,当n3时,则D中存在哈密顿回路。|)( 11 VVGP |V6.3 平面 的着色图与图一、平面图的定义如果无向图G的所有结点 所有的边(可 )画在平面 ,何两条边 有 点,则称G为平面图。 则,称为平面图。例如K4 可画为 是平面图。

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。