《《图的基本概念》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图的基本概念》PPT课件.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论 (Graph Theory)图论是个应用十分广泛而又极其有趣数学分支图论是个应用十分广泛而又极其有趣数学分支,物理、物理、学、生物、经济、管理科学、信息论、计算机等各个领学、生物、经济、管理科学、信息论、计算机等各个领域都可以找到图论的足迹域都可以找到图论的足迹.历史上很多数学家对图论的形成作出过贡献历史上很多数学家对图论的形成作出过贡献,特别要提特别要提到的欧拉到的欧拉(Euler)、基尔霍夫、基尔霍夫(Kirchhoff)与凯莱与凯莱(Cayley).欧拉在欧拉在1736年发表了第一篇图论的论文年发表了第一篇图论的论文,解决了著名的解决了著名的七桥问题七桥问题.拓扑学中著名的欧拉公式
2、拓扑学中著名的欧拉公式,也是图论中的重要也是图论中的重要公式公式.基尔霍夫对电路网络的研究基尔霍夫对电路网络的研究(基尔霍夫定律基尔霍夫定律)以及凯莱在以及凯莱在有机化学计算中应用了树和生成树等概念有机化学计算中应用了树和生成树等概念.很多有趣的数学游戏也促进了图论的发展很多有趣的数学游戏也促进了图论的发展,如汉米尔顿如汉米尔顿周游世界游戏周游世界游戏,四色定理等四色定理等,都促进了图论的发展都促进了图论的发展.1.图的基本概念例例1.多用户操作系统中的进程状态变换图多用户操作系统中的进程状态变换图:(进程进程:一个业务可以分成若干个阶段一个业务可以分成若干个阶段,每个阶段看成一每个阶段看成一
3、个进程个进程.一个进程有三种状态一个进程有三种状态.)就绪状态就绪状态:进程具备执行条件进程具备执行条件,因因CPU少少,要排队等待分配要排队等待分配 CPU.就绪 r执行 e等待 w进程调度请求I/OI/O完成rweV=r,e,wE=,执行状态执行状态:进程已经分配到进程已经分配到CPU,它的程序正被执行它的程序正被执行.等待状态等待状态:进程等待某事件进程等待某事件(如如I/O完成完成),此时就是给它此时就是给它CPU 也不能执行也不能执行.例例2.“七桥问题七桥问题”十八世纪十八世纪,哥尼斯堡城内有一条河哥尼斯堡城内有一条河-普雷普雷格尔河格尔河,河中有两个岛屿河中有两个岛屿,河面架有七
4、座桥河面架有七座桥,使得岛屿与两使得岛屿与两岸之间互相贯通岸之间互相贯通.V=A,B,C,D E=e1,e2,e3,e4,e5 e6,e7 人们茶余饭后经常到桥上散步人们茶余饭后经常到桥上散步,从而提出这样问题从而提出这样问题:是否是否可以从某地出发，每座桥都走一次可以从某地出发，每座桥都走一次,再回到出发点再回到出发点.很多很多人试图找出这样的路径人试图找出这样的路径,都没有找到都没有找到.后来欧拉证明这样后来欧拉证明这样的路径根本不存在的路径根本不存在.此图可以抽象为上边右图此图可以抽象为上边右图.ABCDABC De1e5e7e6e3e4e2例例3.在机械加工中在机械加工中,经常需要在一
5、块金属薄板上钻若干孔经常需要在一块金属薄板上钻若干孔(或者是机械手在印刷电路板上安装电子元件或者是机械手在印刷电路板上安装电子元件)如图所示如图所示:问如何确定钻孔的次序问如何确定钻孔的次序,使之加工的时间最短使之加工的时间最短.这个问题可以抽象为在一个图上求从某一个结点出发这个问题可以抽象为在一个图上求从某一个结点出发,经过所有结点一次经过所有结点一次,使得此路径最短使得此路径最短.如何找到此路径如何找到此路径.类似的类似的:旅行最优问题旅行最优问题,工程最优问题工程最优问题,成本成本(费用费用)最最低低.5372一一.图的概念图的概念 一个图一个图 G=,其中其中 V(G):是是G的结点的
6、非空集合的结点的非空集合.(V(G),简记成简记成V.E(G):是是G的边的集合的边的集合.有时简记成有时简记成E.结点结点(Vertices):用用 表示表示,旁边标上该结点的名称旁边标上该结点的名称.边边(Edges):有向边有向边:带箭头的弧线带箭头的弧线.从从u到到v的边表示成的边表示成 无向边无向边:不带箭头的弧线不带箭头的弧线.u和和v间的边表示成间的边表示成(u,v)rweV(G1)=r,e,wE(G1)=,ABC De1e5e7e6e3e4e2G1:G2:V(G2)=A,B,C,DE(G2)=e1,e2,e3,e4,e5,e6,e7 在图中在图中,结点的相对位置不同结点的相对位
7、置不同,边的曲直、长短无关紧要边的曲直、长短无关紧要.邻接点邻接点:与一边关联的两个结点与一边关联的两个结点.u v a b 邻接边邻接边:关联同一个结点的两条边关联同一个结点的两条边.环环:只关联一个结点的边只关联一个结点的边.平行边平行边:在两个结点之间关联的多条边在两个结点之间关联的多条边.二二.有向图与无向图有向图与无向图 有向图有向图:只有有向边的图只有有向边的图.无向图无向图:只有无向边的图只有无向边的图.三三.零图与平凡图零图与平凡图 孤立结点孤立结点:不与任何边关联的结点不与任何边关联的结点.u 零图零图:仅由一些孤立结点构成的图仅由一些孤立结点构成的图.a 即此图的边的集合即
8、此图的边的集合E=b c 平凡图平凡图:仅由一个孤立结点构成的零图仅由一个孤立结点构成的零图.|V(G)|=1,|E(G)|=0e1 v e2 G:四四.简单图与多重图简单图与多重图 简单图简单图:不含有环和平行边的图不含有环和平行边的图.多重图多重图:含有平行边的图含有平行边的图.五五.无向图结点无向图结点v的度的度:1.定义定义:G是个无向图是个无向图,vV(G),结点结点v所关所关联边数联边数,称之为结点称之为结点v的度的度.记作记作 deg(v).(或或d(v).deg(a)=3 deg(b)=5 deg(c)=4 deg(d)=2 一个环给结点的度是一个环给结点的度是2.:令令G=是
9、无向图是无向图,V=v1,v2,v3,vn,则称则称:(deg(v1),deg(v2),deg(v3),deg(vn)为图为图G的结点度的结点度序列序列.例如上图的结点度序列为例如上图的结点度序列为:(3,5,4,2)(G)与最小度与最小度(G):G=是无向图是无向图,(G)=maxdeg(v)|vG (G)=mindeg(v)|vGABCDe1e5e7e6e3e4e2cbacabd上图中上图中(G)=5 (G)=2 4.每个无向图所有结点度总和等于边数的每个无向图所有结点度总和等于边数的2倍倍.即即证明证明:因为图中每条边关联两个结点因为图中每条边关联两个结点,因此每条边给予它因此每条边给予
10、它所所关联的两个结点的度各是关联的两个结点的度各是1,即一条边对应的度数是即一条边对应的度数是2,所所以整个图的度数总和为边数的以整个图的度数总和为边数的2倍倍.(握手定理握手定理)每个无向图中每个无向图中,奇数度的结点必为偶奇数度的结点必为偶数个数个.(一次集会中一次集会中,与奇数个人握手的人与奇数个人握手的人,必是偶数个必是偶数个.)证明证明:令令G=是无向图是无向图,将将V分成两个子集分成两个子集V1 和和V2,其中其中 V1-是度数是奇数的结点集合是度数是奇数的结点集合,V2-是度数是偶数的结点集合是度数是偶数的结点集合 而而 是偶数是偶数.所以所以 也是偶数也是偶数,于是奇数度的结点
11、数是偶数于是奇数度的结点数是偶数.deg(v)=2|E|vVdeg(v)+deg(v)=2|E|vV1 vV2deg(v)vV2deg(v)vV1六六.k-正则图正则图:一个无向简单图一个无向简单图G中中,如果如果(G)=(G)=k则称则称G为为k-正则图正则图.课堂练习课堂练习:1.下面哪些数的序列下面哪些数的序列,可能是一个图的度数序列可能是一个图的度数序列?如果可能如果可能,请试画出它的图请试画出它的图.哪些可能不是简单图哪些可能不是简单图?a)(1,2,3,4,5)b)(2,2,2,2,2)c)(1,2,3,2,4)2.已知无向简单图已知无向简单图G中中,有有10条边条边,4个个3度结
12、点度结点,其余结点其余结点的的度均小于或等于度均小于或等于2,问问G中至少有多少个结点中至少有多少个结点?为什么为什么?1.a)(1,2,3,4,5)b)(2,2,2,2,2)c)(1,2,3,2,4)解解:a)不是不是,因为有三个数字是奇数因为有三个数字是奇数.b)是是.c)可能不是简单图可能不是简单图,如图：如图：:已知边数已知边数|E|=10,deg(v)=2|E|=20 其中有其中有4个个3度结点度结点,余下结点度之和为余下结点度之和为:20-34=8因为因为G是简单图是简单图,其余每个结点度数其余每个结点度数2,所以至少还有所以至少还有4个结点个结点.所以所以G中至少有中至少有8个结
13、点个结点.同时，同时，8个结点也是个结点也是足够的。例如足够的。例如“目目”的图形就是满足条件的例子。的图形就是满足条件的例子。七七.有向图结点的出度和入度有向图结点的出度和入度:(in degree out degree)G=是有向图是有向图,vV v的出度的出度:从结点从结点v射出的边数射出的边数.记作记作deg+(v)或或 dego(v)v的入度的入度:射入结点射入结点v的边数的边数.记作记作deg-(v)或或 degi(v)degi(a)=2 degi(b)=2 degi(c)=1 degi(d)=1dego(a)=2 dego(b)=3 dego(c)=1 dego(d)=0 G=是
14、有向图是有向图,则则G的所有结点的出度之和的所有结点的出度之和等于入度之和等于入度之和.证明证明:因为图中每条边对应一个出度和一个入度因为图中每条边对应一个出度和一个入度.所以所所以所有结点的出度之和与所有结点的入度之和都等于有向边有结点的出度之和与所有结点的入度之和都等于有向边数数.必然有所有结点的出度之和等于入度之和必然有所有结点的出度之和等于入度之和.abcd八八.完全图完全图 定义定义:G是个简单图是个简单图,如果每对不同结点之间都有边相连如果每对不同结点之间都有边相连则称则称G是个无向完全图是个无向完全图.如果如果G有有n个结点个结点,则记作则记作Kn.定理定理8-1.4 无向完全图
15、无向完全图Kn,有边数有边数证明证明:因为因为Kn中每个结点都与其余中每个结点都与其余n-1个结点关联个结点关联,即每即每个结点的度均为个结点的度均为n-1,所以所以Kn的所有结点度数总和为的所有结点度数总和为n(n-1),设边数为设边数为|E|,于是于是n(n-1)=2|E|所以所以|E|=K2K3K4K52.有向图的完全图有向图的完全图(注注:这里的定义与教材不同这里的定义与教材不同)1).有向简单完全图有向简单完全图:G是个是个有向简单图有向简单图,如果任何两个如果任何两个不不同同结点之间都有相互可达的边结点之间都有相互可达的边,则称它是有向简单完全则称它是有向简单完全图图.例如例如:定
16、理定理8-1.5:有有n个结点的有向简单完全图有边数为个结点的有向简单完全图有边数为n(n-1).证明证明:显然它的边数是显然它的边数是Knn(n-1).2).有向完全图有向完全图(有向全图有向全图)(它与完全关系图一致它与完全关系图一致)G是个有向图如果任何两个结点之间都有相互可达的边是个有向图如果任何两个结点之间都有相互可达的边,则称它是有向完全图则称它是有向完全图.其图形如下其图形如下:所以有所以有n个结点的有向完全图个结点的有向完全图,有边数有边数 n2.:设设G=是图是图,如果如果G=且且V V,V,E E,则称则称G是是G的子图的子图.可见可见G1,G2,G3都是都是K5的子图的子
17、图.bcdeabcabcdeG1G2G3K5abcde2.生成子图生成子图设设G=是图是图,G=,G是是G的子图的子图,如果如果V=V,则称则称G是是G的生成子图的生成子图.上例中上例中,G1是是K5的生成子图的生成子图.十十.补图补图由由G的所有结点和为使的所有结点和为使G变成完全图变成完全图,所需要添加的那些所需要添加的那些边组成的图边组成的图,称之为称之为G相对完全图的补图相对完全图的补图,简称简称G的补图的补图,记作记作 .GK5GG设设G1=是图是图G=的子图的子图,如果有如果有G2=使得使得E2=E-E1且且V2中仅包含中仅包含E2中的边所关联的结点中的边所关联的结点,则称则称G2
18、是是G1相对相对G的补图的补图.可见可见G2是是G3相对相对G的补图的补图.G3也是也是G2相对相对G的补图的补图.而而G1不是不是G3相对相对G的补图的补图(多了一个结点多了一个结点).但是但是G3是是G1相对相对G的补图的补图.可见可见:相对补图无相互性相对补图无相互性.abcdeGG1abcdecdbeG2abcdeG3十二十二.图的同构图的同构设设G=和和G=是图是图,如果存在双射如果存在双射f:VV 且且任何任何vi,vjV,若边若边(vi,vj)E,当且仅当当且仅当 边边(f(vi),f(vj)E,(或或若边若边E,当且仅当当且仅当 边边E),则称则称G与与G同构同构,记作记作G
19、G.(同构图要保持边的同构图要保持边的“关联关联”关系关系)例如例如:右边所示的两个图右边所示的两个图:G=G=构造映射构造映射f:VV两个图同构的必要条件两个图同构的必要条件:1.结点个数相等结点个数相等.2.边数相等边数相等.3.度数相同的结点数相等度数相同的结点数相等.4.对应的结点的度数相等对应的结点的度数相等.abcd1432a 1b 2c 3d 4a 1b 2c 3d 4下面是同构的图下面是同构的图:右面两个图不同构右面两个图不同构:左图中四个左图中四个3度结点度结点构成四边形构成四边形,而右图而右图,则不然则不然.练习练习:请画出请画出K4的所有不同构的生成子图的所有不同构的生成
20、子图.afbecd35162 4312abcabecd13452练习练习:请画出请画出K4的所有不同构的生成子图的所有不同构的生成子图.本节要求本节要求:准确掌握如下基本概念和定理准确掌握如下基本概念和定理:1.有向边有向边,无向边无向边,孤立结点孤立结点,平行边平行边,环环.2.有向图有向图,无向图无向图,零图零图,平凡图平凡图,简单图简单图,多重图多重图,完全图完全图,子图子图,生成子图生成子图,补图补图,相对补图相对补图3.四个定理四个定理(关于结点度关于结点度,以及结点度与边数关系以及结点度与边数关系)4.图的同构图的同构(会判断会判断).作业作业:P173 (7.1)(7.3)(7.4)(7.5)(7.15)