图的基本概念汇总课件

1、图论绪10/11/20221图论绪10/10/20221图论绪图形可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。 10/11/20222图论绪图形可直观地表示离散对象之间的相互关系，研究它们的共性7.1 无向图及有向图一个图是由一些结点和连接两个结点之间的连线（即边）所组成的，与连线的长度及结点的位置无关此两图是相同的，因为点与边的对应关系相同10/11/202237.1 无向图及有向图一个图是由一些结点和连接两个结点之间的 图论中的一些概念边顶点中的元素称为顶点，用带标记的点表示，也称为结点。10/11/20224 图论中的一些概念边顶点10/10/202241

2、0/11/2022510/10/2022510/11/2022610/10/20226定理7-1.2 在任何图中度数为奇数的结点必定是偶数个。定理7-1.3 在任何有向图中，所有结点的入度之和等于所有结点的出度之和，且等于边数。 10/11/20227定理7-1.2 在任何图中度数为奇数的结点必定是偶数个。定10/11/2022810/10/20228例 证明：在任意六个人的集会上，要么有三人似曾相识，要么有三人不曾相识。10/11/20229例 证明：在任意六个人的集会上，要么有三人似曾相识，10/10/11/20221010/10/20221010/11/20221110/10/20221

3、1两图同构的必要条件（非充分）1、结点数相同2、边数相同3、度数相同的结点数相同10/11/202212两图同构的必要条件（非充分）10/10/2022127.2通路、回路、图的连通性 通路 中相邻边的序列（0，1），（1，2），（k-1，k）称为一条通路。此通路的长度为。也可以用（0，1，k）表示通路，0为起点，k为终点。 当0=k时，该通路称为回路。10/11/2022137.2通路、回路、图的连通性 通路10/10/202213简单通路 一条通路中没有两条边是相同的，称此通路为简单通路（迹）。当其是回路时，称为简单回路。初级通路 一条通路中，除了起点和终点可以相同，没有其他相同顶点出现，

4、称此通路为初级通路（基本通路或路径）。当其是回路时，称为初级回路（基本回路或圈）。7.2通路、回路、图的连通性10/11/202214简单通路初级通路7.2通路、回路、图的连通性10/10/20（5，1 ，2 ，3，4）是简单通路，不是初级通路，因为（，）中出现了两次。但（c，d，b，c）是初级回路。7.2通路、回路、图的连通性10/11/202215（5，1 ，2 ，3，4）是简单通路，不是初级通路7.2通路、回路、图的连通性10/11/2022167.2通路、回路、图的连通性10/10/202216连通性 设（，）， （0，1，k） 是G中的一条通路，则称0到k连通或可达。说明：对无向图而

5、言，若0到k可达，则k到0也可达。对有向图而言则未必。7.2通路、回路、图的连通性10/11/202217连通性7.2通路、回路、图的连通性10/10/202217连通分支 无向图可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为的连通分支。无向图的连通性 若（，）中任两个顶点都连通，则称此无向图是连通的。7.2通路、回路、图的连通性任意一个连通无向图的任两个不同顶点都存在一条简单通路。10/11/202218连通分支无向图的连通性7.2通路、回路、图的连通性任意一个连有向图的连通性(1)弱连通： 若（，）对应的无向图是连通图，则称为弱连通。(2）强连通： 若（，）中任两点间都有

6、路，即对与，到可达，到可达，称为强连通。 7.2通路、回路、图的连通性10/11/202219有向图的连通性7.2通路、回路、图的连通性10/10/2027.2通路、回路、图的连通性10/11/2022207.2通路、回路、图的连通性10/10/2022207.3 图的矩阵表示1.无向图的关联矩阵设无向图G=,为顶点与边的关联次数,则称矩阵为G的关联矩阵,记为M(G).显然,的可能取值为0(与不关联),1(与关联1次),2(与关联2次)即的以为端点的环.10/11/2022217.3 图的矩阵表示1.无向图的关联矩阵设无向图G=V,E7.3图的矩阵表示从关联矩阵中得到下列性质1、（第i行元素之

7、和为的度数）2、，当且仅当为孤立点。3、若第j列与第k列相同，则说明与为平行边。10/11/2022227.3图的矩阵表示从关联矩阵中得到下列性质1、（第i行元素之7.3图的矩阵表示2.有向图的关联矩阵若有向图D中无环存在,设D=,令则称为D的关联矩阵,记为M(D)10/11/2022237.3图的矩阵表示2.有向图的关联矩阵若有向图D中无环存在,7.3图的矩阵表示从关联矩阵中得到下面性质10/11/2022247.3图的矩阵表示从关联矩阵中得到下面性质10/10/2027.3图的矩阵表示 10/11/2022257.3图的矩阵表示 10/10/202225由邻接矩阵可以看出1、图中是否有环2、图是否是零图或完全图3、每行元素之和即为此行对应结点的出度，每列元素之和即为此列对应结点的入度。10/11/202226由邻接矩阵可以看出10/10/2022267.3图的矩阵表示 4、若两结点通过其他点中转，也有可能连通。作邻接矩阵的普通矩阵乘法：ij的值表示i到j路长为的道路条数10/11/2022277.3图的矩阵表示 4、若两结点通过其他点中转，也有可能连通7.3图的矩阵表示 定理 m的元素ij表示i到j长度为的道路的条数。10/11/2022287.3图的矩阵表示 定理 m的元素ij表示i到j长度10/