第五部分图论GraphTheory教学课件.ppt
《第五部分图论GraphTheory教学课件.ppt》由会员分享,可在线阅读,更多相关《第五部分图论GraphTheory教学课件.ppt(75页珍藏版)》请在三一文库上搜索。
1、1,第五章 图 论 (Graph Theory),2,Konigsberg(柯尼斯堡)七桥问题,能否从河岸或小岛出发,恰好通过每一座桥一次再回到出发地?,图论的起源,3,瑞士数学家Euler(欧拉)于1736年从理论上圆满解决这个问题。,欧拉引进了图论,A,D,B,C,抽象,4,1736年 欧拉解决柯尼斯堡七桥问题图论产生 1936 年图论第一部专著出现有界图和无界图的理论 经过近六十多年的发展,逐渐成为一门相对独立的学科。,图论发展过程,5,图论的应用,网络技术的理论基础和重要的研究工具 生物和化学:区别分子式相同但结构不同的两种化合物。 计算机和通信:用于通信网络和计算机网络的设计,交通网
2、络的合理分布 大型工程项目的计划管理。,6,图的基本概念 1,图(graph):由结点(顶点)(vertex)和连接结点的边所构成的图形. V(G)表示图G的结点集 E(G)表示图G的边集。 图G可记为或 有n个顶点和m条边的图记为(n,m)图或称为n阶图。,7,注意:图论中研究的图只关心图的结点之间是否有边相连,不关心结点的位置和边的长短,8,图的基本概念 2(1),边(edge) 有向边(directed edge) 无向边(indirected edge) 平行边(parallel edge ) 自回路(环)(Self-loop / Ring),9,图的基本概念 2(2),边(edge)
3、 有向边(directed edge) 端点有始点和终点之分的边。 用有序二元组表示 无向边(indirected edge) 边的两个端点都可以作始点和终点的边 端点为v1和v2的无向边表示为 (v1, v2) 或v1v2,10,图的基本概念 2(2),边(edge) 平行边(parallel edge ) 两结点之间的多条无向边或 多条方向相同的有向边称为平行边。 两个端点a和b之间平行边的条数 称为边(a,b)(或)的重数 自回路(环)(Self-loop / Ring) 两个端点重合的无向(有向)边。,v1,a,b,11,图的基本概念 3,边与结点的关系 设边e的端点为a和b 边e关联
4、(incident)于顶点a和b(或a和b关联边e) a、b是邻接(相邻)的(adjacent),12,根据图中边的类型可将图分为: 无向图(undirected graph) 有向图(directed graph) 混合图(mixed graph) 多重图(multiple graph) 简单图(simple graph),图的基本类型(1),13,图的基本类型(2),无向图(undirected graph):所有边都是无向边的图。 有向图(directed graph):所有边都是有向边的图。 混合图:既有有向边又有无向边的图。,(c),14,图的基本分类(2),多重图(multiple
5、 graph):含平行边的图 简单图(simple graph):无环和平行边的图,a,b,c,15,图的基本分类(3),有限图(finite graph):顶点个数有限的图 无限图(infinite graph):顶点个数无限的图,根据图中结点的数目可分为:,16,回顾,所有边都有方向,所有边都无方向,既有有向边又有无向边,有平行边,无平行边和环,结点数有限,结点数无限,17,练习题,判断下面给出的两个图的类型。,无向图,有向图 简单图,有向图 无向图 混合图 多重图 简单图,18,底图 定向图 逆图,图的基本分类(4),19,图的基本类型(5),底图:将有向图G的所有有向边换成无向边,得到
6、的无向图称为G的底图。,20,图的基本类型(6),定向图:将无向图G中每条无向边指定一个方向所得到的图称为G的定向图。,21,图的基本分类(7),逆图 将有向图G的每一条边的方向颠倒所得到的图称为G的逆图,记为 。,a,b,c,a,b,c,逆图,22,结点的度(1),结点v的度: 指结点v关联的边数, 记为deg(v)或d(v)。 注意:每个环看作两条边,d(b)=2,d(a)=4,d(c)=4,d(d)=2,23,结点的度(2),有向图中,度可分为:出度(out-degree)和入度 (in-degree) 结点v的出度: 以v为起点的有向边的数目 记为deg+(v) 或d+(v) 结点v的
7、入度: 以v为终点的有向边的数目, 记为deg-(v)或d-(v) 有向图中结点v的度d(v):d(v)=d+(v)+d-(v),a,b,c,deg+(c) = 2 deg-(c) = 3 deg(c) = deg+(c) + deg-(c) = 5,24,定理 1,设图G是具有n个顶点、m条边的有向图,V(G)=v1,v2,vn,则,25,定理 2 (Hankshaking),设图G是具有n个顶点、m条边,V(G)=v1,v2,vn,则,推论:度数为奇数的顶点个数必为偶数。,26,常用的简单图,赋权图 无向完全图 有向完全图 竞赛图 正则图,27,赋权图,赋权图是顶点或边附加了信息的图。 顶
8、点或边中附加的信息称为权。,28,赋权图例,A,F,B,C,D,E,29,普通图和赋权图,比较 对普通图,主要研究结点和边之间的拓扑关系 度,连通,通路等性质 赋权图给普通图附加了数量关系 距离,成本,代价,规模等性质,30,无向完全图,任意两个不同的顶点间都有一条边关联的无向简单图称为无向完全图 n阶无向完全图记为:Kn,K1,K2,K3,K4,K5,31,有向完全图,任意两个不同的顶点之间都有两条方向相反的有向边相连并且每一个顶点都有一条自回路的有向图 称为有向完全图,32,完全图边数,n阶无向完全图的边数是多少? n(n-1)/2 n阶有向完全图的边数是多少? n2,33,竞赛图(tou
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 部分 GraphTheory 教学 课件
链接地址:https://www.31doc.com/p-2562011.html