您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 信息化管理 > 第十四部分图的基本概念教学-
1第十四章图的基本概念第四部分:图论2七桥问题问题寻找走遍哥尼斯堡(KÖnigsberg)城的7座桥,且只许走过每座桥一次,最后又回到原出发点求解1736年瑞士大数学家欧拉(Leonhard•Euler)发表了关于“哥尼斯堡七桥问题”的论文(图论的第一篇论文)。他指出从一点出发不重复的走遍七桥,最后又回到原来出发点是不可能的。3图论图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究,如1736年欧拉(L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题:例如迷宫问题、棋盘上马的行走路线问题4棋盘上马的行走路线问题在中国象棋中,马走“日”字,即每步从1×2矩形的一个顶点跳到相对的顶点。如图,马从M(3,2)一次只能跳到A、B、C、D、E、F、G、H中的任何一个位置。问题:马能否从棋盘上任意一点出发,不重复、不遗漏地走遍整个棋盘(即每一点都走到并且只到一次)?5棋盘上马的行走路线问题将马目前所在位置涂成白色,用涂色的方法,将棋盘上的点分为黑、白相间的两类楚河汉界01234567812346环游世界各国的问题英国数学家哈密顿于1859年以游戏的形式提出:把一个正十二面体的二十个顶点看成二十个城市,要求找出一条经过每个城市恰好一次而回到出发点的路线。这条路线就称“哈密顿圈”。一百多年来,对哈密顿问题的研究,促进了图论的发展。以一个正12面体的20个顶点分别代表20个城市,要求旅行者从1个城市出发,沿着正12面体的棱,寻找一条不重复、不遗漏地一次跑遍所有城市,最后回到出发点的途径。7四色猜想问题:任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色用数学语言表示,即:“将平面任意地细分为不相重叠的区域,每一个区域总可以用1,2,3,4这四个数字之一来标记,而不会使相邻的两个区域得到相同的数字”8图论图论不断发展,它在解决运筹学,网络理论,信息论,控制论,博奕论以及计算机科学等各个领域的问题时,显示出越来越大的作用9第十四章图的基本概念第一节:图第二节:通路、回路、图的连通性第三节:图的矩阵表示和运算10第一节:图无序积:设A,B为任意的两个集合,称{{a,b}|a∈A且b∈B}为A与B的无序积,记做A&B无向图:一个无向图G是一个二重组V(G),E(G),其中V(G)为有限非空结点(或叫顶点)集合,E(G)是边的集合,它是无序积V&V的多重子集,其元素为无向边,简称边。有向图:一个有向图G是一个二重组V(G),E(G),其中V(G)为有限非空结点(或叫顶点)集合,E(G)是边的集合,它是笛卡儿乘积V×V的多重子集,其元素为有向边,简称边。11下面定义一些专门名词:(1)通常用G表示无向图,D表示有向图,但G也可以泛指图。V(G),E(G)分别表示G的顶点集和边集。|V(G)|,|E(G)|分别表示G的顶点数和边数,若|V(G)|=n,则称G为n阶图。(2)若|V(G)|,|E(G)|均为有限数,则称G为有限图。(3)若图G中,边集为空,则称之为零图,若G为n阶图,则称之为n阶零图,记为Nn,N1称为平凡图。(4)顶点集为空的图记为空图。第一节:图12一些定义(5)称顶点或边用字母标定的图为标定图,否则成为非标定图。另外,将有向边改为无向边后的图称为原图的基图。(6)设G=V,E为无向图,ek=(vi,vj)∈E,则称vi,vj为ek的端点,ek与vi或ek与vj是彼此关联的。若vi≠vj,则称ek与vi或ek与vj的关联次数为1,若vi=vj,则称ek与vi的关联次数为2,并称为环。任意的vl∈V,若vl≠vi且vl≠vj,则称ek与vl的关联次数为0。13一些定义(7)设无向图G=V,E,vi,vj∈V,ek,el∈E。若存在et∈E,使得et=(vi,vj),则称vi与vj是相邻的。若ek与el至少有一个公共端点,则称ek与el是相邻的。有向图D=V,E,vi,vj∈V,ek,el∈E。若存在et∈E,使得et=vi,vj,则称vi为et的始点,vj为et的终点,并称vi邻接到vj,vj邻接于vi,若ek的终点为el的始点,则称ek与el相邻。14一些定义(8)设无向图G=V,E,对所有的v∈V称为v的邻域,记为NG(v),并称NG(v)∪{v}为v的闭邻域,记为。称为v的关联集,记为IG(v)。设有向图G=V,E,对所有的v∈V,称为v的后继元素。称为v的先驱元素。称两者之并为v的邻域,记为ND(v)。称ND(v)∪{v},v的闭邻域。{|(,)}uuVuvEuvGN(v){|}eeEev与相关联{|V,}uuvuEuv{|,}uuVuvEuv15一些定义定义14.3在无向图中,关联一对顶点的无向边如果多于一条,则称这些边为平行边,平行边的条数称为重数。在有向图中,关联一对顶点的有向边如果多于一条,并且这些边的始点和终点相同,则称这些边为平行边。含平行边的图称为多重图,即不含平行边也不含环的图称为简单图。16一些定义非多重图称为线图。由定义可见,简单图是没有环和平行边的图。17一些定义定义14.4:在无向图中,任意点其作为边的端点次数之和称为该点的度数,记为dG(v).在有向图中,对于任何结点v,以v为始点的边的条数,称为结点v的引出次数(或出度),记作d+(v);以v点为终点的边的条数称为v的引入次数(或入度),记作d-(v);结点的v的引入次数和引出次数之和称为v的次数(度数),用d(v)表示。由定义可见:度数d(v)=d+(v)+d-(v)。定义:最大度,最小度,最大出度,最大入度,最小入度,最小出度,悬挂点,悬挂边18例1例:d(a)=3(引入)+2(引出)=5d(b)=4d(c)=3d(1)=3d(2)=3d(3)=2以后为了叙述方便,我们将具有n个结点和m条边的图简称为(n,m)图19握手定理定理14.1(握手定理):设G是(n,m)无向图,它的顶点集合V={v1,v2,…,vn},于是有1()2niidvm111()2,()()nnniiiiiidvmdvdvm证明:∵在无向图中引入一条边,总的次数增2,∴若有m条边,则总次数为2m。(此定理也可推广到有向图和混合图)定理14.1在有向图中,则为:20例2d(a)=4,d(b)=3,d(c)=4,d(d)=3,m=7,2m=14=ΣdΣd=3+4+3+4=1421例3例:若图G有n个顶点,(n+1)条边,则G中至少有一个顶点的度数≥3。证明:设G中有n个结点分别为v1,v2,…,vn,则由握手定理:Σd(vi)=2(n+1)而顶点的平均度数为:d(vi)=2(n+1)/n=2+1/n2∴顶点中至少有一个顶点的度数≥322握手定理的推论推论:在图中,度数为奇数的顶点必定有偶数个。证明:设度数为偶数的顶点有n1个,记为vei(i=1,2,…n1),度数为奇数的顶点有n2个,记为voi(i=1,2,…,n2)。由上一定理得因为度数为偶数的各顶点次数之和为偶数。所以前一项度数为偶数;若n2为奇数,则第二项为奇数,两项之和将为奇数,但这与上式矛盾。故n2必为偶数。问题:是否在一个部门的25个人中间,由于意见不同,每个人恰好与5个人意见一致?121112()()()nnnieioiiiimdvdvdv23可图化、可简单图化设G=V,E为一个n阶无向图,V={v1,v2,…,vn},称d(v1),d(v2)…d(vn)为G的度数列。对于顶点标定的无向图,它的度数列是唯一的。反之,对于给定的非负整数列d=(d1,d2,…,dn),若存在以V={v1,v2,…,vn}为顶点集的n阶无向图G,使得d(vi)=di,则称d是可图化的。特别的,如果所得图是简单图,则称d是可简单图化的。24可图化的判断定理定理14.3设非负整数列d=(d1,d2,…,dn),则d是可图化的当且仅当证明:必要性显然充分性:构造性证明定理14.4设G为任意n阶无向简单图,则△(G)≤n-110(mod2)niid25可图化例:判断下列各非负整数列哪些是可图化的?哪些是可简单图化的?(1)(5,5,4,4,2,1)(2)(5,4,3,2,2)(3)(3,3,3,1)(4)(d1,d2,…,dn),d1d2…dn≥1,且为偶数(5)(4,4,3,3,2,2)1niid26同构的定义定义14.5:设G=〈V,E〉和G’=〈V’,E’〉是两个图,若存在从V到V’一双射函数g:V→V’,使得对任意的a,b∈V,[a,b]∈E当且仅当[g(a),g(b)]∈E’,并且[a,b]和[g(a),g(b)]有相同的重数,则称G’和G同构。讨论定义:(1)G’和G是同构的,它们的顶点必须是一一对应的;(2)且对无向图而言,还要保持顶点之间的邻接关系和边的重数;(3)且对有向图而言,不但要保持顶点之间的邻接关系,而且还应保持边的方向和边的重数。图的同构关系可以看作是全体图集合上的二元关系,并且此关系是等价关系。27例4例:存在一双射函数g:{1,2,3,4}→{a3,a4,a2,a1},其中:顶点的一一对应:g(1)=a3;g(2)=a4;g(3)=a2;g(4)=a1;边的一一对应:g3,1=a2,a3;g4,2=a1,a4;g4,3=a1,a2;g2,1=a4,a328例5例:下面给出二个无向图,试求出同构函数g:{1,2,3,4,5,6}→{a1,a2,a3,a4,a5,a6}边的对应为:g((i,j))=(g(i),g(j))={ai,aj}29同构的性质两图同构的必要条件:(1)顶点数相等;(2)边数相等;(3)度数相同的顶点数相等。但这不是充分条件。如下图30完全图定义14.6:在n个顶点的有向图G=V,E中,如果每个顶点都邻接到其余的n-1个顶点,又邻接于其余的n-1个顶点,则称G为有向完全图;在n个顶点的无向图G=V,E中,每二个顶点之间均有一条边连接,则称G为无向完全图。31特殊图定义14.7:所有顶点均具有同样度数的简单无向图为正则图,各顶点的度数均为k时称为k-正则图。32子图的定义定义14.8:设G=V,E,G’=V’,E’是二个图,(a)若V’V,E’E,则称G’是G的子图;(b)若V’V,E’E,并且G≠G’,则称G’是G的真子图;(c)若V’=V,E’E,则称G’是G的生成子图(支撑子图)。(d)若子图G’中没有孤立顶点,G’由E’唯一确定,则称G’为由边集E’导出的子图。(e)若在子图G’中,对V’中的任意二顶点u,v,当[u,v]∈E时有[u,v]∈E’,则G’由V’唯一确定,此时称G’为由顶点集V’导出的子图。33例6例:G图如下G的真子图生成子图:E’={b,a,a,d,c,b,c,d}导出的子图由V’={a,b,d,e}导出的子图34例7例画出4阶3边的所有非同构的无向简单图。解:由握手定理可知,该无向简单图各顶点度数之和为6,最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是,将6分成4个非负数,每个整数均大于等于0且小于等于3,并且奇数的个数为偶数。有三种情况3,1,1,1;2,2,1,1;2,2,2,0将每种度数列所有非同构的图都画出来即可得所要求的全部非同构图。35补图定义14.9:设无向简单图G=V,E有n个顶点,无向简单图H=V,E’也有同样的顶点,而E’是由n个顶点的完全图的边删去E所得,则图H称为图G的补图。自补图:H与G同构36例8例:试画出5个顶点三条边和5个顶点七条边的简单无向图。解:5个顶点三条边的图5个顶点七条边的图(为5顶点三条边的补图)37图的操作关于图的四种操作:(1)删去G中的一条边e;(2)删去G中的一个顶点(即是删去顶点v和与v有关联的所有边)。(3)设边e=(u,v)∈E,用G\e表示从G中删除e后,将e的两个端点u
本文标题:第十四部分图的基本概念教学-
链接地址:https://www.777doc.com/doc-1863820 .html