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