第七章 第一讲 无向图及有向图优秀PPT.ppt
《第七章 第一讲 无向图及有向图优秀PPT.ppt》由会员分享,可在线阅读,更多相关《第七章 第一讲 无向图及有向图优秀PPT.ppt(34页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第七章第七章 第一讲第一讲 无无向图及有向图向图及有向图现在学习的是第1页,共34页现在学习的是第2页,共34页第一讲第一讲 无向图及有向图无向图及有向图知识结构知识结构q图的定义图的定义q图的一些概念和规定图的一些概念和规定q简单图和多重图简单图和多重图q顶点的度数与握手定理顶点的度数与握手定理q图的同构图的同构q子图与补图子图与补图现在学习的是第3页,共34页 引例引例1 1:哥尼斯堡七桥哥尼斯堡七桥问题问题问题问题(图论应用的开始)(图论应用的开始)(图论应用的开始)(图论应用的开始)qq问:能否从某地出发,通过每桥恰好一次,走遍了七桥问:能否从某地出发,通过每桥恰好一次,走遍了七桥问:
2、能否从某地出发,通过每桥恰好一次,走遍了七桥问:能否从某地出发,通过每桥恰好一次,走遍了七桥 后又返回到原处?后又返回到原处?后又返回到原处?后又返回到原处?qq瑞士数学家瑞士数学家瑞士数学家瑞士数学家欧拉欧拉欧拉欧拉在在在在1736173617361736年发表了一篇论文讨论这个问题,指出这年发表了一篇论文讨论这个问题,指出这年发表了一篇论文讨论这个问题,指出这年发表了一篇论文讨论这个问题,指出这个问题无解。个问题无解。个问题无解。个问题无解。普雷格尔河现在学习的是第4页,共34页欧拉:传奇的一生欧拉:传奇的一生q年少时,听从父亲的安排,巴塞尔大学,学习神学和希伯来语,年少时,听从父亲的安排
3、,巴塞尔大学,学习神学和希伯来语,结果被约翰结果被约翰伯努利欣赏,伯努利欣赏,1717岁获得硕士学位之后,才开始专岁获得硕士学位之后,才开始专供数学。供数学。q为获得圣彼得堡科学院的医学部的职位空缺,的职位空缺,欧拉在巴塞尔便全力投入生理学的研究,并出席医学报告会。1727年,等他到等他到达俄罗斯时,叶卡捷琳娜一世女皇去世,他进入数学部。达俄罗斯时,叶卡捷琳娜一世女皇去世,他进入数学部。q1733年,欧拉回到瑞士,并结婚,一生共生育13个孩子,5个存活。q为了赢得巴黎奖金而投身于一个天文学问题,那是几个有影响的大数学家搞了几个月时间的,欧拉在三天之后把它解决了。可是过分的劳累使他得了一场病,病
4、中右眼失明了。q欧拉到底出了多少著作,直至1936年人们也没有确切的了解。但据估计,要出版已经搜集到的欧拉著作,将需用大4开本60至80卷。彼得堡学院为了整理他的著作整整花了47年。现在学习的是第5页,共34页问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题,问题,18571857年年):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市,能否个城市,能否从某个城市出发在十二面体上依次经过每个城市恰好从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点?一次最后回到出发点?哈密顿圈(环球旅行游戏)哈密顿圈(环球旅行游戏)现在学习的是第6页,共34页问题问
5、题3(3(四色问题四色问题):):对任何一张地图进行着色,两个共同边界的国对任何一张地图进行着色,两个共同边界的国家染不同的颜色,则只需要四种颜色就够了家染不同的颜色,则只需要四种颜色就够了.问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一一个工序才能开始个工序才能开始.即它们之间存在完成的先后次序即它们之间存在完成的先后次序关系关系,一般
6、认为这些关系是预知的一般认为这些关系是预知的,而且也能够预计而且也能够预计完成每个工序所需要的时间完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目间才能够完成整个工程项目,影响工程进度的要害工影响工程进度的要害工序是哪几个?序是哪几个?现在学习的是第7页,共34页二、图的概念二、图的概念二、图的概念二、图的概念 q设设A,B为任意的两个集合,为任意的两个集合,a,b|aAbB为为A与与B的的无序积无序积,记作,记作A&B。可将无序积中的无序对可将无序积中的无序对a,b记为记为(a,b),并且允许并且允许ab。
7、无论无论a,b是否相等,均有是否相等,均有(a,b)(b,a),故故A&BB&A。q元素可以重复出现的集合称为元素可以重复出现的集合称为多重集合多重集合或者或者多重集多重集。例如例如 多重集合多重集合a,a,b,b,b,c,d,(a,a),(b,b),(b,b).现在学习的是第8页,共34页定义定义定义定义1 1 一个一个无向图(无向图(无向图(无向图(undirected graphundirected graph)是一个有序的二元组是一个有序的二元组,记作记作记作记作G,其中其中(1 1)V V称为称为顶点集顶点集,其元素称为,其元素称为顶点顶点顶点顶点或或或或结点(结点(结点(结点(ve
8、rtices,nodes)。(2 2)E E称为称为边集边集,它是,它是无序积无序积V V&V的多重子集,其元素称的多重子集,其元素称为为无向边无向边,简称,简称边(边(edges)。例例例例1 1(1)(1)给定无向图给定无向图给定无向图给定无向图G,其中其中其中其中 V Vv1,v2,v3,v4,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).现在学习的是第9页,共34页例例1(2)E,定义定义2 一个一个有向图有向图(directed graph)是一个有序的二)是一个有序的二元组元组,记作记作D,其中其中(1)V
9、称为顶点集,其元素称为称为顶点集,其元素称为顶点顶点或或结点结点。(2)E为边集,它是笛卡儿积为边集,它是笛卡儿积VV的多重子集,其元素的多重子集,其元素称为称为有向边有向边,简称,简称边边。现在学习的是第10页,共34页图的一些概念和规定图的一些概念和规定图的一些概念和规定图的一些概念和规定qqG G表示无向图,但有时用表示无向图,但有时用G G泛指图泛指图泛指图泛指图(无向的或有向的无向的或有向的无向的或有向的无向的或有向的)。qqD D只能表示有向图。只能表示有向图。只能表示有向图。只能表示有向图。qqV V(G G),E E(G)分别表示分别表示G G的的顶点集顶点集和和边集边集边集边
10、集。qq若若若若|V V(G)|n n,则称则称则称则称G为为为为n阶图阶图。qq若若若若|V(G G)|与与|E E(G G)|均为有限数,则称均为有限数,则称均为有限数,则称均为有限数,则称G为为为为有限图有限图。q若边集若边集E(G),则称则称则称则称G为为零图零图零图零图,此时,又若,此时,又若G G为为n n阶图,阶图,则称则称G G为为为为n n阶零图阶零图阶零图阶零图,记作,记作,记作,记作N Nn n,特别地,称特别地,称特别地,称特别地,称N N1为为为为平凡图平凡图(trivial graph)。现在学习的是第11页,共34页关联与关联次数、环、孤立点关联与关联次数、环、孤
11、立点 qq设设设设G 为无向图,为无向图,为无向图,为无向图,e ek(vi i,vj)E,称称vi i,vj j为为e ek k的端点的端点,e ek k与与与与vi或或或或ek k与与v vj j是彼此相是彼此相关联关联的。的。的。的。若若v vi v vj,则称则称则称则称e ek k与与与与vi或或ek与与vj的的的的关联次数为关联次数为关联次数为关联次数为1 1。若若viv vj,则称则称ek与与与与v vi i的的的的关联次数为关联次数为关联次数为关联次数为2 2,并称,并称ek为为为为环环。任意的任意的任意的任意的v vl lV V,若若v vl l vi i且且vl lvj,则
12、称则称则称则称ek与与v vl l的的的的关联次数为关联次数为关联次数为关联次数为0 0。qq设设设设D D 为有向图,为有向图,e ek k E,称称称称vi i,v vj为为为为e ek的的的的端点。端点。端点。端点。若若若若vi iv vj j,则称则称则称则称e ek为为D中的中的中的中的环环。qq无论在无向图中还是在有向图中,无边关联的顶点均称为无论在无向图中还是在有向图中,无边关联的顶点均称为无论在无向图中还是在有向图中,无边关联的顶点均称为无论在无向图中还是在有向图中,无边关联的顶点均称为孤孤立点立点(isolated verticesisolated vertices)。现在学
13、习的是第12页,共34页相邻与邻接相邻与邻接 q设无向图设无向图G ,v vi,vjV,e ek k,el lE。若若若若 e et tE,使得使得使得使得e et t(vi i,v vj j),则称则称v vi i与与v vj j是是是是相邻的相邻的。若若ek与与与与el l至少有一个公共端点,则称至少有一个公共端点,则称e ek与与与与el l是是相邻的相邻的。设有向图设有向图D D,v vi,v vjV,ek k,e elE E。若若若若 e et tE,使得使得使得使得e et ,则称则称则称则称v vi为为et的的始点始点始点始点,vj j为为为为et t的的终点终点终点终点,并称,
14、并称v vi i邻接到邻接到v vj j,v vj邻接于邻接于vi。若若ek k的终点为的终点为的终点为的终点为el l的始点,则称的始点,则称e ek与与e el l相邻相邻(adjacent)。v vivj je ek ke elv vi ivjekel现在学习的是第13页,共34页简单图与多重图简单图与多重图 定义定义3 在无向图中,关联一对顶点的无向边如果多于在无向图中,关联一对顶点的无向边如果多于在无向图中,关联一对顶点的无向边如果多于在无向图中,关联一对顶点的无向边如果多于1 1条,则称这条,则称这条,则称这条,则称这些边为些边为些边为些边为平行边平行边,平行边的条数称为,平行边的
15、条数称为,平行边的条数称为,平行边的条数称为重数重数重数重数。在有向图中,关联一对顶点的有向边如果多于在有向图中,关联一对顶点的有向边如果多于1条,并且条,并且这些边的始点和终点相同这些边的始点和终点相同(也就是它们的方向相同也就是它们的方向相同),则,则称这些边为称这些边为平行边平行边平行边平行边(parallel edges)。含平行边的图称为。含平行边的图称为。含平行边的图称为。含平行边的图称为多重图多重图多重图多重图(multigraph)。既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图简单图简单图(simple graph)。例如:在图例如:在图例如:在图例如:
16、在图中中中中e e5 5与与与与e6是平行边,是平行边,不是简单图。不是简单图。现在学习的是第14页,共34页顶点的度数顶点的度数(degree)定义定义4 设设G为一无向图,为一无向图,vV,称称v作为边的作为边的端点次数之和为端点次数之和为v的度数的度数,简称为,简称为度度,记做,记做 dG(v)。在不发生混淆时,简记为在不发生混淆时,简记为d(v)。设设D为有向图,为有向图,vV,称称v作为边的始点次数之和为作为边的始点次数之和为v的出度的出度(out-degree),记做记做d+D(v),简记作简记作d+(v)。称称v作为边的终点次数之和为作为边的终点次数之和为v的入度的入度(in-d
17、egree),记做,记做 d-D(v),简记作简记作d-(v)。称称d+(v)+d-(v)为为v的的度数度数,记做,记做d(v)。现在学习的是第15页,共34页设设G G 为一个为一个为一个为一个n n阶无向图,阶无向图,V V v v1,v2,v vn n,称称称称d d(v1),d d(v2),d d(v vn)为为G的的的的度数列度数列。对于顶点标定的无向图,它的度数列是唯一的。对于顶点标定的无向图,它的度数列是唯一的。类似地,设类似地,设D D 为一个为一个为一个为一个n阶有向图,阶有向图,阶有向图,阶有向图,V V v v1,v v2 2,v vn n,称称称称d(v v1 1),d
18、(v v2),d d(vn n)为为为为D的的的的度数列度数列度数列度数列,另外称,另外称d+(v1 1),d d+(v2),d+(v vn)与与与与d-(v v1 1),d-(v v2),d-(vn n)分别为分别为D的的的的出度列出度列出度列出度列和和和和入度列入度列入度列入度列。度数列为度数列为4,4,2,1,34,4,2,1,3。度数列,出度数列,出度列,入度度列,入度列分别为列分别为5,3,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,2现在学习的是第16页,共34页图的度数的相关概念图的度数的相关概念qq在无向图在无向图在无向图在无向图G G中,中,中,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第七章 第一讲 无向图及有向图优秀PPT 第七 第一 优秀 PPT
限制150内