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

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