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

,第九章 图的基本概念及其矩阵表示,离散数学 陈志奎主编人民邮电出版社,前言,图论（Graph Theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。,前言,图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有7座桥将河中的岛及岛与河岸联结起来，如下图所示，a、b、c、d表示陆地。从4块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？1736年瑞士大数学家列昂哈德欧拉（Leonhard Euler）解决了这一问题，他用了科学研究中最一般的方法抽象。用四个字母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 的出度（Out Degree），记为；G 中以 v 为终点的边的数目称为 v 的入度（In Degree），记为；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.10 1至5阶完全无向图,24,图的定义,9.1 图的基本概念,定义9.9 定义以下图：（7）设，每个结点的出度和入度均为 n-1的 n 阶简单有向图称为完全有向图，如图9.11。图9.11 1至3阶完全有向图,25,图的定义,显然，完全无向图的任意两个不同结点都邻接，完全有向图的任意两个不同结点之间都有一对方向相反的有向边相连接。,9.1 图的基本概念,定理9.3 n个节点的无向完全图 的边数为。证明：因为在无向完全图 中，任意两个节点之间都有边相连，所以 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.6 n阶图中的基本路径的长度小于或等于。,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 的连通分支(Connected Component)，其个数应为,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，j）元素的值，等于从vi到vj长度为m的路径数目。证明：对于m进行归纳证明。当m=1时，由邻接矩阵A的定义中能够得到A1=A。设矩阵Ak中的元素值是aijk，且对于m=k来说结论为真。因为AK+1=AkA，所以应有 式中，是从结点vi出发，经过结点vk到vj的长度为k+1的各条路径的数目。这里vk是倒数第二个结点。因此，aij应是从结点vi出发，经过任意的倒数第二个结点到vi的长度为k+1的路径总数。因此，对于m=k+1，定理成立。,74,9.4 图的矩阵表示,例9.25 重新考察例9.24中的邻接矩阵A的幂A2，A3，A4和A5。由图9.30不难看出，从结点v1到v3有一条长度为2的路径，因此在矩阵A2中的第一行和第三列上，记上了1。与此类似，从结点v1到v3有一条条长度为5的路径。因此，在矩阵A5中的第一行和第三列上，也记上了1。推论9.2 设A是简单有向图G的邻接矩阵，令 则使 的最小k值，正是 到 的距离,75,9.4 图的矩阵表示,推论9.3 设A是n阶简单有向图G的邻接矩阵，则对，恒成立 当且仅当从 到 是不可达的。推论9.4 令 则存在t，s使 和 当且仅当G中有一条包含 和 的有向回路。定理9.14 及其推论对于无向图也同样有效。特别地，若无向图的邻接矩阵满足推论9.2的条件，则这个无向图必定不是连通图。,76,9.4 图的矩阵表示,给定一个简单有向图G=，如图9.31所示，其中的结点集合V=v1，v2，v3，v4。试求出图G的邻接矩阵A和A的幂A2，A3，A4。解：所要求得到的矩阵如下：从这些矩阵中能够得到一些结论。例如，从结点v1到v4，有3条长度为4的路径。从结点v1到v3的距离d=1。图G中没有长度为3的闭路。,77,9.4 图的矩阵表示,定义9.33 给定一个简单有向图G=，其中，并且假定G中的各结点是有序的。试定义一个nn的路径矩阵（或可达性矩阵）P，使得其元素为 不难看出，路径矩阵P仅表明了图中的任何结点偶对之间是否至少存在一条路径，以及在任何结点上存在循环与否；它并不能指明存在的所有路径。在这种意义上说，与邻接矩阵A不同，路径矩阵并不能给出关于图的完整信息。虽然如此，路径矩阵还是很有用处的。另外，由前述的矩阵B能够求得路径矩阵P。其方法是，如果Bn中的（i，j）元素是非零元素，则选取pij=1，否则pij=0。,78,可达性矩阵,9.4 图的矩阵表示,例9.27 试构成图9.30中的有向图的路径矩阵P。解：设邻接矩阵A=A1。在前面的例9.24中，已经求出过矩阵A的幂A2，A3、A4和A5。所以能够分别求出矩阵B5和路径矩阵P如下。可见图9.30中任何两个结点之间都是相互可达的，这个图也就是一个强连通图。,79,可达性矩阵,9.4 图的矩阵表示,不难看出，首先构成矩阵A，A2，An，而后由他们构成矩阵Bn，再由矩阵Bn构成路径矩阵P，显然是件很麻烦的事。下面将给出另外一种方法，这种方法也是基于类似的原理，但在实际应用中更为方便。对于可达性来说，并不需要讨论从结点vi到vj的任何特定长度的路径数目。然而，在构成邻接矩阵A的幂过程中，得到了这些信息。不过，由于不需要它们，而后又把它隐去了。为了减少计算工作量，应该设法使得这些不必要的信息不产生。采用布尔矩阵（元素或为0或为1的任何矩阵）的运算，就能够达到了上述的目的。给定了一个两元素布尔代数，其中的集合B=0，1。由定义9.33可知，在一个矩阵中，如果所有的元素都是中的元素，则此矩阵都必定是一个布尔矩阵。在表9.1和表9.2中，分别给出了集合B中的运算和运算的定义。,80,可达性矩阵,9.4 图的矩阵表示,对于两个nn的布尔矩阵A和B来说，A和B的布尔和是AB，A和B的布尔积是AB，并分别称为矩阵C和D，它们也都是布尔矩阵。对于所有的i，j=1，2，n来说，试把矩阵C和D的元素分别定义成不难看出，对矩阵A中的第i行从左至右进行扫描，同时对矩阵B中的第j列自上而下进行扫描，并且按公式（2）进行计算，就能够求出所有的元素dij。显然，元素dij=1或者dij=0。,81,可达性矩阵,9.4 图的矩阵表示,可知，邻接矩阵A是个布尔矩阵。路径矩阵P也是个布尔矩阵。能够由邻接矩阵A构成路径矩阵P。对于r=2，3，来说，令AA=A(2)A(r-1)A=A(r)应该注意，矩阵A(2)和A2是不同的。A(2)是个布尔矩阵。如果从结点vi到vj至少有一条长度为2的路径的话，则A(2)中的（i，j）元素值为1；然而在矩阵A2中，（i，j）元素值则表明了从vi到vj长度为2的路径数目。类似的讨论也适用于A(3)和A3以至可以推广到对于任何正整数r的A(r)和Ar。于是，可以把路径矩阵P表示成P=A A(2)A(3)A(k)另外，如果是从k=1到k=n-1进行求和，则又能够得到另外一个矩阵P。在P与P之间如果有区别的话，那么仅是主对角线上的各元素有所不同。,82,可达性矩阵,9.4 图的矩阵表示,例9.28 对于图9.30中的有向图来说，试求出矩阵A(2)，A(3)，A(4)，A(5)和P。解：应有,83,9.4 图的矩阵表示,可以用不同的方法解释矩阵A，A(2)，A(3)，。在简单有向图G=中，应有E VV，因此可以把集合E看成是V中的二元关系。邻接矩阵A是关系E的关系矩阵。在第4章中，曾经把合成关系E。E=E 2定义成这样一种关系：如果存在一个结点Vk，能使viEvk和vkEvj，则必有viE2vj。换句话说，从vi到vj如果至少存在一条长度为2的路径的话，那么E2的关系矩阵中的（i，j）元素值是1。这就说明了，矩阵A(2)是关系E2的关系矩阵。与此类似，A(3)是V中的关系的关系矩阵，A(4)是关系E4的关系矩阵，其余的依此类推。设E1和E2是V中的两种关系，并且A1和A2分别是E1和E2的关系矩阵。于是，关系E1E2和E1 E2的关系矩阵分别是A1A2和A1A2。,84,9.4 图的矩阵表示,显然，可传递闭包E+的关系矩阵应为：A+=A A(2)A(3)式中的A是关系E的关系矩阵。前面曾经说明，如果|V|=n，则图G中的基本路径或基本循环的长度不会超过n。因此，求和到A(n)就能够求得A+，亦即A+=A A(2)A(3)A(N)=p不难看出，矩阵A+与路径矩阵P相同。应该说明，在(3)中如果在加上幂高于n的矩阵，则并不会使A+发生什么变化。计算关系的可传递闭包和简单有向图的路径矩阵，都可以在计算机上进行。由图的邻接矩阵A和路径矩阵P，还能够确定出简单有向图的许多其他性质。例如，能够由路径矩阵P求得含有给定图的任何特定结点的强分图。,85,9.4 图的矩阵表示,例9.29 对于图9.32中的有向图来说，通过矩阵PPT就可以确定其强分图。如果从结点vi到vj是可达的，则显然有pij=1；如果从结点vj到vi是可达的，则应有pji=1或=1。因此，结点vi和vj是相互可达的，当且仅当矩阵PPT中的（i，j）元素值为1。对于所有的j，这个命题都成立，因此上述的命题为真。,86,9.4 图的矩阵表示,定义9.34 设G=（V，E）是一个无环的、至少有一条有向边的有向图，。构造矩阵，其中称M是G的关联矩阵。,87,关联矩阵,9.4 图的矩阵表示,例9.30 图9.33的关联矩阵如下 图9.33,88,关联矩阵,9.4 图的矩阵表示,同邻接矩阵一样，关联矩阵也给出了一个图的全部信息。从定义不难发现：（1）第 i 行中，1的个数是 的出度，-1的个数是 的入度。（2）矩阵中每列都有且仅有一个1和一个-1。（3）若矩阵中有全零元素行，则图有孤立点。（4）若有向图G 的结点和边在一种编号（定序）下的关联矩阵是，在另一种编号下的关联矩阵是，则必存在置换阵P 和Q，使,89,关联矩阵,9.4 图的矩阵表示,定理9.15 设G是n阶连通无环的的有向图，其关联矩阵是M，则M的秩是n-1。定义9.35 设G=（V，E）是至少有一边的无环图，。构造矩阵，其中称M为G的关联矩阵。这个矩阵通常看作 矩阵加以研究。同有向图的情形一样，可以证明n阶无环连通图，其关联矩阵的秩是n-1。,90,关联矩阵,91,谢谢！,