图的基本概念与握手定理.ppt

单击此处编辑母版标题样式,*,第三部分 图 论,第一讲,图论的基本概念与握手定理,1,一、图的概念,二、图的类型,三、结点的度数,四、握手定理,五、同构概念,六、邻接矩阵,主要内容,2,图论研究,图的逻辑结构与性质,.,引 言,图论最早起源于一些数字游戏的难题研究图论的最早论文是,1736,年瑞士数学家欧拉（,Leonhard,Euler,）,所写,，,从而使欧拉成为图论的创始人。,图论是组合数学的一个分支，,研究集合上的二元关系的工具，是建立数学模型的一个重要手段。,在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。计算机的迅速发展，使得图论成为数学领域里发展最快的分支之一。,3,引 言,哥尼斯堡七桥问题,当时哥尼斯堡（,Konigsberg,）,城（现名加里宁格勒,属俄罗斯）的居民有郊游的习惯，在城郊的普雷格尔（,Pregel,）,河畔，河中有两个小岛，七座桥将两个小岛和河岸连接起来，如图所示，,问一个人能否从任一小岛出发不重复地走遍七座小桥？,4,1852,年毕业于伦敦大学的弗南西斯,格思里发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？,四色问题,5,Hamilton,问题,1856,年，英国数学家,Hamilton,设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。,此路线称为：,哈密尔顿回路,，而此图称为：,哈密尔顿图,。,6,图,G,=,其中,(1),V,为顶点集，,其元素称为,结点（顶点）,-,用来表示事物,(2),E,为,V,V,的多重集。,其元素称为,边,-,表示事物,间的二元关系,(,一,),图的定义,:,一、图的概念,7,(,二,),结点与边的关系,:,结点与边,(,不,),相,关联,：,结点与结点,边与边,(,不,),相,邻接,一、图的概念,(,三,),特殊点,孤立点,:,不与任何结点相邻接的结点,悬挂点,:,只与一条边相关联的结点,(,四,),特殊的边,:,环,:,一条边若与两个相同的结点相关联则称为,环,。,多重边,(,平行边）,:,与两个结点相关联的边若多于一条，则称这些边为,多重边,。,8,有向图与无向图,:,简单图与多重图,:,简单图,-,不含环与多重边；多重图,-,含多重边,有权图与无权图,:,b.,按边的种类分类：,有限图与无限图,：,V,与,E,为有限集合的图叫,有限图,，否则叫无限图。,(,n,m,),图,：,有,n,个结点与,m,条边的图。,零图,:,即,(n,0),图,;,平凡图,:,即,(1,0),图,。,完全图,:,任意两个结点都相邻接的图。,K-,正则图,:,每个结点都与,K,条边相关联。,c.,按结点集与边集的“阶”分类,a,按边的方向分类,二、图的类型,9,注意,：,完全图是,n,-,1,正则图,完全图的每个结点都与其它,n-1,个结点相邻接,即与,n-1,条边相关联,所以是,n-1,正则图,反之正则图不一定是完全图。,1.,完全图：,2.,正则图：,是,3,正则图,完全图,不是完全图,二、图的类型,10,子图：,设,G=,G=,为两个图，满足,V,V,且,E,E,，,则称,G,为,G,的,子图,，,G,为,G,的,母图,，记作,G,G,。,(1),G,为,G,的,真子图：,若,G,G,且,V,V,或,E,E,。,(2),G,为,G,的,生成子图：,若,G,G,且,V,=,V,。,(3)V,1,导出的导出子图：,顶点集,V,1,V,边集为两端点均在,V,1,中的全体边构成的子图。,(4),E,1,导出的导出子图：,E,1,E,以,E,1,中边关联的顶点的全体为顶点集的,G,的子图。,二、图的类型,11,a,b,c,d,a,1,b,1,a,b,c,d,d,1,a,1,b,1,c,1,a,b,c,d,d,1,b,1,a,b,c,d,d,1,a,1,b,1,c,1,母图,真子图,V,V,或,E,E,生成子图,G,G,且,V,=,V,导出子图,V,V,或,E,E,二、图的类型,12,补 图,设,G=V,E,对于,G1=V,E1,若,有,G2=V,EE1,是完全图,且,EE1=,则称,G1,是,G,的补图。,图,G,图,G1,图,G2,二、图的类型,13,在无向图,G,中，与,v,相邻的顶点的数目称为,v,的次或度,/degree,。,记为,deg(v,),或,d(v,),。,在有向图,G,中，以,v,为终点的边的条数称为,v,的,入次或入,度,/in-degree,。,记为,deg,(v),或,d,(v),。,以,v,为起点的边的条数称为,v,的,出次或出度,/out-degree,。,记为,deg,+,(v,),或,d,+,(v),。,三、结点的度数,14,在无向图,G,中,令,(G)=,maxd(v)|vV(G,),(G)=,mind(v,)|,vV(G,),称,(G),和,(G),分别为,G,的最大度和最小度。,在有向图,D,中,类似定义,(D),、,(G),。,另外,令,+,(G)=,maxd,+,(v,)|,vV(D,),+,(G)=,mind,+,(v,)|,vV(D,),-,(G)=,maxd,-,(v,)|,vV(D,),-,(G)=,mind,-,(v,)|,vV(D,),分别为,D,的最大出度、最小出度、最大入度、最小入度。简记作、,、,+,、,+,、,-,、,-,。,三、结点的度数,15,定理,1,设,G,=,为,任意无向图,，,V,=,v,1,v,2,v,n,|,E,|=,m,则,四、握手定理,定理,2,设,D,=,为,任意有向图,，,V,=,v,1,v,2,v,n,|,E,|=,m,则,证,G,中每条边,(,包括环,),均有两个端点，所以在计算,G,中各顶点度数之和时，每条边均提供,2,度，,m,条边共提供,2,m,度,.,16,握手定理推论及应用,推论,任何图,(,无向或有向,),中，奇度顶点的个数是偶数,.,例,1,无向图,G,有,16,条边，,3,个,4,度顶点，,4,个,3,度顶点，其余顶点度数均小于,3,，问,G,的阶数,n,为几？,解 设除,3,度与,4,度顶点外，还有,x,个顶点,v,1,v,2,v,x,，则,d,(,v,i,),2,，,i,=1,2,x,，,于是,32,24+2,x,得,x,4,阶数,n,4+4+3=11.,17,五、图的同构,定义,设,G,1,=,G,2,=,为两个图,(,有向或无向图,),，,（,1,）若存在双射函数,f,:,V,1,V,2,对于,v,i,v,j,V,1,(,v,i,v,j,),E,1,当且仅当,(,f,(,v,i,),f,(,v,j,),E,2,（,E,1,当且仅当,E,2,),（,2,）,(,v,i,v,j,),（,）与,(,f,(,v,i,),f,(,v,j,),（,）的重数相同。,则称,G,1,与,G,2,是,同构,的，记作,G,1,G,2,.,18,图同构的必要条件,图之间的同构关系是等价关系,.,同构的必要条件：,边数相同，顶点数相同,;,度数列相同,;,度数相同的结点数目相同,19,图同构的实例,(1)(2)(3)(4),图中，,(1),与,(2),不同构（度数列不同），,(3),与,(4),也不同构,.,20,六、图的表示,邻接矩阵,21,同构判定算法（用邻接矩阵）,1,、根据图确定其邻接矩阵,2,、,计算行次（矩阵每行的个数,-,对应于出次）和列次：（对应于入次）,3,、不考虑出现的次序不同，若行次与列次不同，则必不同构，否则继续,4,、同时交换其一矩阵的行和行，列和列。,若此矩阵能变成与另一矩阵一样，则同构。对所有顶点的排列都试过，仍不相同，则不同构。,邻接矩阵的应用,22,