离散数学第九章图的基本概念及其矩阵表示.ppt

,第九章图的基本概念及其矩阵表示,离散数学陈志奎主编人民邮电出版社,前言,图论（GraphTheory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。,前言,图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有7座桥将河中的岛及岛与河岸联结起来，如下图所示，a、b、c、d表示陆地。从4块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？1736年瑞士大数学家列昂哈德欧拉（LeonhardEuler）解决了这一问题，他用了科学研究中最一般的方法抽象。用四个字母a，b，c，d表示4块陆地，并用7条线表示7座桥，从而将七桥问题抽象为图的问题，寻找经过图中每边一次且仅一次的回路，后来人们把有这样回路的图称为欧拉图。,图论的起源,前言,图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。图论部分共分为三章：图的基本概念及其矩阵表示，几种图的介绍，树。,图论的起源,图的基本概念,主要内容,子图和图的运算,路径、回路和连通性,图的矩阵表示,9.1图的基本概念,图是用于描述现实世界中离散客体之间关系的有用工具。在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。同样的方法也可以用来描述其他的问题。当我们考察交通路线时，可以用点来代表城市，用线来表示两城市间有道路通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道。在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。从图的这种表示方式中可以抽象出图的数学概念来。,6,图的定义,9.1图的基本概念,定义9.1设一个三元组，其中是一个非空的节点集合，是有限的边集合，如果是从边集合E到点集合V中的无序偶映射，即，则称为无向图。在无向图中，如果，则称e连接和，和既是e的起点，也是e的终点，也称和为点邻接。如果两条不同的边和与同一个结点连接，则称和为边邻接。,7,图的定义,9.1图的基本概念,定义9.1设一个三元组，其中是一个非空的节点集合，是有限的边集合，如果是从边集合E到点集合V中的有序偶映射，即，则称为无向图。在有向图中，如果，则称e连接和，分别称和是e的起点和终点，也称和邻接。,8,图的定义,9.1图的基本概念,无论是无向图还是有向图，都统称为图，其中V的元素称为图G的结点，E的元素称为图G的边，图G的结点数目称为图的阶。我们可以用几何图形表示上面定义的图。用小圆圈表示结点。在无向图中，若，就用连接结点和的无向线段表示边g。在有向图中，若，就用指向的有向线段表示边e。,9,图的定义,9.1图的基本概念,例9.1无向图和有向图分别示于图9.1和图9.2。在图9.1中，连接和，和邻接，和邻接。在图9.2中，和分别是的起点和终点，与邻接。,10,图9.1,图9.2,9.1图的基本概念,定义9.3设图，e1和e2是G的两条不同的边。（1）如果与e1连接的两个结点相同，则称e1为自回路或环。（2）如果，则称e1与e2平行。（3）如果图G没有自回路，也没有平行边，则称G为简单图。（4）如果图G没有自回路，有平行边，则称G为多重边图。（5）如果图G既有自回路，又有平行边，则称G为伪图。,11,在有向图中，如果两条边连接的结点相同，但方向相反，它们也不是平行边。,9.1图的基本概念,12,例9.2中国主要城市通讯图如图9.3所示：当数据量很小时，可采用单线通讯如图（a）所示；数据量很大时，两点之间往往要连接多条线路如图（b）所示。为了诊断本地故障也可采用自环连接如图（c）所示；有时数据可以不是双向传输，沈阳只接收数据不发送数据如图（d）所示（有向图允许有自环）；数据量大时也可采用多重有向图如图（e）所示。,9.1图的基本概念,简单图是一类非常重要的图。在某些图论著作中，把我们定义的简单图称为图，而把允许有平行边的图称为多重边图，把我们定义的图称为伪图。从图的定义可以看出，图的最本质的内容是结点和边的关联关系。两个表面上看起来不同的图，可能表达了相同的结点和边的关联关系。如图9.4的两个图，不仅结点和边的数目相同，而且结点和边的关联关系也相同。为了说明这种现象，我们引进两个图同构的概念。,13,9.1图的基本概念,定义9.4设图和。如果存在双射和双射，使得对于任意的，都满足则称G与同构，记作，并称f和g为G和之间的同构映射，简称同构。两个同构的图有同样多的结点和边，并且映射保持结点间的邻接关系，映射保持边之间的邻接关系。,14,同构映射,9.1图的基本概念,定义9.5设。（1）如果G是无向图，G中与v关联的边和与v关联的自回路的数目之和称为v的度（Degree），记为。（2）如果G是有向图，G中以v为起点的边的数目称为v的出度（OutDegree），记为；G中以v为终点的边的数目称为v的入度（InDegree），记为；v的出度与入度之和称为v的度（Degree），记为，显然=,15,节点的度,在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。,9.1图的基本概念,例9.3在图9.5所示的无向图中，。在图9.6所示的有向图D中，1，图9.5图9.6显然，每增加一条边，都使图中所有结点的度数之和增加2。,16,9.1图的基本概念,定理9.1在无向图中，所有节点的度数之和等于边数的2倍。证明：因为每条边（包括环）给图带来两度，图有m条边，所以图共有2m度，等于图的所有结点的度数之和。定理9.2在有向图中，所有顶点的度数之和等于边的2倍；所有顶点的入度之和等于所有节点的出度之和，都等于边数。证明：因为每条边（包括环）给图带来两度（一个出度和一个入度），图有m条边，所以图共有2m度（m个入度和m个出度），等于图的所有结点的度数之和。,17,9.1图的基本概念,18,9.1图的基本概念,定义9.6度数为奇数的结点称为奇结点，度数为偶数的结点称为偶结点。推论9.1任何图都有偶数个奇结点。证明：设，则因为是偶数，所以也是偶数，而中每个点v的度均为奇数，因此为偶数。,19,9.1图的基本概念,定义9.7设是图的结点集，称为G的度序列。如图9.5的度序列为3,4,4,1,0，图9.6的度序列是3,4,3,2。定义9.8度为0的结点称为孤立结点，度为1的结点称为端点。,20,9.1图的基本概念,定义9.9定义以下图：（1）结点都是孤立结点的图称为零图。（2）一阶零图称为平凡图。（3）由n个顶点v1,v2,vn(n3)以及边v1,v2,v2,v3,vn-1,vn,vn,v1组成的图（Cn）称为圈图，如图9.7。,21,图的定义,图9.7圈图,9.1图的基本概念,定义9.9定义以下图：（4）对n来说，当给圈图Cn添加一个顶点，并且把这个新顶点与Cn里的n个顶点逐个连接，可以得到轮图（Wn），如图9.8。图9.8轮图,22,图的定义,9.1图的基本概念,定义9.9定义以下图：（5）所有结点的度均为自然数的无向图称为度正则图，如图9.9。3度、4度正则图,23,图的定义,9.1图的基本概念,定义9.9定义以下图：（6）设，如果n阶简单无向图G是n-1度正则图，则称G为完全无向图，记为。如图9.10。图9.101至5阶完全无向图,24,图的定义,9.1图的基本概念,定义9.9定义以下图：（7）设，每个结点的出度和入度均为n-1的n阶简单有向图称为完全有向图，如图9.11。图9.111至3阶完全有向图,25,图的定义,显然，完全无向图的任意两个不同结点都邻接，完全有向图的任意两个不同结点之间都有一对方向相反的有向边相连接。,9.1图的基本概念,定理9.3n个节点的无向完全图的边数为。证明：因为在无向完全图中，任意两个节点之间都有边相连，所以n个节点中任取两个点的组合数为，故无向完全图的边数为。如果在中，对每条边任意确定一个方向，就称该图为n个节点的有向完全图。显然，有向完全图的边数也是。,26,图的基本概念,主要内容,子图和图的运算,路径、回路和连通性,图的矩阵表示,9.2子图和图的运算,定义9.10设和为图。（1）如果，则称是G的子图，记作，并称G是的母图。（2）如果，则称是G的真子图，记作（3）如果，则称是G的生成子图。,28,子图和补图,9.2子图和图的运算,定义9.11设图，且。以为结点集合，以起点和终点均在中的边的全体为边集合的G的子图，称为由导出的G的子图，记为。若，导出子图，记为。是从G中去掉中的结点以及与这些结点关联的边而得到的图G的子图。,29,子图和补图,9.2子图和图的运算,定义9.11设图，且，以为结点集合，以为边集合的G的子图称为由导出的子图。显然，从图示看，图G的子图是图G的一部分，G的真子图的边数比G的边数少，G的生成子图与G有相同的结点，G的导出子图是G的以为结点集合的最大子图。,30,子图和补图,9.2子图和图的运算,例9.5在图9.12中，图(b)是图(a)的子图、真子图和生成子图，图(c)是图(a)的由1,2,3,4导出的子图。图9.12图和子图,31,子图和补图,9.2子图和图的运算,定义9.13设n阶无向图是n阶完全无向图的生成子图，则称为G的补图，记为。显然，简单无向图都有补图，并且一个简单无向图的每个补图都是同构的。对于任意两个简单无向图和，如果是的补图，那么也是的补图。例如，在图9.13中(a)和(b)互为补图。,32,子图和补图,图9.13互补的图,9.2子图和图的运算,定义9.14设图和同为无向图或同为有向图。（1）如果对于任意具有，则称G和是可运算的。（2）如果，则称G和是不相交的。（3）如果，则称G和是边不相交的。,33,子图和补图,9.2子图和图的运算,定义9.15设图和为可运算的。（1）称以为结点集合，以为边集合的和的公共子图为和的交，记为（2）称以为结点集合，以为边集合的和的公共母图为和的并，记为。（3）称以为结点集合，以为边集合的的子图为和的环和，记为,34,子图和补图,9.2子图和图的运算,例9.6在图9.14中，(a)和(b)分别为和，则图c、d、e分别是、和,35,子图和补图,9.2子图和图的运算,定理9.4设图和为可运算的。（1）如果，则存在唯一的（2）存在唯一的和图9.15不可运算的图,36,子图和补图,9.2子图和图的运算,定义9.16设图，记为，对任意，记为是从G中去掉中的边所得到的G的子图。定义9.17设图和同为无向图或同为有向图，并且边不相交，记为是由G增加中的边所得到的图，其中指出中的边与结点的关联关系。,37,子图和补图,9.2子图和图的运算,例9.7设图9.16中的(a)和(b)分别为和，则(c)，(d)，(e)分别是，其中，,38,子图和补图,9.2子图和图的运算,例9.7设图9.16中的(a)和(b)分别为和，则(c)，(d)，(e)分别是，其中，,39,子图和补图,图的基本概念,主要内容,子图和图的运算,路径、回路和连通性,图的矩阵表示,9.3路径、回路和连通性,计算机网络中常见的一个问题是网络中任何两台计算机是否可以通过计算机间的信息传递而使其资源共享？我们可以用图论的方法对这个问题进行研究，其中用结点表示计算机，用边表示通讯连线，因此，计算机的信息资源共享问题就变为图中任何两个结点之间是否都有连接路径存在？,41,9.3路径、回路和连通性,定义9.18设是图，从图中结点到的一条路径或通路是图的一个点、边的交错序列，其中(或者),分别称为通路的起点和终点，路径中包含的边数n称为路径的长度,当起点和终点重合时则称其为闭路径。在上述定义路径与回路中，节点和边不受限制，即节点和边都可以重复出现。下面我们讨论路径与回路中节点和边受限的情况。,42,9.3路径、回路和连通性,定义9.19如果中出现的边互不相同，则称该路径为简单路径。闭的简单路径称为回路。如果出现的点互不相同，则称该路径是基本路径。基本路径中除了起点和终点相同外，别无相同的结点，则称为圈。例9.8在图9.17所示的无向图中，是路径，但不是简单路径；是简单路径，但不是基本路径；是闭路径，但不是简单闭路径。,43,9.3路径、回路和连通性,例9.9在图9.18所示的有向图中，是路径，但不是简单路径；是简单路径，但不是基本路径。从中去掉闭路径就得到基本路径。可以看出，从3至1存在多条路径，从1至3也存在多条路径。由路径的定义知道，单独一个结点v也是路径，它是长度为0的基本路径。因此，任何结点到其自身总存在路径。在无向图中，若从结点v至结点v存在路径，则从v至v必存在路径。而在有向图中，从结点v至结点v存在路径，而从v至v却不一定存在路径。,44,9.3路径、回路和连通性,例9.10“摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？解：河左岸允许出现的情况有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）之间画一直线，得到图9.19。,45,摆渡问题,9.3路径、回路和连通性,定理9.5设v和v是图G中的结点。如果存在从v至v的路径，则存在从v至v的基本路径。,46,9.3路径、回路和连通性,定理9.6n阶图中的基本路径的长度小于或等于。,47,9.3路径、回路和连通性,定理9.7设v是图G的任意结点，G是回路或有向回路，当且仅当G的阶与边数相等，并且在G中存在这样一条从v到v的闭路径，使得除了v在该闭路径中出现两次外，其余结点和每条边都在该闭路径上恰出现一次。,48,9.3路径、回路和连通性,定义9.20如果回路（有向回路，无向回路）C是图G的子图，则称G有回路（有向回路，无向回路）C。定理9.8如果有向图G有子图G满足：对于G的任意结点v，则G有有向回路。,49,9.3路径、回路和连通性,定理9.9如果有向图G有子图G满足：对于G中的任意结点v，则G有有向回路。例9.11为判断图9.20的(a)有没有有向回路，我们依次得到图9.20的。由(g)是平凡图知(a)没有有向回路。(a)不是非循环图，因为它的所有结点的度均大于1。,50,9.3路径、回路和连通性,定义9.21设v1和v2是图G的结点。如果在G中存在从v1至v2的路径，则称在G中从v1可达v2或v1和v2是连通的，否则称在G中从v1不可达v2。对于图G的结点v，我们用R(v)表示从v可达的全体结点的集合。在无向图中，若从v1可达v2，则从v2必可达v1；而在有向图中，从v1可达v2不能保证从v2必可达v1。无论无向图还是有向图，任何节点到自身都是可达的。,51,9.3路径、回路和连通性,例9.12在图9.20所示的无向图中，存在路径v1av2bv3所以v1可达v3，v3也可达v1，从v1可达的全体节点的集合=,52,9.3路径、回路和连通性,例9.13在图9.22所示的有向图中，存在路径所以1可达4。从2可达的全体节点的集合=,53,9.3路径、回路和连通性,定义9.22设v1和v2是图G的结点。如果从v1至v2是可达的，则在从v1至v2的路径中，长度最短的称为从v1至v2的测地线，并称该测地线的长度为从v1至v2的距离，记作。如果从v1不可达v2，则称从v1至v2的距离为应该说明，对于任何结点来说，总是假定，另外，从结点vi至vj的距离具有下列性质。对于任何结点来来说，都应有（1）（2）（3）不等式（3），通常称为三角不等式，如果结点vi到vj是可达的，并且从vj到vi也是可达的，但是却不一定等于，这一点读者应予注意。,54,9.3路径、回路和连通性,定义9.23图的直径定义为例9.14在图9.23所示的有向图中，=1，=1，=1，=2。+，且,55,9.3路径、回路和连通性,定义9.24设图，其中R+是正实数集合，则称为加权图。对任意称为边e的加权长度。路径中所有边的加权长度之和称为该路径的加权长度。从结点至的路径中，加权长度最小的称为从至的最短路径。若从可达,则称从至最短路径的加权长度为从至加权距离；若从不可达，则称从至的加权距离为在图论的实际应用中，常常需要从一结点至另一结点的加权距离。图的连通性分为无向图的连通性和有向图的连通性。而且有向图的连通性要比无向图的连通性复杂些。下面讨论图的重要性质连通性。,56,9.3路径、回路和连通性,定义9.25若无向图G中任意两个结点都可达的，则称G是连通的。规定平凡图是连通的。显然，无向图是连通的，当且仅当对于任意，易知，无向图G中，结点之间的连通关系是等价关系。设G为一无向图，R是中结点之间的连通关系，由R可将划分成个等价类，记作，由它们导出的导出子图称为G的连通分支(ConnectedComponent)，其个数应为,57,9.3路径、回路和连通性,例9.16图9.25所示的（a）为无向连通图，=1。（b）为无向非连通图，=3。图9.25无向图由于可达性的非对称性，有向图的连通概念要复杂得多，这里需要用到基础图的概念。,58,9.3路径、回路和连通性,定义9.26设有向图，若略去G中各有向边的方向后得到无向图D，则称D为有向图G的基础图。例9.17图9.26所示，有向图（a）的基础图为无向图（b）。图9.26基础图,59,9.3路径、回路和连通性,定义9.27设G是有向图。（1）如果G的基础图是连通的，则称G是弱连通的。（2）如果对于G的任意两结点，必有一个结点可达另一个结点，则称G是单向连通的。（3）如果G中任意两个结点都互相可达，则称G是强连通的。例9.18图9.27给出了三个有向图，其中（a）是强连通的，（b）是单向连通的，（c）是弱连通的。,60,9.3路径、回路和连通性,定义9.28设G是G的具有某种性质的子图，并且对于G的具有该性质的任意子图G，只要，就有，则称相对于该性质是G的极大子图。定义9.29无向图G的极大连通子图称为G的分支。定义9.30设G是有向图。（1）G的极大弱连通子图称为G的弱分支。（2）G的极大单向连通子图称为G的单向分支。（3）G的极大强连通子图称为G的强分支。,61,9.3路径、回路和连通性,定理9.10连通无向图恰有一个分支。非连通无向图有一个以上分支。定理9.11强连通（单向连通，弱连通）有向图恰有一个强分支（单向分支，弱分支）；非强连通（非单向连通，非弱连通）有向图有一个以上强分支（单向分支，弱分支）。,62,9.3路径、回路和连通性,定义9.31设是一个无向图，（1）如果从图G中删去结点v（及相关联的边）后得到的子图的连通分支数多于原图的连通分支数，即,则称v是图G的一个割点。（2）如果，则称e为图G的一个割边或桥。显然，从连通图中删去一个割点或割边后得到的子图是不连通的。,63,9.3路径、回路和连通性,定理9.12在图G中e是割边，当且仅当e不在任何回路上。例9.20图9.29中，是割点，都是割边。,64,图的基本概念,主要内容,子图和图的运算,路径、回路和连通性,图的矩阵表示,9.4图的矩阵表示,一个图可以按定义描述出来，也可以用图形表示出来，还可以同二元关系一样，用矩阵来表示。图用矩阵表示有很多优点，既便于利用代表知识研究图的性质、构造算法，也便于计算机处理。图的矩阵表示常用的有两种形式：邻接矩阵和关联矩阵。邻接矩阵常用于研究图的各种道路的问题，关联矩阵常用于研究子图的问题。由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，需将图的结点和边加以编号（定序），以确定与矩阵元素的对应关系。,66,9.4图的矩阵表示,定义9.32设G=是一个简单有向图，其中的结点集合V=v1，v2，vn，并且假定各结点已经有了从结点v1到vn的次序。试定义一个nn的矩阵A，使得其中的元素则称这样的矩阵A是图G的邻接矩阵。这个定义也适用于无向图，只需把其中的有向表示换成无向表示。,67,邻接矩阵,9.4图的矩阵表示,例9.21在图9.30中，给出了一个有向图。首先给各结点安排好一个次序，譬如说是v1，v2，v3，v4，v5。于是，能够写出给定有向图的邻接矩阵如下。在矩阵A的第一行上有一个1，在第一列上有2个1，因此结点v1的出度和入度应分别为1和2。在第二行上有一个1，在第二列上也有3个1，因此结点v2的出度为1，入度为3。第三行和第三列以及第四行和第四列上1的个数，都和前面的解释意义相同。,68,邻接矩阵,9.4图的矩阵表示,显然，当改变图的结点编号顺序时，可以得到图的不同的邻接矩阵，这相当于对一个矩阵进行相应行列的交换得到新的邻接矩阵。例如对图9.30的结点重新定序，使v1与v5对换，则得到新的邻接矩阵A给定两个有向图和相对应的邻接矩阵，如果首先在一个图的邻接矩阵中交换一些行，而后交换相对应的各列，从而有一个图的邻接矩阵，能够求得另外一个图的邻接矩阵，则事实上这样的两个有向图，必定是互为同构的。,69,邻接矩阵,9.4图的矩阵表示,从给定的简单有向图的邻接矩阵中，能够直接判定出它的某些性质。如果有向图是自反的，则邻接矩阵的主对角线上的各元素，必定都是1。如果有向图是反自反的，则邻接矩阵的主对角线上的各元素，必定都是0。对于对称的有向图来说，其邻接矩阵也是对称的，也就说，对于所有的i和j而言，都应有aij=aji。与此类似，如果给定有向图是反对称的，则对于所有的i和j和ij而言，aij=1蕴涵aji=0。可以把简单有向图的矩阵表示的概念，推广到简单无向图、多重边图和加权图。对于简单无向图来说，这种推广会给出一个对称的邻接矩阵。在多重边图或加权图的情况下，可以令其中的wij，或者是边的重数，或者是边的权。另外，若，则wij=0。,70,邻接矩阵,9.4图的矩阵表示,在零图的邻接矩阵中，所有元素都应该是0，亦即其邻接矩阵是个零矩阵。如果给定图中的每个结点上都有闭路，而且又没有其他的边存在，则其邻接矩阵是个单位矩阵。如果给定的图G=是一个简单有向图，并且其邻接矩阵是A，则图G的逆图G的邻接矩阵是A的转置AT。对于无向图或者对称的有向图来说，应有AT=A。下面就来定义矩阵B=AAT。设aij是邻接矩阵A中的第i行和第j列上的（i，j）元素，bij是矩阵B中的第i行和第j列上的（i，j）元素。于是，对于i，j=1，2，3，n来说，有,71,邻接矩阵,9.4图的矩阵表示,在零图的邻接矩阵中，所有元素都应该是0，亦即其邻接矩阵是个零矩阵。如果给定图中的每个结点上都有闭路，而且又没有其他的边存在，则其邻接矩阵是个单位矩阵。如果给定的图G=是一个简单有向图，并且其邻接矩阵是A，则图G的逆图G的邻接矩阵是A的转置AT。对于无向图或者对称的有向图来说，应有AT=A。下面就来定义矩阵B=AAT。设aij是邻接矩阵A中的第i行和第j列上的（i，j）元素，bij是矩阵B中的第i行和第j列上的（i，j）元素。于是，对于i，j=1，2，3，n来说，有,72,邻接矩阵,9.4图的矩阵表示,例9.24对于例9.21中的图9.30来说，根据上述的定义能够求得从这些矩阵可以知道图中存在两条从到的长度为2的有向道路，不存在从到自身的长度为2或3的有向回路，但是存在从到自身的两条长度为4的有向回路和一条长度为5的有向回路等等。,73,9.4图的矩阵表示,定理9.13设G=是一个n阶简单有向图，A是G的邻接矩阵。对于m=1，2，3，来说，矩阵Am中的（i