![离散数学--第8章+图论-7ppt课件_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-1/31/54ccd7d7-33be-4c98-bc8b-9a2177c455f2/54ccd7d7-33be-4c98-bc8b-9a2177c455f21.gif)
![离散数学--第8章+图论-7ppt课件_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-1/31/54ccd7d7-33be-4c98-bc8b-9a2177c455f2/54ccd7d7-33be-4c98-bc8b-9a2177c455f22.gif)
![离散数学--第8章+图论-7ppt课件_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-1/31/54ccd7d7-33be-4c98-bc8b-9a2177c455f2/54ccd7d7-33be-4c98-bc8b-9a2177c455f23.gif)
![离散数学--第8章+图论-7ppt课件_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-1/31/54ccd7d7-33be-4c98-bc8b-9a2177c455f2/54ccd7d7-33be-4c98-bc8b-9a2177c455f24.gif)
![离散数学--第8章+图论-7ppt课件_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-1/31/54ccd7d7-33be-4c98-bc8b-9a2177c455f2/54ccd7d7-33be-4c98-bc8b-9a2177c455f25.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1返回 结束第八章 图论-22返回 结束v一、欧拉Euler回路转化 Euler1736年 3返回 结束v判别定理:无向图G是欧拉图当且仅当G是连通图,且G中没有奇度顶点。 (充要条件)v证明反证法):v 设C=(e1=(v0,v1),e2=(v1,v2),em=(vm-1 ,v0)是图中最大的回路。v 假设C不是Euler回路。则图G如下图所示:CC或4返回 结束 图是连通的,则顶点不可能出现下面的情况:C图中任意结点的度均为偶数,有如下所示:C与假设矛盾, C是Euler回路。C5返回 结束v推论:如果连通图G只有两个度为奇数的顶点,则存在以这两个顶点为两端点,且包含G所有边的Euler道
2、路。v补充:连通有向图存在Euler回路的充要条件是:每个顶点的入度出度。6返回 结束v欧拉回路求解方法v(Fleurys algorithm ):v(1)可从任一点出发去掉连接此点的一边。 v(2)依序去掉相连的边但必须注意下列两条件: v a、如果某边去掉后会导致某点无连通的 边,则此顶点亦可去。 v b、去某边后不能造成图形的不连通。7返回 结束例1-1:如果可能求出下图的一条Euler回路。v1v2v5v3v4v6v7v8v98返回 结束解:首先看图中是否有Euler回路,即看每个顶点的度是否都是偶数。 d(V1)=2, d(V2)=4, d(V3)=2, d(V4)=4, d(V5)
3、=4, d(V6)=4, d(V7)=2, d(V8)=2, d(V9)=4。 所以存在Euler回路。 可以任意一个顶点为起点,这里以v2为起点:v1v2v5v3v4v6v7v8v99返回 结束依序去掉相连的边但必须注意下列两条件: a、如果某边去掉后会导致某点无连通的边,则此顶点亦可去也。 b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v910返回 结束(1)先去掉(v2,v4)依序去掉相连的边但必须注意下列两条件: a、如果某边去掉后会导致某点无连通的 边,则此顶点亦可去。 b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v9111返回 结束v(2)
4、接着去掉(v4,v3)v依序去掉相连的边但必须注意下列两条件: v a、如果某边去掉后会导致某点无连通的 边,则此顶点亦可去。 v b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v91212返回 结束v(3)接着去掉(v3,v2)v依序去掉相连的边但必须注意下列两条件: v a、如果某边去掉后会导致某点无连通的v 边,则此顶点亦可去。 v b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v912313返回 结束vv依序去掉相连的边但必须注意下列两条件: v a、如果某边去掉后会导致某点无连通的 v 边,则此顶点亦可去。 v b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v912314返回 结束v依序去掉相连的边但必须注意下列两条件: v a、如果某边去掉后会导致某点无连通的 边,则此顶点亦可去。 v b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v912345678这时,如果去掉(v6,v5)将导致图不连通15返回 结束v1v2v5v3v4v6v7v8v91234567891011121
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 在办公室实习报告4篇
- 范文新学期学习计划模板合集八篇
- 个人宅基地使用权转让协议(标准版)
- 南京劳务合同范本
- 募集资金协议书范本
- 末上市公司的联权质押合同模板
- 广东省汕头市名校2025届下学期初三第二次月考生物试题理试题含解析
- 绿色简约中国脑健康日模板
- 广东省汕头市潮阳区达标名校2025届初三五校联谊期中考试试卷数学试题含解析
- 广东省梅州五华县联考2025届初三第一次模拟(适应性测试)考试物理试题试卷含解析
- 学前教育政策法规全套教学课件
- 起重机械安装修理程序文件汇编2022版
- 社区书记工作室计划书
- 第1课中华文明的起源与早期国家的形成【中职专用】《中国历史》(高教版2023基础模块)
- 小学教育课件教案学习酸碱指示剂的制备方法
- 《链球菌属》课件
- 《中职就业指导》全套课件(共6章)
- (完整文本版)新概念英语第一册单词表默写版1-144
- 案件研判室管理制度
- 人教版初中数学新教材详细目录
- 干细胞临床研究质量管理手册
评论
0/150
提交评论