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