![7.3-图-论(2)(部编)课件_第1页](http://file4.renrendoc.com/view14/M04/22/11/wKhkGWaDkPWAHKCdAACBdtsy_oU299.jpg)
![7.3-图-论(2)(部编)课件_第2页](http://file4.renrendoc.com/view14/M04/22/11/wKhkGWaDkPWAHKCdAACBdtsy_oU2992.jpg)
![7.3-图-论(2)(部编)课件_第3页](http://file4.renrendoc.com/view14/M04/22/11/wKhkGWaDkPWAHKCdAACBdtsy_oU2993.jpg)
![7.3-图-论(2)(部编)课件_第4页](http://file4.renrendoc.com/view14/M04/22/11/wKhkGWaDkPWAHKCdAACBdtsy_oU2994.jpg)
![7.3-图-论(2)(部编)课件_第5页](http://file4.renrendoc.com/view14/M04/22/11/wKhkGWaDkPWAHKCdAACBdtsy_oU2995.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
几种特殊的图
欧拉图哈密顿图平面图树17.3.4欧拉图一笔画问题:欧拉通路或欧拉回路。定义7.1.5
在无向连通简单图中,通过图中每边一次且仅一次并行遍每个结点的一条通路(回路),称为该图的一条欧拉通路(回路)。存在欧拉回路的图称为欧拉图。无欧拉通路或欧拉回路欧拉通路欧拉回路2定理7.3
无向连通图G是欧拉图的充分必要条件是G不含奇数度结点。推论非平凡连通图G含有欧拉通路的充分必要条件是G最多有两个奇数度结点。例下列图是否可以一笔画出来.AB×√√3例1验证哥尼斯堡七桥问题无解.解七桥问题图7-7可简化为图7-20.从图7-20知,此图为无向连通图,并且每个结点度数为奇数,由定理7.3,此图不是欧拉图,即知哥尼斯堡七桥问题无解.4定理连通有向图G含有欧拉回路的充分必要条件是G中每个结点的入度等于出度;连通有向图G含有欧拉通路的充分必要条件是除两个结点外,其余每个结点的入度等于出度,这两个结点中一个结点的入度比其出度多1,另一个结点的入度比其出度少1。57.3.5哈密顿图定义7.1.6经过图中每个结点一次且仅一次的通路(回路),称为哈密顿通路(回路)。存在哈密顿回路的图称为哈密顿图。哈密顿图哈密顿图无哈密顿通路存在哈密顿通路6例举出满足下列条件具有6个点的图。⑴无哈密顿回路,无欧拉路。⑵有哈密顿回路,无欧拉路。⑶无哈密顿回路,有欧拉路。⑷有哈密顿回路,有欧拉路。⑴⑵⑶⑷7讨论题判断各图是否为哈密顿图,并说明原因,若是哈密顿图,请画出哈密顿回路。×××√√8√√××9(补充)平面图在印刷电路版等方面有应用.定义3
设无向图G=<V,E>,如果能够把G的所有结点和边画在平面上,使得任何两边除公共结点外没有其它交叉点,则称G为可嵌入平面图,或称G是可平面图,可平面图在平面上的一个嵌入称为平面图。否则称G为非平面图。有些图虽然有相交的边,如果经改画后可以不相交,这样的图仍是平面图。10例G可改画为所以G是平面图。二个典型的非平面图.K5K3,311定理
平面图中,所有面的次数之和是其边数的两倍。定理(欧拉公式)设连通平面图G=<V,E>,共有v个结点,e条边和r个面,则有
v-e+r=2.127.3.6树
在计算机科学中树是一种经常使用的数据结构.定义7.1.7
连通且无回路的无向图称为树,用T表示。T中d(v)=1的结点v称为树叶。T中d(v)>1的结点称为分支点或内点。每个连通分图是树的无向图称为森林。一个孤立结点称为平凡树。13树树叶分枝点非树森林非树树树14定理
给定图T=<V,E>,以下关于树的定义是等价的(|V|=n,|E|=m):⑴无回路的连通图;⑵无回路且m=n-1;⑶连通且m=n-1;⑷无回路,但增加一条新边,得到一个且仅一个回路;⑸连通但删去任一边后,就不连通了;⑹每一对结点有一条且仅一条通路。15定理7.4
任何非平凡树至少有两片树叶。证:2m=deg(vi)≥k+2(n-k)=2n-k
i设有k个一度结点其余n-k个结点的度≥2∵m=n-1,∴2(n-1)≥2n-k ∴k≥2 ■16生成树及其应用定义若图G的生成子图(含图G所有结点的子图)是树,则称这棵树为G的生成树。图G的一棵生成树为T。e1e2e3e4e5e6e7e8e9e10Ge1e2e3e6e8e9T17定理7.5
连通图G至少有一棵生成树。G只要删边去回路→连通无回路。GT1T2T318
若连通图G有n个结点,m条边,要确定G的一棵生成树,必须删去G的m-(n-1)条边。定义
在图G的所有生成树中,带权最小的那棵树称为最小生成树。19求最小生成树的克鲁斯克尔算法:
1.在G中选取最小权的边ei,置i=1;
2.当i=n-1时结束,否则转3;
3.设已选择边为T={e1,e2,...,ei},在E-T中选取ei+1,使T
ei+1无回路,且ei+1具有最小的权;
4.置i=i+1,转2。22223311红线组成最小生成树T,w(T)=6.20根树定义
一个有向图,如果删去每条边的方向所得到的无向图是一棵树,则称这个有向图为有向树。定义
一棵非平凡的有向树,如果恰有一个结点的入度为有向树0,其余所有结点的入度均为1,则称这棵有向树为根树。入度为0的结点称为树根,出度为0的结点称为树叶,出度不为0的结点称为内点,内点同树根统称为分支点。v1v2v3v4v5v6v7v8v9v10v11v12v1321习惯上有向边方向均指向下方,一般可省去全部箭头,上图可画成:在根树中从树根到任意结点的长度,称为该结点的层数,所有结点中最大的层数称为根树的树高。定义
在根树中若vi可达vj
且通路长度≥2,则称vi是vj的祖先,vj是vi的后代。若<vi,vj>是根树的边,则称vi是vj的父亲,vj是vi的儿子,同一结点的儿
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 服装缝纫工初级理论知识试卷
- 运动场馆灯具产品相关项目建议书
- 贵州省铜仁地区沿河土家族自治县2024年六年级数学小升初摸底考试含解析
- 贵州省黔西县市级名校2024-2025学年初三下学期期中语文试题理试卷含解析
- 《物联网控制技术》-彭力 控制系统仿真实验手册 实验1-7 采样与保持仿真实验-振铃的消除仿真实验
- 贵州省黔南州名校2024届七年级英语第二学期期末经典试题含答案
- 药具库房管理和养护
- 开闭幕词之太阳能开业开幕词
- DB3707T 123-2024 地理标志产品 昌邑梭子蟹
- 福寿螺防控专项行动方案
- 中级职称(建筑结构设计专业)工作总结
- 高职国际英语1-Unit-1-People
- 《品质》课件23张 2024年高教版(2023)中职语文职业模块
- 五官科疾病健康宣教
- 公共机构能源分析报告
- 潜水员潜水作业安全
- 脑出血科普知识宣教
- 新教材人教版高中英语选择性必修第二册全册书重点单词短语总结(2022新高考一轮复习资料)
- 让学习真实发生-《学习共同体-走向深度学习》学习体会
- 小儿急性上呼吸道感染的护理查房
- 【语文】辽宁省大连市甘井子区2023-2024学年七年级上学期期中考试试题(解析版)
评论
0/150
提交评论