图的基本概念及其矩阵表.ppt

离散数学大连理工大学软件学院陈志奎 2 128 第9章图的基本概念及其矩阵表示论 3 128 图论 GraphTheory 是数学的一个分支 它以图为研究对象 图论中的图是由若干给定的点及连接两点的线所构成的图形 这种图形通常用来描述某些事物之间的某种特定关系 用点代表事物 用连接两点的线表示相应两个事物间具有这种关系 图论起源于著名的柯尼斯堡七桥问题 在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来 如下图所示 A B C D表示陆地 4 128 图论的起源 哥尼斯堡七桥问题 17世纪的东普鲁士有一座哥尼斯堡 Konigsberg 城 城中有一条普雷格尔 Pregel 河 全城共有七座桥将河中的岛及岛与河岸联结起来 如下图所示 a b c d表示陆地 从四块陆地的任何一块出发 怎样通过且仅通过每座桥一次 最终回到出发地点 5 128 图论的起源 1736年瑞士大数学家列昂哈德 欧拉 LeonhardEuler 解决了这一问题 他用了科学研究中最一般的方法 抽象 用四个字母a b c d表示四块陆地 并用7条线表示7座桥 从而将七桥问题抽象为图的问题 寻找经过图中每边一次且仅一次的回路 后来人们把有这样回路的图称为欧拉图 6 128 图论的起源 欧拉证明了这个问题没有解 并且推广了这个问题 给出了对于一个给定的图可以某种方式走遍的判定法则 这项工作使欧拉成为图论的创始人 欧拉被称为图论之父 1736年也被称为 图论元年 图论部分共分为三章 图的基本概念及其矩阵表示 几种图的介绍 树 本章将首先讨论图论中的一些基本概念 继之阐述图的基本性质 而后介绍图的矩阵表示方法 7 128 主要内容 图的基本概念子图和图的运算路径 回路 连通性图的矩阵表示欧拉图哈密尔顿图二部图 平面图网络树 基础知识 特殊图 8 128 9 1图的基本概念 图是由一些顶点和连接这些顶点的一些边所组成的离散结构 根据连接顶点对的边的种类和数目的不同 图有多种类型 几乎每一门可以想到的学科 都有用图模型来解决的问题 9 128 图的种类 1 如果 则称为无向图 2 如果 则称为有向图 无论是无向图还是有向图 都统称为图 其中V的元素称为图G的结点 E的元素称为图G的边 图G的结点数目称为图的阶 可以用几何图形表示上面定义的图 用小圆圈表示结点 在无向图中 若 就用连接结点v1和v2的无向线段表示边e 在有向图中 若 就用v1指向v2的有向线段表示边e 10 128 图的基本概念 定义 设无向图 1 如果 则称e与v1 或v2 互相关联 e连接v1和v2 v1和v2既是e的起点 也是e的终点 也称v1和v2为点邻接 2 如果两条不同的边e1和e2与同一个结点关联 则称e1和e2为边邻接 也就是说 共边的点称为点邻接 共点的边称为边邻接 11 128 图的基本概念 定义 设有向图 如果 则称e连接v1和v2 e与v1 或v2 互相关联 分别称v1和v2是e的起点和终点 也称v1和v2邻接 例 无向图 e1连接v1和v2 v1和v2邻接 e1和e2邻接 12 128 图的基本概念 例 有向图 v2和v1分别是e1的起点和终点 v2与v1邻接 13 128 图的基本概念 定义 设图 e1和e2是G的两条不同的边 1 如果与e1关联的两个结点相同 则称e1为自圈 或称环和回路 2 如果 则称e1与e2平行 3 如果图G没有自圈 也没有平行边 则称G为简单图 4 如果图G没有自回路 有平行边 则称G为多重边图 5 如果图G既有自回路 又有平行边 则称G为伪图 14 128 图的种类 例 中国主要城市通讯图 15 128 图的种类 16 128 度 定义 如果G是无向图 G中与v关联的边和与v关联的自回路的数目之和称为v的度 或次 记为 如果G是有向图 G中以v为起点的边的数目称为v的出度 记为 G中以v为终点的边的数目称为v的入度 记为 v的出度与入度之和称为v的度 记为 注意 在计算无向图中结点的度时 自回路要考虑两遍 因为自回路也是边 17 128 度 例 计算下图中各结点的度 18 128 度 定理 在无向图中 所有节点的度数之和等于边数的2倍 证 因为每条边给图G带来两度 设图G有m条边 所以图G共有2m度 等于图G的所有结点的度数之和 定理 在有向图中 所有顶点的度数之和等于边的2倍 所有顶点的入度之和等于所有节点的出度之和 都等于边数 度 例 结点的度 19 128 20 128 结点 定义 度数为奇数的结点称为奇结点 度数为偶数的结点称为偶结点 定理 任何图都有偶数个奇结点 定义 度为0的结点称为孤立结点 度为1的结点称为端点 21 128 一些特殊的简单图 零图 结点都是孤立结点的图称为零图 平凡图 一阶零图称为平凡图 圈图 Cn n 3 是由n个顶点v1 v2 vn以及边 v1 v2 v2 v3 vn 1 vn vn v1 组成的 22 128 一些特殊的简单图 轮图 对 来说 当给圈图Cn添加一个顶点 并且把这个新顶点与Cn里的n个顶点逐个连接 可以得到轮图Wn 23 128 一些特殊的简单图 正则图 所有结点的度均为自然数d的无向图称为d度正则图 24 128 一些特殊的简单图 完全无向图 设 如果n阶简单无向图G是n 1度正则图 则称G为完全无向图 记为Kn 注意 完全无向图的任意两个不同结点都邻接 一至五阶完全无向图 25 128 一些特殊的简单图 注意 完全有向图的任意两个不同结点之间都有一对方向相反的有向边相连接 完全有向图 设 每个结点的出度和入度均为n 1的n阶简单有向图称为完全有向图 一至三阶完全有向图 26 128 一些特殊的简单图 27 128 特殊类型的图的一些应用 局域网 在一座大楼里 像小型计算机和个人电脑这样的计算机 以及像打印机这样的外设 可以用局域网来连接 有三种常见的局域网拓扑结构 28 128 图的同构 从图的定义可以看出 图的最本质的内容是结点和边的关联关系 两个表面上看起来不同的图 可能表达相同的结点和边的关联关系 29 128 图的同构 实际中 利用图的同构可以研究是否有可能用同样的方式画两个图 例如化学里 表示过去已知化合物的图可以用来判定想象中的新化合物是否已经研究过了 30 128 图的同构 定义 设图和 如果存在双射和双射 使得对于任意的 都满足 则称G与G 同构 记作 并称f和g为G和G 之间的同构映射 简称同构 31 128 图的同构 换一种更简单的方法来描述 设图和图 若存在从 到 的双射函数f 对于V中所有的结点a和b来说 在G中有a到b的边当且仅当在G 中有f a 和f b 的边 就说G与G 同构 也就是说 两个同构的图有同样多的结点和边 并且映射f保持结点间的邻接关系 映射g保持边之间的邻接关系 图同构的直观含义 是将其中一个图经过旋转 平移 拉伸等变形后与另一个图完全重合 32 128 图的同构 例 求证下图 和 同构 证明 两个图点 边的数目都相同 设函数f为f u1 v1 f u2 v4 f u3 v3 f u4 v2 G中相邻的点是u1与u2 u2与u4 u4与u3 u3与u1 对应的像点f u1 v1与f u2 v4 f u2 v4与f u4 v2 f u4 v2与f u3 v3 f u3 v3与f u1 v1在H中相邻 因此 二图同构 33 128 图的同构 两个图同构必须满足的必要条件是 1 顶点个数相同 2 边数相同 3 度数相同的顶点个数相同 4 K度顶点的导出子图同构 判定图的同构比较难 但是却可以通过上述四点证明图不同构 34 128 图的同构 例 判断下列两图是否同构 35 128 图的同构 例 判断下列两图是否同构 36 128 上面两个图不是同构的 因为左图中 度结点都和两个 度结点相关联 而右图中的 度结点和一个 度结点相关联还和一个 度结点相关联 37 128 图的同构 例 判断下列两图是否同构 38 128 上面两个图是同构的 我们只要构造双射函数f a1 b1 c1 d1 e1 f1 a2 b2 c2 d2 e2 f2 并且f a1 f2 f b1 b2 f c1 c2f d1 d2 f e1 a2 f f1 e2f是个双射函数 并且保持了边的邻接关系 39 128 图的同构 判定两个图是否同构 已知的最好算法具有指数的最坏情形时间复杂度 对图的结点来说 不过 解决这个问题的线性平均情形时间复杂度的算法已经找到 而且有希望找到判定两个图是否同构的多项式最坏情形时间复杂度算法 一个名叫NAUTY的最佳算法 目前可以在个人电脑上 秒之内判定带有100个结点的两个图是否同构 40 128 图模型 图可以用在各种模型里 用于不同的行业 栖息地重叠图 顶点表示物种 若两个物种竞争 他们共享某些食物来源 则用无向边连接表示他们的顶点 41 128 图模型 熟人图 可以用模型表示人与人之间的各种关系 顶点表示人 当两个人互相认识时 用一条无向边连接这两个人 据估计 世界上所有人的熟人图有超过60亿个顶点和可能超过1万亿条边 好莱坞图 好莱坞图用顶点表示演员 当两个顶点的演员共同出演一部电影时 就用一条无向边连接这两个顶点 根据无联网电影数据库 在2001年11月 好莱坞图有574724个顶点和超过1600万条边 这些顶点所表示的演员出现在292609部电影中 42 128 43 128 图模型 循环赛图 每个队其其他所有队各有一次的比赛称为循环赛 其中每个顶点表示每个队 若a队击败b队 则有一条从a指向b的有向边 44 128 图模型 合作图 合作图可以用来为学术论文的合作者关系建立模型 顶点表示某个文章的某个作者 人 如果两个人合作论文 则用无向边连接这两个人 已经发现在数学研究论文上合作的合作图有超过337000个顶点和496000条边 网络图 互联网可以用有向图来建模 用顶点表示网页 若有从网页a指向网页b的链接 则做一条从a指向b的有向边 网络图几乎是连续变化的 几乎每秒都有新页面产生而又有其他页面被删除 目前网络图有超过10亿个顶点和几百亿条边 许多研究者正在研究网络图的性质 以便更好的理解网络的特性 45 128 图模型 优先图与并发处理 通过并发的执行某些语句 计算机程序可能执行的更快 但重要的是 要避免语句执行时还要用到尚未执行语句的结果 语句与前面语句的相关性可以表示成有向图 用顶点表示某个语句 若在a语句执行完之前不能执行b语句 则引出一个从a到b的有向边 这样的图称为优先图 46 128 图模型 47 128 9 2子图和图的运算 定义 设和为图 平凡生成子图 对于图 G本身以及零图都是G的平凡生成子图 48 128 子图 定义 设图 且 以V 为结点集合 以起点和终点均在V 中的边的全体为边集合的G的子图 称为由V 导出的G的子图 记为G V 若 导出子图 记为 是从G中去掉V 中的结点以及与这些结点关联的边而得到的图G的子图 定义 设图 且 以为结点集合 以为边集合的G的子图称为由E 导出的子图 49 128 子图 从图示看 图G的子图是图G的一部分 G的真子图的边数比G的边数少 G的生成子图与G有相同的结点 G的导出子图是G的以为结点集合的最大子图 例 b 是 a 的子图 真子图和生成子图 c 是 a 的由 1 2 3 4 导出的子图 子图 50 128 51 128 图的运算 定义 设图和同为无向图或同为有向图 1 如果对于任意具有 则称G和是可运算的 2 如果 则称G和是不相交的 3 如果 则称G和是边不相交的 52 128 图的运算 设图和为可运算的 1 称以为结点集合 以为边集合的G1和G2的公共子图为G1和G2的交 记为 2 称以为边集合 以与这些边关联的结点集合为点集的G1和G2的公共母图为G1和G2的并 记为 3 称以为结点集合 以为边集合的的子图为G1和G2的环和 记为 图的运算 53 128 54 128 图的运算 并不是任何两个图都有交 并和环和 如上图 a 和 b 没有交和并 因为边e1在 a 中连接v1和v2 而在 b 中连接v2和v3 55 128 图的运算 定理 设图和为可运算的 1 如果 则存在唯一的 2 存在唯一的和 证 设G1和G2同为有向图 若同为无向图也可同样证明 1 定义为 对任意的 显然 设图和均为G1和G2的交 因为 对任意 因为 对任意 这表明 因此 56 128 图的运算 证 2 定义如下 显然 设和均为G1和G2的并 因为且 所以对任意 这表明 因此 对于存在唯一的可同样证明 57 128 图的运算 定义 设图 记为 对任意 记为 是从G中去掉E 中的边所得到的G的子图 定义 设图和同为无向图或同为有向图 并且边不相交 记为 是由G增加E 中的边所得到的图 其中指出E 中的边与结点的关联关系 58 128 图的运算 59 128 上面的例子中 a 和 b 分别为G1和G2 则图c d e分别是 G1 G2 v5 v6 G1 G2 g h G2 E 其中 g g v1 v3 图的运算 60 128 9 3路径 回路和连通性 61 128 路径和回路 例 分析下列无向图 在该无向图中 是路径 但不是简单路径 是简单路径 但不是基本路径 是闭路径 但不是简单闭路径 另外 如果从路径中去掉闭路径就得到基本路径 62 128 路径和回路 例 分析下列有向图 在该有向图中 是路径 但不是简单路径 是简单路径 但不是基本路径 从中去掉闭路径1a1就得到基本路径1c4 可以看出 从2至1存在多条路径 但从1至2没有路径 63 128 路径和回路 注意 单独一个结点v也是路径 它是长度为0的基本路径 因此 任何结点到其自身总存在路径 在无向图中 若从结点v至结点v 存在路径 则从v 至v必存在路径 而在有向图中 从结点v至v 结点存在路径 而从v 至v却不一定存在路径 设路径和 用P1P2记路径 路径和回路 64 128 例 摆渡问题 一个人带有一条狼 一头羊和一捆白菜 要从河的左岸渡到右岸去 河上仅有一条小船 而且只有人能划船 船上每次只能由人带一件东西过河 另外 不能让狼和羊 羊和菜单独留下 问怎样安排摆渡过程 65 128 路径和回路 解 河左岸允许出现的情况有以下10种情况 人狼羊菜 人狼羊 人狼菜 人羊菜 人羊 狼菜 狼 菜 羊及空 各物品已安全渡河 我们把这10种状态视为10个点 若一种状态通过一次摆渡后变为另一种状态 则在两种状态 点 之间画一直线 得到上图 这样摆渡问题就转化成在图中找出以 人狼羊菜 为起点 以 空 为终点的简单路 容易看出 只有两条简单路符合要求 即 1 人狼羊菜 狼菜 人狼菜 菜 人羊菜 羊 人羊 空 2 人狼羊菜 狼菜 人狼菜 狼 人狼羊 羊 人羊 空 对于简单路 1 的安排为 人带羊过河 人回来 带狼过河 放下狼再将羊带回 人再带菜过河 人回来 带羊过河 对于简单路 2 的安排为 人带羊过河 人回来 带菜过河 放下菜再将羊带回 人再带狼过河 人回来 带羊过河 上述的两种方案都是去4次 回3次 且不会再有比这更少次数的渡河办法了 66 128 路径和回路 定理 设v和v 是图G中的结点 如果存在从v至v 的路径 则存在从v至v 的基本路径 证 设当从v至v 存在长度小于的路径时 从v至v 必存在基本路径 如果存在路径 其中 并且有i和j满足且 则是从v至v 的长度为l j i的路径 根据归纳假设 存在从v至v 的基本路径 l 67 128 路径和回路 定理 n阶图中的基本路径的长度小于或等于n 1 证 在任何基本路径中 出现于序列中的各结点都是互不相同的 在长度为l的任何基本路径中 不同的结点数目是l 1 因为集合V仅有n个不同的结点 所以任何基本路径的长度不会大于n 1 对于长度为l的基本循环来说 序列中有l个不同的结点 因为是n阶图 所以任何基本循环的长度 都不会超过n 综上所述 在n阶图中 基本路径的长度不会超过n 1 68 128 路径和回路 路径可以表示很多图模型中的有用信息 熟人关系图中的通路 最小世界原理 合作图中的通路 数学家的埃德斯数 好莱坞图中的通路 演员的培根数 著名演员凯文 培根 69 128 路径和回路 定理 设v是图G的任意结点 G是回路或有向回路 当且仅当G的阶与边数相等 并且在G中存在这样一条从v到v的闭路径 使得除了v在该闭路径中出现两次外 其余结点和每条边都在该闭路径上恰出现一次 证 见书上 70 128 路径和回路 71 128 路径和回路 72 128 路径和回路 例 判断图 a 有没有有向回路 73 128 连通性 定义 设v1和v2是图G的结点 如果在G中存在从v1至v2的路径 则称在G中从v1可达v2或v1和v2是连通的 否则称在G中从v1不可达v2 对于图G的结点 用R v 表示从v可达的全体结点的集合 注意 在无向图中 若从v1可达v2 则从v2必可达v1 而在有向图中 从v1可达v2不能保证从v2必可达v1 无论无向图还是有向图 任何节点到自身都是可达的 74 128 连通性 75 128 连通性 76 128 连通性 77 128 连通图 78 128 连通图 无向图是连通的 当且仅当对于任意 79 128 连通图 由于可达性的非对称性 有向图的连通概念要复杂得多 这里需要用到基础图的概念 80 128 连通图 定义 设G是有向图 1 如果G中任意两个结点都互相可达 则称G是强连通的 2 如果对于G的任意两结点 必有一个结点可达另一个结点 则称G是单向连通的 3 如果G的基础图是连通的 则称G是弱连通的 81 128 子图和分支 定义 设G 是G的具有某种性质的子图 并且对于G的具有该性质的任意子图G 只要G G 就有G G 则称G 相对于该性质是G的极大子图 定义 无向图G的极大连通子图称为G的分支 定义 设G是有向图 1 G的极大强连通子图称为G的强分支 2 G的极大单向连通子图称为G的单向分支 3 G的极大弱连同子图称为G的弱分支 82 128 子图和分支 定理 连通无向图恰有一个分支 非连通无向图有一个以上分支 定理 强连通 单向连通 弱连通 有向图恰有一个强分支 单向分支 弱分支 非强连通 非单向连通 非弱连通 有向图有一个以上强分支 单向分支 弱分支 83 128 子图和分支 例 84 128 子图和分支 注意 无向图的每个结点和每条边都恰在一个连通分支中 有向图中 并不是每个边都恰在一个强分支中 在简单有向图中 每个结点每条边都恰在一个弱分支中 在简单有向图中 每个结点每条边至少位于一个单项分支中 85 128 由结点集合 v1 v2 v3 v4 v5 v6 和 v7 形成的诱导子图都是强分图 由结点集合 v1 v2 v3 v4 v5 v7 v4 v5 和 v6 v5 所成的诱导子图都是单向分图 由结点集合 v1 v2 v3 v4 v5 v6 v7 形成的诱导子图是弱分图 子图和分支 86 128 资源分配图 下面给出简单有向图的一个应用 资源分配图 在多道程序的计算机系统中 可以同时执行多个程序 实际上 程序共享计算机系统中的资源 如磁带机 磁盘设备 CPU 主存贮器和编译程序等 操作系统对这些资源负责分配给各个程序 当一个程序要求使用某种资源 它要发出请求 操作系统必须保证这一请求得到满足 87 128 死锁状态 对资源的请求可能发生冲突 如程序A控制着资源r1 请求资源r2 但程序B控制着资源r2 请求资源r1 这种情况称为处于死锁状态 然而冲突的请求必须解决 资源分配图有助发现和纠正死锁 88 128 假设条件 假设某一程序对一些资源的请求 在该程序运行完之前必须都得到满足 在请求的时间里 被请求的资源是不能利用的 程序控制着可利用的资源 但对不可利用的资源则必须等待 89 128 分析 令Pt p1 p2 pm 表示计算机系统在时间t的程序集合 Qt Pt是运行的程序集合 或者说在时刻t至少分配一部分所请求的资源的程序集合 Rt r1 r2 rn 是系统在时刻t的资源集合 资源分配图Gt 是有向图 它表示了时间t系统中资源分配状态 把每个资源ri看作图中一个结点 其中i 1 2 n 表示有向边 E当且仅当程序pk Pt已分配到资源ri且等待资源rj 90 128 分析 续 例如 令Rt r1 r2 r3 r4 Qt p1 p2 p3 p4 资源分配状态是 p1占用资源r4且请求资源r1 p2占用资源r1且请求资源r2和r3 p3占用资源r2且请求资源r3 p4占用资源r3且请求资源r1和r4 于是 可得到资源分配图Gt 如图16 2 7所示 能够证明 在时刻t计算机系统处于死锁状态iff资源分配图Gt中包含强连通图 91 128 前例资源分配图 92 128 割集 有时删除一个结点和它所关联的边 就产生带有比原图更多的连通分支的子图 把这样的结点称为割点 有时删除一条边 就产生带有比原图更多的连通分支的子图 把这样的边叫做割边或者桥 93 128 9 4图的矩阵表示 邻接矩阵 定义 设是一个简单有向图 其中的结点集合 并且假定各结点已经有了从结点v1到vn的次序 试定义一个n n的矩阵A 使得其中的元素 则称这样的矩阵A是图G的邻接矩阵 94 128 邻接矩阵 定义 元素或为0或为1的任何矩阵 都称为比特矩阵或布尔矩阵 邻接矩阵也是布尔矩阵 第i行上值为1的元素的个数 等于结点vi的出度 第j列上值为1的元素的个数 等于结点vj的入度 95 128 邻接矩阵 图的邻接矩阵不具有唯一性 对于给定简单有向图来说 其邻接矩阵依赖于集合V中的各元素间的次序关系 给定两个有向图和相对应的邻接矩阵 如果首先在一个图的邻接矩阵中交换一些行 而后交换相对应的各列 从而有一个图的邻接矩阵 能够求得另外一个图的邻接矩阵 则事实上这样的两个有向图 必定是互为同构的 96 128 邻接矩阵 例 写出下图的邻接矩阵 并计算各个节点的出度和入度 解 首先给各结点安排好一个次序 譬如说是 得出邻接矩阵如下 97 128 邻接矩阵 上例中 如果重新把各结点排列成 就能写出另外一个矩阵如下 98 128 邻接矩阵 对于给定图G 显然不会因结点编序不同而使其结构会发生任何变化 即图的结点所有不同编序实际上仍表示同一个图 换句话说 这些结点的不同编序的图都是同构的 并且它们的n 个邻接矩阵都是相似的 今后将略去这种由于V中结点编序而引起邻接矩阵的任意性 而取该图的任一个邻接矩阵作为该图的矩阵表示 99 128 邻接矩阵 由邻接矩阵判断有向图的性质 如果有向图是自反的 则邻接矩阵的主对角线上的各元素 必定都是1 如果有向图是反自反的 则邻接矩阵的主对角线上的各元素 必定都是0 对于对称的有向图来说 其邻接矩阵也是对称的 也就说 对于所有的i和j而言 都应有aij aji 如果给定有向图是反对称的 则对于所有的i和j和i j而言 aij 1蕴含aji 0 100 128 邻接矩阵 可以把简单有向图的矩阵表示的概念 推广到简单无向图 多重边图和加权图 对于简单无向图来说 这种推广会给出一个对称的邻接矩阵 在多重边图或加权图的情况下 可以令 其中的wij 或者是边的重数 或者是边的权 另外 若 则 在零图的邻接矩阵中 所有元素都应该是0 亦即其邻接矩阵是个零矩阵 101 128 邻接矩阵 逆图的邻接矩阵 如果给定的图是一个简单有向图 并且其邻接矩阵是A 则图G的逆图的邻接矩阵是A的转置 对于无向图或者对称的有向图来说 应有 102 128 在图上的意义 定义矩阵 设是邻接矩阵中的第i行和第j列上的元素 是矩阵中的第i行和第j列上的元素 i j 于是 对于来说 有 如果边 则有 如果边 则有 对于某一个确定的k来说 如果和都是给定图的边 则在表示的上述求和表达式中 应该引入基值1 从结点vi和vj二者引出的边 如果能共同终止于一些结点的话 那么这样的一些结点的数目 就是元素的值 103 128 在图上的意义 例 如图 求 解 简单算法 原矩阵A中 第i行和第j行相交 有几个1 AAT的第i行第j列就是几 矩阵的主对角线的元素对应了各个节点的出度 104 128 在图上的意义 设是邻接矩阵A中的 i j 元素 是矩阵C中的元素 于是 对于 对于某一个确定的k来说 如果都是给定图的边 则在上式中应引入基值1 可得从图中的一些点所引出的边 如果能够同时终止于结点vi和vj的话 那么这样的一些结点的数目 就是元素Cij的值 105 128 在图上的意义 例 如图 求 解 简单算法 原矩阵A中 第i列和第j列相交 有几个1 ATA的第i行第j列就是几 矩阵的主对角线的元素对应了各个节点的入度 106 128 邻接矩阵的幂 对于来说 考察邻接矩阵A的幂An可知 邻接矩阵A中的第i行和第j列上的元素值1 说明了图G中存在一条边 也就是说 存在一条从结点vi到vj长度为1的路径 试定义矩阵A2 使得A2中的各元素为 元素值等于从vi到vj长度为2的不同路径的数目 显然 矩阵中主对角线上的元素的值 表示了结点上长度为2的循环的个数 矩阵A3中的元素值 i j 依次类推 107 128 邻接矩阵的幂 例 108 128 邻接矩阵的幂 定理 设是一简单有向图 并且A是G的邻接矩阵 对于来说 矩阵Am中的元素 i j 的值 等于从vi到vj长度为m的路径数目 证 对于m进行归纳证明 当m 1时 由邻接矩阵的定义中能够得到Am A 设矩阵Ak中的元素 i j 值是 且对于m k来说结论为真 因为 所以应有 是从结点vi出发 经过结点vk到vj的长度为k 1的各条路径的数目 这里vk是倒数第二个结点 因此 应是从结点vi出发 经过任意的倒数第二个结点到vj的长度为k 1的路径总数 因此 对于m k 1 定理成立 109 128 邻接矩阵的幂 根据上述定理 可得出结论 能使矩阵Am中的元素 i j 值是非零的最小正整数m 就是距离 对于和来说 如果矩阵中的 i j 元素值和 j i 元素值都为0 那么就不会有任何路径连通结点vi和vj 因此 结点vi和vj必定是属于图G的不同分图 110 128 邻接矩阵的幂 例 给定一个简单有向图 如下图所示 其中的结点集合 试求出图G的邻接矩阵A和A的幂A2 A3 A4 111 128 邻接矩阵的幂 解 112 128 可达性矩阵 给定一个简单有向图 并且设结点 可知 由图G的邻接矩阵A能够直接确定G中是否存在一条从vi到vj的边 设 由矩阵能够求得从结点vi到vj长度为r的路径数目 试构成矩阵 矩阵Bk的 i j 元素值表示了从结点vi到vj长度小于或等于r的路径数目 当图中的结点数目为n时 矩阵Bn都能够提供足够的信息 以表明从图中的任何结点到其它结点的可达性 113 128 可达性矩阵 定义 给定一个简单有向图 其中 V n 并且假定G中的各结点是有序的 试定义一个n n的路径矩阵P 使得其元素为 路经矩阵P仅表明了图中的任何结点偶对之间是否至少存在一条路径 以及在任何结点上存在循环与否 它并不能指明存在的所有路径 114 128 可达性矩阵 例 试构成下列有向图的路径矩阵P 解 设邻接矩阵A A1 在前面的例中 已经求出过矩阵的幂A2 A3和A4 A5 求出矩阵B5和路径矩阵P如下 115 128 可达性矩阵 注意 对于具有n个结点的图而言 长度为n的路径不可能是基本路径 假定图中的每一个结点 从它本身出发总是可达的 由矩阵Bn 1构成路径矩阵P 或由矩阵Bn构成路径矩阵P 这两种方法都可以采纳 116 128 可达性矩阵 首先构成矩阵 而后由他们构成矩阵Bn 再由矩阵Bn构成路径矩阵P 太麻烦了 为了减少计算工作量 应该设法使得不产生