版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1返回 结束第七章 图论-1引言引言7.1 图的基本概念图的基本概念7.2 路与连通路与连通7.3 图的矩阵表示图的矩阵表示7.4 最短路径问题最短路径问题7.5 图的匹配图的匹配8.1 Euler图和图和Hamilton图图8.2 树树8.3 生成树生成树 8.4 平面图平面图2返回 结束7.2 路与连通 内容:图的通路,回路,连通性。内容:图的通路,回路,连通性。 重点:重点:1、通路,回路,简单通路,回路、通路,回路,简单通路,回路,初级通路,回路的初级通路,回路的定义定义2、图的连通性的概念、图的连通性的概念3、短程线,距离的概念。、短程线,距离的概念。3返回 结束7.2.1 路1、路
2、 (回路)中顶点和边的交替序列G0 1 1 2llv e v ee v ,其中1(,)iiievv(无向图),或1,iiievv(有向图),始点,0v终点,称为到lv0vlv的路。当0lvv时, 为回路。1v2v3v4v5v1e2e3e4e5e6eG1 1253443562v e v e v e v e v e v125344352v e v e v e v e v4返回 结束7.2.1 路2.简单通路、简单回路 边不同简单通路简单通路 ( (迹迹) ):路中所有的边都不同:路中所有的边都不同简单回路简单回路 ( (闭迹闭迹) ):回路中所有的边都不同:回路中所有的边都不同复杂通路复杂通路 (
3、 (回路回路) ):路回路中有重复的边出现:路回路中有重复的边出现5返回 结束7.2.1 路3.初级通路、初级回路 初级根本通路,初级回路:点不同初级通路初级通路 ( (途径途径) ):路中所有的顶点互不相同:路中所有的顶点互不相同初级回路初级回路 ( (圈圈) ):回路中所有的顶点互不相同:回路中所有的顶点互不相同初级通路 (回路)简单通路 (回路),但反之不真。4、路,回路的长度中边的数目。6返回 结束7.2.1 路例例1、(1)例例1 1、(1)(1)图(1)中,从的路有:到1v6v11 1 2 5 5 76v e v e v e v 21 1 22 3 3 442 5 5 76v e
4、v e v e v e v e v e v 31 1 2 5 5 64 42 5 5 76v ev e v e v e v e v e v 长度3长度6长度67返回 结束7.2.1 路例例1、(1)图(1)中,从的通路有:到1v6v11 1 2 5 5 76v e v e v e v 21 1 22 3 3 442 5 5 76v e v e v e v e v e v e v 31 1 2 5 5 64 42 5 5 76v ev e v e v e v e v e v 初级通路简单通路复杂通路8返回 结束7.2.1 路例例1、(2)1244 3 3 22v e v e v e v 22 5
5、 5 64 3 3 22v e v e v e v e v 3243243256325432vvvvvvveeeveeee 长度3长度4长度7图(2)中过)有:的回路 (从2v2v到2v9返回 结束7.2.1 路例例1、(2)1244 3 3 22v e v e v e v 22 5 5 64 3 3 22v e v e v e v e v 3244 3 3 22 5 5 64 3 3 22v e v e v e v e v e v e v e v 初级回路(圈)初级回路(圈)复杂回路图(2)中过)有:的回路 (从2v2v到2v10返回 结束7.2.1 路5、图中最短的回路如图: 无向图中,环
6、构成的回路长为无向图中,环构成的回路长为1 1 ,两平行边构成的回路长为,两平行边构成的回路长为2 2。 有向图中,环构成的回路长为有向图中,环构成的回路长为1 1,两条方向相反的边构成的回路,两条方向相反的边构成的回路长为长为2 2。11返回 结束7.2.1 路6、性质定理:定理:阶图中,若从顶点nivjv到存在路()ijvv,则从ivjv到存在长度小于等于在一个的路。1n推论:推论:阶图中,若从顶点nivjv到存在通路()ijvv,则从ivjv到存在长度小于等于在一个的初级通路。1n证明思路:多于证明思路:多于n-1n-1条边的路中必有重复出现的结点,反条边的路中必有重复出现的结点,反复删
7、去夹在两个重复结点之间的边之后,剩余的边数不会复删去夹在两个重复结点之间的边之后,剩余的边数不会超过超过n-1n-1条边。条边。 12返回 结束7.2.1 路6、性质定理:定理:阶图中,假设niv到自身存在回路,则从到自身存在长度小于等于ivn的回路。在一个推论:推论:阶图中,假设niv到自身存在一个简单回路,则从 到自身存在长度小于等于ivn的初级回路。在一个由以上定理可知,在阶图中,n任何一条初级通路的长度任何一条初级回路的长度1nn13返回 结束7.2.2 图的连通性7.2.2 图的连通性1、连通,可达。无向图中,从 到存在路,称ivjv到ivjv是 连通的连通的( (双向双向) )。有
8、向图中,从 到存在路,称ivjv可达可达ivjv(注意方向)。2、短程线,间隔。短程线连通或可达的两点间长度最短的 路。间隔短程线的长度,记,ijd v v( ,)ijd v v无向图有向图14返回 结束7.2.2 图的连通性2、短程线,间隔假设之间无路(或不可达),规定,ijv v( ,),ijijd v vd v v 间隔满足:,ijd v v(1),时,等号成立。 ,0ijd v vijvv(2),ijjkikd v vd v vd v v若是无向图,还具有对称性,( ,)(,)ijjid v vd v v。15返回 结束7.2.2 图的连通性3、无向图的连通。为连通图为连通图是平凡图,
9、或都是连通的。GGG中任两点为非连通图为非连通图G中至少有两点不连通。G例 1G3G2G1v2v3v4v4u1u2u3u 这里 是连通图, 是非连通图,仅有一个顶点的图 我们也把它看成是连通图。 1G2G3G16返回 结束7.2.2 图的连通性3、无向图的连通2G1v2v3v4v4u1u2u3u1v2v3v4v4u1u2u3u 连通图可以看成是只有一个连通分支的图,即 。( )1w G 17返回 结束7.2.2 图的连通性4、有向图的连通G中任一对顶点都互相可达 (双向)中任一对顶点至少一向可达略去 中有向边的方向后 得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通强连通单向连通G
10、G18返回 结束7.2.2 图的连通性例例2单向连通弱连通非连通图19返回 结束7.2.2 图的连通性5 图与顶点之间的若干关系图与顶点之间的若干关系 把度数为把度数为1的顶点称为悬挂点(的顶点称为悬挂点( pendant nodes)各顶点的度均相同的图称为正则图各顶点的度均相同的图称为正则图(regular graph),各顶点度均为各顶点度均为k的正则图称为的正则图称为k-正则正则图。图。删除结点:所谓在图中删除结点删除结点:所谓在图中删除结点v,即是把,即是把v以以及与及与v关联的边都删除。关联的边都删除。删除边:所谓在图中删除某条边,即是把该边删除边:所谓在图中删除某条边,即是把该边
11、删除。删除。 见见P-282页的图页的图7-2.2和图和图7-2.3。20返回 结束7.2.3 图的连通度定义定义7-2.4 设无向图设无向图G =是连通图是连通图,若有结点集若有结点集V1V,使图使图 G中删除了中删除了V1的所有结点后的所有结点后,所得到的子图是不连通所得到的子图是不连通图图,而删除了而删除了V1的任何真子集后的任何真子集后,所得到的子图仍是连通所得到的子图仍是连通图图,则称则称V1是是G的一个点割集的一个点割集(cut-set of nodes) 。k(G)=min|V1| 是是G的点割集的点割集 称为图称为图G的点连通度的点连通度(node-connectivity)
12、。v5v1v2v4v5v1v4点割集点割集V1=v2V1=v221返回 结束7.2.3 图的连通度定义定义7-2.5 设无向图设无向图G =是连通图是连通图,若有边集若有边集E1E,使图使图 G中删除了中删除了E1的所有边后,所得到的子图是不连通的所有边后,所得到的子图是不连通图,而删除了图,而删除了E1的任何真子集后,所得到的子图仍是连的任何真子集后,所得到的子图仍是连通图,则称通图,则称E1是是G的一个边割集的一个边割集(cut-set of edges) 。若。若某一条边就构成一个边割集,则称该边为割边或桥。某一条边就构成一个边割集,则称该边为割边或桥。 割边割边e使图使图G满足满足W(
13、G-e)W(G) 。边连通度边连通度(edge-connectivity) (G)定义:非平凡图的边定义:非平凡图的边连通度为连通度为 (G)=min |E1| | E1是是G的边割集的边割集 边连通度边连通度 (G)是为了产生一个不连通图需要删去的边是为了产生一个不连通图需要删去的边的最少数目。对平凡图的最少数目。对平凡图G可以定义可以定义 (G)=0,一个不连,一个不连通图也有通图也有 (G)=022返回 结束7.2.4 二分图v例:人员分配问题,某公司分配 个工人做 件工作。代表人的一组顶点用 表示,代表工作的一组顶点 用表示 。 与 相邻当且仅当工人 能做工作 ,从而 之间(Y 之间)
14、无边。所得图称为二分图 。nmnxxxX,2112,mYy yyXjyixixjy 一、一、 二分图定义二分图定义 定义定义1: 的二分划的二分划 ,即,即使使 的每条边的两个端点一个在的每条边的两个端点一个在 中,另一个在中,另一个在 中。则称中。则称 是二是二分图或偶图,分图或偶图, 称为称为 的二分划,记为的二分划,记为 。VYXYXGVYX,),(GYX ,G);,(EYXG XYYX ,G23返回 结束7.2.4 二分图我们可以验证下面三条成立YX和)(GVXYXGYGG (1) 是的一个划分; (2) 和; (3)和均为空图。由以上三条可知,为二分图。24返回 结束7.2.4 二分
15、图123 ,Xv v v123, ,Yu u u1v2v3v1u2u3u图 是二分图当且仅当存在顶点集合的二分划 ,使 为空图; 当且仅当 不含长为奇数的回路; 当且仅当 的所有非平凡子图是二分图。 GYX ,YGXGGG例: 1v2v3v1u2u3u 的一个回路为假设 ,那么 类似有所以而 ,故 是偶数。G34,uX uY1uX212,lluX uYkuY122u uEuY121kCu uu uk利用第二个等价刻画即可。25返回 结束7.2.4 二分图定理定理7.2.1 非平凡图非平凡图 是二分图当且仅当是二分图当且仅当 中中不含长为奇数的回路。不含长为奇数的回路。GG证明必要性是明显的。证
16、明必要性是明显的。充分性:不妨设充分性:不妨设G中每一对顶点之间有路连接否则中每一对顶点之间有路连接否则只需考虑只需考虑G的每个每一对顶点之间有路连接的极大子的每个每一对顶点之间有路连接的极大子图)。任取图)。任取G的一个顶点的一个顶点u,由,由G的假设,对的假设,对G的每个顶的每个顶点点v,在,在G中存在中存在u-v路。现利用路。现利用u对对G的顶点进行分类。的顶点进行分类。设设V1v|vV(G),G中存在一条长度为偶数的中存在一条长度为偶数的u-v路路V2v|vV(G),G中存在一条长度为奇数的中存在一条长度为奇数的u-v路路显然显然uV1。由于图。由于图G中不存在长度为奇数的圈,所以对中不存在长
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 煤矿机电设备管理系统技术方案
- 绩效发展咨询服务
- 展会服务合同范本在线看
- 拼花地板购销合同样本
- 个人工作承诺
- 社区安宁餐饮业静音承诺
- 马戏团表演安全保障服务协议
- 终止协议合同的操作
- 版评审表采购合同
- 机电工程招标文件解读与指导
- 黑龙江省龙东地区2025届英语九上期末监测模拟试题含解析
- 2024年人教版小学三年级科学(上册)期末试卷及答案
- 公共广播系统施工与方案
- 2024年个人信用报告(个人简版)样本(带水印-可编辑)
- 硒鼓回收处理方案
- 书法创作与欣赏智慧树知到期末考试答案章节答案2024年华侨大学
- 经典导读与欣赏-知到答案、智慧树答案
- 悉尼歌剧院-建筑技术分析
- 肺结核病防治知识宣传培训
- 三切口食管癌手术步骤
- 食品安全与卫生智慧树知到期末考试答案2024年
评论
0/150
提交评论