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

1、第三部分第三部分 图图 论论 第一讲 图论的基本概念与握手定理一、一、图的概念图的概念 二、二、图的类型图的类型三、三、结点的度数结点的度数四、四、握手定理握手定理五、五、同构概念同构概念六、六、邻接矩阵邻接矩阵主要内容主要内容图论研究图论研究图的逻辑结构与性质图的逻辑结构与性质.引引 言言 图论最早起源于一些数字游戏的难题研究图论的最早论文是1736年瑞士数学家欧拉（Leonhard Euler）所写，从而使欧拉成为图论的创始人。图论是组合数学的一个分支，图论是组合数学的一个分支，研究集合上的二研究集合上的二元关系的工具，是建立数学模型的一个重要手段。元关系的工具，是建立数学模型的一个重要手

2、段。在物理、化学、信息学、运筹学等各方面都取得在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。计算机的迅速发展，使得图论成了丰硕的成果。计算机的迅速发展，使得图论成为数学领域里发展最快的分支之一。为数学领域里发展最快的分支之一。引引 言言哥尼斯堡七桥问题哥尼斯堡七桥问题 当时哥尼斯堡（Konigsberg）城（现名加里宁格勒,属俄罗斯）的居民有郊游的习惯，在城郊的普雷格尔（Pregel）河畔，河中有两个小岛，七座桥将两个小岛和河岸连接起来，如图所示，问一个人能否从任一小岛出发不重复地走遍七座小桥？1852年毕业于伦敦大学的弗年毕业于伦敦大学的弗南西斯南西斯格思里发现了一种有格思里发现了

3、一种有趣的现象：趣的现象：“看来，每幅地看来，每幅地图都可以用四种颜色着色，图都可以用四种颜色着色，使得有共同边界的国家都被使得有共同边界的国家都被着上不同的颜色。着上不同的颜色。”这个现这个现象能不能从数学上加以严格象能不能从数学上加以严格证明呢？证明呢？四色问题四色问题Hamilton问题问题 1856年，英国数学家年，英国数学家Hamilton设计了一个名为周游世设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿二十座大城市（见图），提出的问题是要求游戏者找一条沿

4、着十二面体的棱通过每个端点恰好一次的行走路线。着十二面体的棱通过每个端点恰好一次的行走路线。此路线称为：此路线称为：哈密尔顿回路哈密尔顿回路，而此图称为：而此图称为：哈密尔顿图哈密尔顿图。图图G=,其中其中(1)V 为顶点集，为顶点集，其元素称为其元素称为结点（顶点）结点（顶点）-用来表示事物用来表示事物(2)E为为V V 的多重集。的多重集。其元素称为其元素称为边边-表示事物表示事物间的二元关系间的二元关系(一一)图的定义图的定义:一、图的概念一、图的概念(二二)结点与边的关系结点与边的关系:结点与边结点与边(不不)相相 关联关联：结点与结点结点与结点,边与边边与边(不不)相相邻接邻接一、图

5、的概念一、图的概念(三三)特殊点特殊点孤立点:不与任何结点相邻接的结点悬挂点:只与一条边相关联的结点(四四)特殊的边特殊的边:环:一条边若与两个相同的结点相关联则称为环。多重边(平行边）:与两个结点相关联的边若多于一条，则称这些边为多重边。有向图与无向图:简单图与多重图:简单图-不含环与多重边；多重图-含多重边有权图与无权图:b.按边的种类分类：按边的种类分类：有限图与无限图：V与E为有限集合的图叫有限图，否则叫无限图。(n,m)图：有 n 个结点与 m 条边的图。零图:即(n,0)图;平凡图:即(1,0)图。完全图:任意两个结点都相邻接的图。K-正则图:每个结点都与K条边相关联。c.c.按结

6、点集与边集的按结点集与边集的“阶阶”分类分类a a 按边的方向分类按边的方向分类二、二、图的类型图的类型注意注意：完全图是完全图是 n n-1 1 正则图正则图完全图的每个结点都与其它 n-1 个结点相邻接,即与n-1条边相关联,所以是n-1正则图,反之正则图不一定是完全图。1.完全图：2.正则图：是3正则图 完全图,不是完全图二、二、图的类型图的类型子图：子图：设设G=,G=为两个图，满足为两个图，满足V V且且E E，则称，则称G为为G的的子图子图，G为为G的的母图母图，记，记作作G G。(1)(1)GG为为G G的的真子图：真子图：若若GG G G且且VV V V或或EE E E。(2)

7、G为为G的的生成子图：生成子图：若若GG G G且且VV=V V。(3)V(3)V1 1导出的导出子图：导出的导出子图：顶点集顶点集VV1 1 V V,边集为边集为两端点均在两端点均在V V1 1中的全体边构成的子图。中的全体边构成的子图。(4)E E1 1导出的导出子图：导出的导出子图：EE1 1 E,E,以以E E1 1中边关联的中边关联的顶点的全体为顶点集的顶点的全体为顶点集的G G的子图。的子图。二、二、图的类型图的类型abcda1b1abcdd1a1b1c1abcdd1b1abcdd1a1b1c1母母图图真子图真子图V V或或E E生成子图生成子图G G且且V=V导出子图导出子图V

8、V或或E E二、二、图的类型图的类型补补 图图 设G=V,E,对于 G1=V,E1 若有 G2=V,EE1是完全图,且 EE1=,则称G1 是 G 的补图。图G 图G1 图G2二、二、图的类型图的类型 在无向图在无向图G中，与中，与v相邻的顶点的数目称为相邻的顶点的数目称为v的的次或度次或度/degree。记为记为deg(v)或或d(v)。在有向图在有向图G中，以中，以v为终点的边的条数称为为终点的边的条数称为v的的入次或入度入次或入度/in-degree。记为。记为deg(v)或或d(v)。以。以v为起点的边的条数称为为起点的边的条数称为v的的出次或出度出次或出度/out-degree。记为

9、记为deg+(v)或或d+(v)。三、三、结点的度数结点的度数在无向图在无向图G G中中,令令 (G)=maxd(v)|vV(G)(G)=maxd(v)|vV(G)(G)=mind(v)|vV(G)(G)=mind(v)|vV(G)称称(G)(G)和和 (G)(G)分别为分别为G G的最大度和最小度。的最大度和最小度。在有向图在有向图D D中中,类似定义类似定义(D)(D)、(G)(G)。另外。另外,令令 +(G)=maxd(G)=maxd+(v)|vV(D)(v)|vV(D)+(G)=mind(G)=mind+(v)|vV(D)(v)|vV(D)-(G)=maxd(G)=maxd-(v)|v

10、V(D)(v)|vV(D)-(G)=mind(G)=mind-(v)|vV(D)(v)|vV(D)分别为分别为D D的最大出度、最小出度、最大入度、最小的最大出度、最小出度、最大入度、最小入度。简记作、入度。简记作、+、+、-、-。三、三、结点的度数结点的度数mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理1 设设G=为为任意无向图任意无向图，V=v1,v2,vn,|E|=m,则则四、握手定理四、握手定理定理定理2 设设D=为为任意有向图任意有向图，V=v1,v2,vn,|E|=m,则则证证 G中每条边中每条边(包括环包括环)均有两个端点，所以在计算

11、均有两个端点，所以在计算G中各顶点中各顶点度数之和时，每条边均提供度数之和时，每条边均提供2度，度，m 条边共提供条边共提供 2m 度度.握手定理推论及应用握手定理推论及应用推论推论 任何图任何图(无向或有向无向或有向)中，奇度顶点的个数是中，奇度顶点的个数是偶数偶数.例例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,阶数

12、阶数 n 4+4+3=11.五、图的同构五、图的同构定义定义 设设G1=,G2=为两个图为两个图(有向或有向或无向图无向图)，（1）若存在双射函数）若存在双射函数f:V1V2,对于对于vi,vj V1,(vi,vj)E1 当且仅当当且仅当(f(vi),f(vj)E2 （E1 当且仅当当且仅当 E2)（2）(vi,vj)（）与）与(f(vi),f(vj)（）的重数相同。的重数相同。则称则称G1与与G2是是同构同构的，记作的，记作G1 G2.图同构的必要条件图同构的必要条件图之间的同构关系是等价关系图之间的同构关系是等价关系.同构的必要条件：同构的必要条件：边数相同，顶点数相同边数相同，顶点数相同

13、;度数列相同度数列相同;度数相同的结点数目相同度数相同的结点数目相同图同构的实例图同构的实例 (1)(2)(3)(4)图中，图中，(1)与与(2)不同构（度数列不同），不同构（度数列不同），(3)与与(4)也不同构也不同构.adcb无向图b (c)a (b)c (a)d定定义义 邻邻接接矩矩阵阵：设设有有向向图图（，），1 1，2 2，n n，若若用用方方阵阵nnijaA)(来来表表示示，其其中中 EVVEVVajijiij),(0),(1 称称为为的的邻邻接接矩矩阵阵。六、图的表示六、图的表示邻接矩阵邻接矩阵同构判定算法（用邻接矩阵）同构判定算法（用邻接矩阵）1、根据图确定其邻接矩阵、根据图确定其邻接矩阵2、计算行次（矩阵每行的个数、计算行次（矩阵每行的个数-对应于出次）对应于出次）和列次：（对应于入次）和列次：（对应于入次）3、不考虑出现的次序不同，若行次与列次不同，、不考虑出现的次序不同，若行次与列次不同，则必不同构，否则继续则必不同构，否则继续 4、同时交换其一矩阵的行和行，列和列。、同时交换其一矩阵的行和行，列和列。若此矩阵能变成与另一矩阵一样，则同构。对所若此矩阵能变成与另一矩阵一样，则同构。对所有顶点的排列都试过，仍不相同，则不同构。有顶点的排列都试过，仍不相同，则不同构。邻接矩阵的应用邻接矩阵的应用