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

《图的基本概念与握手定理.pptx》由会员分享，可在线阅读，更多相关《图的基本概念与握手定理.pptx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1图论研究图的逻辑结构与性质.引 言 图论最早起源于一些数字游戏的难题研究图论的最早论文是1736年瑞士数学家欧拉（Leonhard Euler）所写，从而使欧拉成为图论的创始人。图论是组合数学的一个分支，研究集合上的二元关系的工具，是建立数学模型的一个重要手段。在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。计算机的迅速发展，使得图论成为数学领域里发展最快的分支之一。第1页/共21页2引 言哥尼斯堡七桥问题 当时哥尼斯堡（Konigsberg）城（现名加里宁格勒,属俄罗斯）的居民有郊游的习惯，在城郊的普雷格尔（Pregel）河畔，河中有两个小岛，七座桥将两个小岛和河岸连接起来，如图所

2、示，问一个人能否从任一小岛出发不重复地走遍七座小桥？第2页/共21页31852年年毕毕业业于于伦伦敦敦大大学学的的弗弗南南西西斯斯格格思思里里发发现现了了一一种种有有趣趣的的现现象象：“看看来来，每每幅幅地地图图都都可可以以用用四四种种颜颜色色着着色色，使使得得有有共共同同边边界界的的国国家家都都被被着着上上不不同同的的颜颜色色。”这这个个现现象象能能不不能能从从数数学学上上加加以以严严格格证明呢？证明呢？四色问题第3页/共21页4Hamilton问题问题 1856年，英国数学家Hamilton设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的

3、问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图。第4页/共21页5图G=,其中(1)V 为顶点集，其元素称为结点（顶点）-用来表示事物(2)E为VV 的多重集。其元素称为边-表示事物间的二元关系(一一)图的定义图的定义:一、图的概念第5页/共21页6(二二)结点与边的关系结点与边的关系:结点与边(不)相 关联：结点与结点结点与结点,边与边边与边(不不)相相邻接邻接一、图的概念(三三)特殊点特殊点孤立点:不与任何结点相邻接的结点悬挂点:只与一条边相关联的结点(四四)特殊的边特殊的边:环:一条边若与两个相同的结点相关联则称为环

4、。多重边(平行边）:与两个结点相关联的边若多于一条，则称这些边为多重边。第6页/共21页7有向图与无向图:简单图与多重图:简单图-不含环与多重边；多重图-含多重边有权图与无权图:b.按边的种类分类：按边的种类分类：有限图与无限图：V与E为有限集合的图叫有限图，否则叫无限图。(n,m)图：有 n 个结点与 m 条边的图。零图:即(n,0)图;平凡图:即(1,0)图。完全图:任意两个结点都相邻接的图。K-正则图:每个结点都与K条边相关联。c.c.按结点集与边集的按结点集与边集的“阶阶”分类分类a a 按边的方向分类按边的方向分类二、图的类型第7页/共21页8注意注意：完全图是完全图是 n n-1

5、1 正则图正则图完全图的每个结点都与其它 n-1 个结点相邻接,即与n-1条边相关联,所以是n-1正则图,反之正则图不一定是完全图。1.完全图：2.正则图：是3正则图 完全图,不是完全图二、图的类型第8页/共21页9子图：子图：设设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,边边集

6、集为为两两端点均在端点均在V V1 1中的全体边构成的子图。中的全体边构成的子图。(4)E E1 1导出的导出子图：E E1 1 E,E,以以E E1 1中中边边关关联联的的顶顶点的全体为顶点集的点的全体为顶点集的G G的子图。的子图。二、图的类型第9页/共21页10abcda1b1abcdd1a1b1c1abcdd1b1abcdd1a1b1c1母母图图真子图真子图V V或E E生成子图生成子图G G且V=V导出子图导出子图V V或E E二、图的类型第10页/共21页11补补 图图 设G=V,E,对于 G1=V,E1 若有 G2=V,EE1是完全图,且 EE1=,则称G1 是 G 的补图。图G

7、 图G1 图G2二、图的类型第11页/共21页12 在无向图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)。三、结点的度数第12页/共21页13在无向图在无向图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的

8、最大度和最小度。的最大度和最小度。在有向图在有向图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)-(G)=mind(G)=mind-(v)|vV(D)(v)|vV(D)分别为分别为D D的最大出度、最小出度、最大入度、最小入的最大出度、最小出度、最大入度、最小入度。简记作度。简记作、+、+、-、-。三、结点的度数第13页/共21页14定理定理1 设设G=

9、为为任意无向图任意无向图，V=v1,v2,vn,|E|=m,则则四、握手定理定理2 设D=为任意有向图，V=v1,v2,vn,|E|=m,则证 G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m 条边共提供 2m 度.第14页/共21页15握手定理推论及应用推论 任何图(无向或有向)中，奇度顶点的个数是偶数.例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.第15页

10、/共21页16五、图的同构定义 设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.第16页/共21页17图同构的必要条件l图之间的同构关系是等价关系.l同构的必要条件：边数相同，顶点数相同;度数列相同;度数相同的结点数目相同第17页/共21页18图同构的实例 (1)(2)(3)(4)图中，(1)与(2)不同构（度数列不同），(3)与(4)也不同构.第18页/共21页19六、图的表示邻接矩阵第19页/共21页20同构判定算法（用邻接矩阵）1、根据图确定其邻接矩阵2、计算行次（矩阵每行的个数-对应于出次）和列次：（对应于入次）3、不考虑出现的次序不同，若行次与列次不同，则必不同构，否则继续 4、同时交换其一矩阵的行和行，列和列。若此矩阵能变成与另一矩阵一样，则同构。对所有顶点的排列都试过，仍不相同，则不同构。邻接矩阵的应用第20页/共21页21感谢您的观看。第21页/共21页