图的基本概念汇总课件.ppt

1、12/30/20221图形可直观地表示离散对象之间的相互关系，研图形可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。究它们的共性和特性，以便解决具体问题。12/30/20222一个图是由一些结点和连接两个结点之间的连线（即边）一个图是由一些结点和连接两个结点之间的连线（即边）所组成的，与连线的长度及结点的位置无关所组成的，与连线的长度及结点的位置无关abcd1e2e4e5e3e6eabcd1e2e3e4e5e6e此两图是相同的，因为点与边的对应关系相同,Va b c d 123456,(,),(,),(,),(,),(,),(,)Ee e e e e ea ba c

2、a db cb dc d12/30/20223边边,jkkjv vv v,jkkjv vv v顶点顶点中的元素称为中的元素称为顶点顶点，用带标记的点表示，也称为，用带标记的点表示，也称为结点结点。12/30/2022412/30/2022512/30/20226定理定理7-1.2 在任何图中度数为奇数的结点必定是偶数个。在任何图中度数为奇数的结点必定是偶数个。定理定理7-1.3 在任何有向图中，所有结点的入度之和等于在任何有向图中，所有结点的入度之和等于所有结点的出度之和，且等于边数。所有结点的出度之和，且等于边数。12/30/2022712/30/20228例例 证明：在任意六个人的集会上，

3、要么有三人似曾相识，证明：在任意六个人的集会上，要么有三人似曾相识，要么有三人不曾相识。要么有三人不曾相识。12/30/2022921(1)2nCn n121nn12/30/202210a d c b 无 向 图 b (c)a (b)c (a)d12/30/202211两图同构的必要条件（非充分）两图同构的必要条件（非充分）1、结点数相同、结点数相同2、边数相同、边数相同3、度数相同的结点数相同、度数相同的结点数相同12/30/202212通路通路 中相邻边的序列（中相邻边的序列（0 0，1 1），（），（1 1，2 2），），（k-1k-1，k k）称为一条称为一条通路通路。此通路的长度为。

4、也可以。此通路的长度为。也可以用（用（0，1，k）表示通路，表示通路，0为起点，为起点，k为终为终点。点。当当0 0=k时，该通路称为时，该通路称为回路回路。12/30/202213简单通路简单通路 一条通路中没有两条边是相同的，称此通路为一条通路中没有两条边是相同的，称此通路为简单通路（迹）简单通路（迹）。当其是回路时，称为。当其是回路时，称为简单回路简单回路。初级通路初级通路 一条通路中，除了起点和终点可以相同，没有一条通路中，除了起点和终点可以相同，没有其他相同顶点出现，称此通路为其他相同顶点出现，称此通路为初级通路（基本通初级通路（基本通路或路径）路或路径）。当其是回路时，称为。当其是

5、回路时，称为初级回路（基本初级回路（基本回路或圈）。回路或圈）。12/30/202214e3e5e2e1dcbae4（5，1，2，3，4）是简单通路，不是初）是简单通路，不是初级级通通路，因为（，）中出路，因为（，）中出现了两次。但（现了两次。但（c，d，b，c）是初级回路。是初级回路。12/30/20221512/30/202216连通性连通性 设（，），设（，），（0，1，k）是是G中的一条中的一条通通路，则称路，则称0到到k连通连通或或可达可达。说明：对无向图而言，若说明：对无向图而言，若0到到k可达，则可达，则k到到0也也可达。对有向图而言则未必。可达。对有向图而言则未必。12/30/

6、202217连通分支连通分支 无向图可分为几个不相连通的子图，每一子图无向图可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为的本身都是连通的。称这几个子图为的连通分支连通分支。无向图的连通性无向图的连通性 若（，）中任两个顶点都连通，则称若（，）中任两个顶点都连通，则称此无向图是此无向图是连通的连通的。任意一个连通无向图的任两个不同顶点都存在一条简单通路。12/30/202218有向图的连通性有向图的连通性(1)(1)弱连通：弱连通：若（，）对应的无向图是连通图，则称若（，）对应的无向图是连通图，则称为为弱连通弱连通。(2(2）强连通：强连通：若（，）中任两点间都有路，即对与若

7、（，）中任两点间都有路，即对与，到可达，到可达，称为，到可达，到可达，称为强连通强连通。12/30/202219 连连通通无无向向图图:弱弱连连通通 强强连连通通:12/30/2022201.无向图的无向图的关联矩阵关联矩阵设无向图G=,je1212,nmijVv vvEe eem为顶点iv与边的关联次数,则称矩阵()ijn mm为G的关联矩阵,记为M(G).显然,ijm的可能取值为0(iv与je不关联),1(iv与je关联1次),2(iv与je关联2次)即je的以iv为端点的环.1v2v3v1e2e3e4e5e4v1110001110()1001200000M G12/30/202221从关

8、联矩阵中得到下列性质从关联矩阵中得到下列性质1、1()mijijmd v（第（第i行元素之和为行元素之和为iv的度数）的度数）2、10nijjm，当且仅当，当且仅当iv为孤立点。为孤立点。3、若第、若第j列与第列与第k列相同，则说明列相同，则说明je与ke为平行边。为平行边。12/30/2022221212,nmVv vvEe ee()ijn mm2.有向图的有向图的关联矩阵关联矩阵若有向图若有向图D中无环存在中无环存在,设设D=,令令1,0ijijijijvemveve为 的始点，与 不关联-1，为 的终点则称为D的关联矩阵,记为M(D)1v1e2v3v4v2e3e4e5e110001011

9、1()0000101110M G12/30/202223从关联矩阵中得到下面性质从关联矩阵中得到下面性质11(1)(),(1)()mmijiijijjmdvmdv 12/30/2022241v2v3v4v12100010()00010010A G12/30/202225由邻接矩阵可以看出由邻接矩阵可以看出1、图中是否有环、图中是否有环2、图是否是零图或完全图、图是否是零图或完全图3、每行元素之和即为此行对应结点的出度，每列、每行元素之和即为此行对应结点的出度，每列元素之和即为此列对应结点的入度。元素之和即为此列对应结点的入度。12/30/2022264、若两结点通过其他点中转，也有可能连通。作

10、、若两结点通过其他点中转，也有可能连通。作邻接矩阵的普通矩阵乘法：邻接矩阵的普通矩阵乘法：ijij的值表示的值表示i i到到j j路长为的道路条数路长为的道路条数21ijn nnijikkjkBAA Abba a12/30/202227定理定理 m m的元素的元素ijij表示表示i i到到j j长度为长度为的道路的条数。的道路的条数。12/30/20222812/30/202229个顶点的图中，个顶点的图中，A A是是G G的邻接矩阵。的邻接矩阵。可达性矩阵可达性矩阵 B=B=A+AA+A2 2+A+An-1 n-1+A+An n，B B的元素非的元素非0 0数改成数改成1 1即得即得邻接矩阵与可达矩阵的关系邻接矩阵与可达矩阵的关系12/30/202230