离散数学-图论基础.ppt

第七章图论基础Graphs 2020 3 29 第一节图的基本概念 一个图G定义为一个三元组 G V 非空有限集合 V中的元素称为结点 node 或顶点 vertex E 有限集合 可以为空 E中的元素称为边 edge 从E到V的有序对或无序对的关联映射 associativemapping 2020 3 29 图的基本概念 图G 中的每条边都与图中的无序对或有序对联系若边e E与无序对结点 va vb 相联系 即 e va vb va vb V 则称e是无向边 或边 棱 若边e E与有序对结点相联系 即 e va vb V 则称e是有向边 或弧 va是e的起始结点 vb是e的终结点 2020 3 29 图的基本概念 若va和vb与边 弧 e相联结 则称va和vb是e的端结点va和vb是邻接结点 记作 vaadjvb adjoin 也称e关联va和vb 或称va和vb关联e若va和vb不与任何边 弧 相联结 则称va和vb是非邻接结点 记作 vanadjvb关联同一个结点的两条边 弧 称为邻接边 弧 关联同一个结点及其自身的边 称为环 cycle 环的方向没有意义 2020 3 29 图的基本概念 若将图G中的每条边 弧 都看作联结两个结点则G简记为 每条边都是弧的图 称为有向图 directedgraph 如图b 每条边都是无向边的图 称为无向图 undirectedgraph 如图a 有些边是弧 有些边是无向边的图 称为混合图 如图c 2020 3 29 图的基本概念 若图G中的任意两个结点之间不多于一条无向边 或不多于一条同向弧 且任何结点无环 则称G为简单图 如图c 若图G中某两个结点之间多于一条无向边 或多于一条同向弧 则称G为多重图 如图a b 两个结点间的多条边 同向弧 称为平行边 弧 平行边 弧 的条数 称为重数 2020 3 29 图的基本概念 在多重图的表示中 可在边 弧 上标注正整数 以表示平行边 弧 的重数把重数作为分配给边 弧 上的数 称为权 weight 将权的概念一般化 使其不一定是正整数 则得到加权图的概念 给每条边 弧 都赋予权的图 叫做加权图 weightedgraph 记作G W是各边权之和 2020 3 29 图的基本概念 在无向图G 中 V中的每个结点都与其余的所有结点邻接 即 va vb va vb V va vb E 如图 a 则称该图为无向完全图 completegraph 记作K V 若 V n 则 E C n n 1 2 2n 2020 3 29 图的基本概念 在有向图G 中 V中的任意两个结点间都有方向相反的两条弧 即 va vb va vb V E E 如图 a 则称该图为有向完全图 记作K V 若 V n 则 E P n n 1 2n 2020 3 29 图的基本概念 在图G 中 若有一个结点不与其他任何结点邻接则该结点称为孤立结点 如图 a 中的v4仅有孤立结点的图 称为零图 零图的E 如图 b 仅有一个孤立结点的图 称为平凡图 trivialgraph 如图 c 2020 3 29 问题 问题1 是否存在这种情况 25个人中 由于意见不同 每个人恰好与其他5个人意见一致 问题2 是否存在这种情况 2个或以上的人群中 至少有2个人在此人群中的朋友数一样多 2020 3 29 结点的次数 二 结点的次数定义 在有向图G 中 对任意结点v V以v为起始结点的弧的条数 称为出度 out degree 引出次数 记为d v 以v为终结点的弧的条数 称为入度 in degree 引入次数 记为d v v的出度和入度的和 称为v的度数 degree 次数 记为d v d v d v 2020 3 29 结点的次数 定义 在无向图G 中 对任意结点v V结点v的度数d v 等于联结它的边数若结点v上有环 则该结点因环而增加度数2记G的最大度数为 G max d v v V 记G的最小度数为 G min d v v V 2020 3 29 结点的次数 在图G中的任意一条边e E 都对其联结的结点贡献度数2定理 在无向图G 中 d v 2 E 通常 将度数为奇数的结点称为奇度结点将度数为偶数的结点称为偶度结点定理 在无向图G 中 奇度结点的个数为偶数个 2020 3 29 结点的次数 问题1 是否存在这种情况 25个人中 由于意见不同 每个人恰好与其他5个人意见一致 在建立一个图模型时 一个基本问题是决定这个图是什么 什么是结点 什么是边 在这个问题里 我们用结点表示对象 人 边通常表示两个结点间的关系 表示2个人意见一致 也就是说 意见一致的2个人 结点 间存在一条边 2020 3 29 结点的次数 问题1 是否存在这种情况 25个人中 由于意见不同 每个人恰好与其他5个人意见一致 这样我们可以知道 如果存在题目所述情况 那么每个结点都与其他5个结点相关联 也就是说 每个结点的度为5 由定理可知 奇度结点的个数为偶数个 现在是否能够得出结论了 2020 3 29 结点的次数 类似问题 晚会上大家握手言欢 握过奇数次手的人数一定是偶数碳氢化合物中 氢原子个数是偶数是否有这样的多面体 它有奇数个面 每个面有奇数条棱 2020 3 29 结点的次数 问题2 是否存在这种情况 两个人或以上的人群中 至少有两个人在此人群中的朋友数一样多 以人为结点 仅当二人为朋友时 在此二人之间连一边 得一 友谊图 G V E 设V v1 v2 vn 不妨设各结点的次数为d v1 d v2 d vn n 1 假设命题不成立 则所有人的朋友数都不一样多 则0 d v1 d v2 d vn n 1 2020 3 29 结点的次数 问题2 是否存在这种情况 两个人或以上的人群中 至少有两个人在此人群中的朋友数一样多 若0 d v1 d v2 d vn n 1 则有 由于d v1 0 则有d v2 1 d v3 2 d vn n 1 又因为d vn n 1 所以 d vn n 1因为d vn n 1 则每个结点皆与vn相邻 则d v1 1 于是有 d v2 2 d v3 3 d vn n 矛盾 故假设不成立 即d v1 d v2 d vn 中至少有一个等号成立 命题成立 2020 3 29 结点的次数 定义 在无向图G 中 若每个结点的度数都是k 即 v v V d v k 则称G为k度正则图 regulargraph 2020 3 29 子图 三 子图定义 给定无向图G1 G2 若V2 V1 E2 E1 则称G2是G1的子图 subgraph 记作G2 G1若V2 V1 E2 E1 且E2 E1 则称G2是G1的真子图 记作G2 G1若V2 V1 E2 E1 则称G2是G1的生成子图 spanningsubgraph 记作G2 G1 V2 V1 2020 3 29 子图 例如 2020 3 29 子图 定义 对于图G G1 G G2 G1和G2都是G的生成子图 称为平凡生成子图定义 设G2 是G1 的子图对任意结点u v V2 若有 u v E1 则有 u v E2 则G2由V2唯一地确定 则称G2是V2的诱导子图记作G V2 或G2 若G2中无孤立结点 且由E2唯一地确定 则称G2是E2的诱导子图 记作G E2 或G2 2020 3 29 子图 例如 2020 3 29 补图 定义 设G1 和G2 是G 的子图 若E2 E E1 且G2是E2的诱导子图 即G2 则称G2是相对于G的G1的补图 2020 3 29 补图 图G1和G2互为相对于G补图 2020 3 29 补图 定义 给定图G1 若存在图G2 且E1 E2 及图是完全图则称G2是相对于完全图的G1的补图 记作G2 G1 2020 3 29 补图 G2 G1 2020 3 29 图的同构 四 图的同构定义 给定图G1 G2 若存在双射函数f V1 V2 使得对于任意u v V1有 u v E1 f u f v E2 或 E1 E2 则称G1与G2同构 isomorphic 记作G1 G2 2020 3 29 图的同构 例7 1 1证明下面两个图G1 G2 同构证明 V1 v1 v2 v3 v4 V2 a b c d 构造双射函数f V1 V2 f v1 a f v2 bf v3 c f v4 d可知 边 v1 v2 v2 v3 v3 v4 v4 v1 被分别映射成 a b b c c d d a 故G1 G2 2020 3 29 图的同构 例7 1 2证明下面两个有向图是同构的 证明 如图所示 G1 G2 结点编号如图所示 构造函数f V1 V2 使得f a 1 f b 3 f c 4 f d 5 f e 2则 被分别映射成 故f是双射函数 所以G1与G2同构 2020 3 29 图的同构 可以给出图的同构的必要条件 结点数相等边数相等度数相等的结点数相等要注意的是 这不是充分条件 2020 3 29 图的同构 例7 1 3证明下面两个无向图是不同构的 v1是3度结点 故f v1 只能是c或d或g或h 若f v1 c 由于v2 v4和v5与v1邻接 因此f v2 f v4 和f v5 应当分别为与c邻接的b d和g 但是 v2 v4和v5中 只有一个3度结点 而b d g中却有2个3度结点 故f v1 c 同理可说明 f v1 也不可能是d g和h 因此这样的f是不存在的 因此G1和G2是不同构的 2020 3 29 第二节路 链 与回路 圈 一 路 链 与回路 圈 定义 给定图G 令v0 v1 vm V e1 e2 em E称交替序列v0e1v1e2v2 emvm为连接v0到vm的链 路 称v0和vm为链 路 的始结点和终结点链的长度为边 弧 的数目m若v0 vm 该链 路 称为圈 回路 circuit 2020 3 29 链和圈 在链中 若任意ei只出现一次 则称该链 路 为简单链 路 若任意vi只出现一次 则称该链 路 为基本链 路 基本链必定是简单链在圈中 若任意ei只出现一次 则称该圈 回路 为简单圈 回路 若任意vi只出现一次 则称该圈 回路 为基本圈 回路 2020 3 29 链和圈 例7 2 1下图中 P1 v1e1v2e7v5 也可以表示为 P1 e1e7 是一个基本链 也是一个简单链 P2 v2e2v3e3v3e4v1e1v2 也可以表示为 P2 e2e3e4e1 是一个简单圈 但不是基本圈 P3 v4e6v2e7v5e8v4e6v2e2v3 是一个链 P4 v2e7v5e8v4e6v2 是一个基本圈 也是一个简单圈 2020 3 29 链和圈 链和圈可以只用边的序列表示上例中 v2e2v3e3v3e4v1e1v2 也可表示为 e2e3e4e1 v4e6v2e7v5e8v4e6v2e2v3 也可表示为 e6e7e8e6e2 对于简单图来说 链和圈可以仅用结点序列表示 图中 v2e2v3e4v1e1v2e3v5e8v4 可表示为 e2e4e1e3e8 也可表示为 v2v3v1v2v5v4 2020 3 29 链和圈 定理 在一个图中 若从结点vi到结点vj存在一条链 路 则必有一条从vi到vj的基本链 路 证明 1 若从vi到vj给定的链本身就是基本链 定理成立2 若从vi到vj给定的链不是基本链 则至少含有一个结点vk 它在该链中至少出现两次以上 也就是说 经过vk有一个圈 于是可以从原有链中去除 中所有出现的边 弧 对于原链中所含的所有圈都做此处理 最终将得到一条基本链 路 2020 3 29 链和圈 问题 在一个图中 若从结点vi到结点vj存在一个圈 则必有一个从vi到vj的基本圈吗 例7 2 2若u和v是一个圈上的两个结点 u和v一定是某个基本圈上的结点吗 习题7 16 答 不一定 本图中 u和v在一个圈上 但是却不在一个基本圈上 2020 3 29 链和圈 定理 在一个具有n个结点的图中 任何基本链 路 的长度不大于n 1任何基本圈 回路 的长度不大于n证明 1 根据基本链的定义可知 出现在基本链中的结点都是不同的 因此在长度为m的基本链中 不同的结点数为m 1又因为图中仅有n个结点 故m 1 n 即m n 12 根据基本圈的定义可知 长度为k的基本圈中 不同的结点数为k 图中共有n个结点 所以k n 2020 3 29 可达 二 连通图定义 在一个图中 若从vi到vj存在任何一条链则称从vi到vj是可达的 accessible 简称vi可达vj规定 每个结点vi到自身都是可达的 2020 3 29 连通无向图 一 连通无向图对于无向图G 而言 可证明 可达性 是一个 关系 它对V给出一个划分 每个块中的元素形成一个诱导子图 两个结点间是可达的 当且仅当它们属于同一个子图称这样的子图为G的连通分图 G的连通分图的个数记为 G 若G中只有一个连通分图 则称G是连通图 即任意两结点可达 否则称G为非连通图 或分离图 等价 2020 3 29 连通无向图 定义 在无向图G 中若任意两个结点可达 则称G是连通的 connected 称G为连通无向图 否则称G是非连通的 称G为非连通图或分离图 若G的子图G 是连通的 且不存在包含G 的更大的G的子图G 是连通的 则称G 是G的连通分图 connectedcomponents 简称分图 G中连通分图的个数记为 G 2020 3 29 连通无向图 例7 2 3 G1 G2 G1是连通图 G1 1 G2是非连通图 G2 2 2020 3 29 连通无向图 定义 从图G 中删除结点集S 是指V SE 与S中结点相连结的边 而得到的子图 记做G S G v3 2020 3 29 连通无向图 定义 从图G 中删除结点集S 是指V SE 与S中结点相连结的边 而得到的子图 记做G S G v3 2020 3 29 连通无向图 定义 从图G 中删除边集T 是指V不变E T而得到的子图 记做G T G e1 e3 e4 2020 3 29 连通无向图 定义 从图G 中删除边集T 是指V不变E T而得到的子图 记做G T G e1 e3 e4 2020 3 29 连通无向图 定义 给定连通无向图G S V若 G S G 1且对任意T S G T G 则称S是G的一个分离结点集 cut setofnodes 若S中仅含有一个元素v 则称v是G的割点 cut node 2020 3 29 连通无向图 例7 2 4G如下图所示 S v1 v3 G 1 G S 2 G S G 2020 3 29 连通无向图 例7 2 4G如下图所示 S v1 v3 G 1 G S 2 G S G G v1 1 2020 3 29 连通无向图 例7 2 4G如下图所示 S v1 v3 G 1 G S 2 G S G G v1 1 G v3 1 2020 3 29 连通无向图 例7 2 4G如下图所示 S v1 v3 G 1 G S 2 G S G G v1 1 G v3 1 S是G的分离结点集 2020 3 29 连通无向图 例7 2 5G如下图所示 S v2 G 1 G S 2 G S G v2是G的割点 不存在其他的G的割点 2020 3 29 连通无向图 定义 给定连通无向图G T E若 G T G 1且对任意F T G F G 则称T是G的一个分离边集 cut setofedges 若T中仅含有一个元素e 则称e是G的割边 cut edge 或桥 2020 3 29 连通无向图 例7 2 6G如下图所示 T e1 e2 G 1 G T 2 G T G 2020 3 29 连通无向图 例7 2 6G如下图所示 T e1 e2 G 1 G T 2 G T G G e1 1 2020 3 29 连通无向图 例7 2 6G如下图所示 T e1 e2 G 1 G T 2 G T G G e1 1 G e2 1 2020 3 29 连通无向图 例7 2 6G如下图所示 T e1 e2 G 1 G T 2 G T G G e1 1 G e2 1 T是G的分离边集 2020 3 29 连通无向图 例7 2 7G如下图所示 T e1 G 1 G T 2 G T G e1是G的割边 e2和e3都是G的割边 2020 3 29 连通无向图 定义 对连通的非平凡图G 称 G min S S是G的分离结点集 为G的结点连通度 node connectivity 它表明产生分离图需要删去结点的最少数目对分离图G而言 G 0对存在割点的连通图G而言 G 1 S V 2020 3 29 连通无向图 例7 2 8求G1和G2的结点连通度 G1 2 G2 1 2020 3 29 连通无向图 定义 对连通的非平凡图G 称 G min T T是G的分离边集 为G的边连通度 edge connectivity 它表明产生分离图需要删去边的最少数目对分离图G而言 G 0对存在割边的连通图G而言 G 1对无向完全图Kn Kn T E n 1 2020 3 29 连通无向图 例7 2 9求G1和G2的边连通度 G1 2 G2 1 2020 3 29 连通无向图 定理 对于任何一个无向图G 有 G G G 证明 1 若G是分离图 则 G G 0 而 G 0 2 若G是连通图 先证明 G G 若G是平凡图 则 G 0 G 若G不是平凡图 则当删去所有联结一个具有最小度的结点的边 除了环 后 便产生了一个分离图 因此 G G 再证明 G G 若 G 1 则G存在一个割边 显然 G G 1 2020 3 29 连通无向图 若 G 2 则删去某 G 条边后 G就成为分离图若只删除 G 1条边 则仍得到连通图且存在一割边e u v 对于 G 1条边中的每一条边 选取一个不同于u和v的结点 把这些结点删去 将必须至少删去 G 1条边若这样会产生分离图 则 G G 1 G 若这样产生的仍是连通图且e是割边 再删除结点u或v必将产生分离图 因此 G G 综上所述 有 G G G 2020 3 29 连通无向图 定理 一个连通无向图G中的结点v是割点 充要条件是存在两个结点u和w 使得联结u和w的每条链都经过v证明 1 充分性 若G中联结u和w的每条链都经过v 删去v 则在子图G v 中 u和w必定不可达 故v是G的割点2 必要性 若v是G的割点 删去v 则子图G v 中至少有两个连通分图G1 和G2 任取两个结点u V1 w V2 u和w不可达 故G中联结u和w的每条链必经过v 2020 3 29 连通无向图 同理可以证明 定理 一个连通无向图G中的边e是割边 充要条件是存在两个结点u和w 使得联结u和w的每条链都经过e定理 一个连通无向图G中的边e是割边 充要条件是e不包含在G的任何基本圈中证明 教材P172 定理7 8 2020 3 29 乌拉姆猜想 1929 左右两张相片 捂住左边相片的一部分 也捂住右边相片的相应部分 例如都捂住左眼 能看到的相片的大部分形象一致 再分别捂住左右相片的另一个对应部分 例如右耳 结果能看到的相片的大部分仍然一致 如此轮番地观察各次对应的暴露部分 都会看到相同的形象 那么谁都会相信这两张照片是同一个人或孪生兄弟的留影 数学描述 有图G1 V1 E1 和G2 V2 E2 V1 v1 v2 vn V2 u1 u2 un n 3 如果G1 vi G2 ui i 1 2 n 则G1 G2 2020 3 29 连通有向图 二 连通有向图对于有向图G 而言 结点间的可达性不再是等价关系 它仅仅是自反的和可传递的 一般不是对称的定义 对于给定的有向图G 要略去G中每条边的方向 便得到一个无向图G 称G 是G的基础图 2020 3 29 连通有向图 定义 在简单有向图G中 若任何两个结点间都是可达的 则称G是强连通的若任何两个结点间 至少是从一个结点可达另一个结点 则称G是单向连通的若G的基础图是连通的 则称G是弱连通的 2020 3 29 连通有向图 例7 2 10判断G1 G2和G3是强连通 单向连通 弱连通 G1是强连通的 G2是单向连通的 G3是弱连通的 2020 3 29 连通有向图 由定义可知 若G是强连通的 则它必定是单向连通的反之未必真若G是单向连通的 则它必是弱连通的反之未必真 2020 3 29 连通有向图 定理 有向图G是强连通的 当且仅当G中有一回路 它至少通过每个结点一次证明 1 充分性 若G中存在一条回路 它至少通过每个结点一回 则G中任何两个结点都是互相可达的 所以G是强连通的 2 必要性 若G是强连通的 则G中任何两个结点都是互相可达的 因此可以做出一条回路经过G中所有结点 否则 必有某结点v不在该回路上 v与回路上的各结点不可能都互相可达 与G是强连通的矛盾 2020 3 29 连通有向图 定义 在简单有向图G中具有强连通性质的极大子图 称为强分图具有单向连通性质的极大子图 称为单向分图具有弱连通性质的极大子图 称为弱分图 2020 3 29 连通有向图 例7 2 11求G的强分图 单向分图和弱分图 G的强分图有 定理 简单有向图G中的任意一个结点 恰位于一个强分图中 2020 3 29 连通有向图 定理 简单有向图G中的任意一个结点 恰位于一个强分图中证明 由强分图的定义可知 G中每个结点位于一个强分图中假设G中存在结点v位于两个强分图G1和G2中则由强分图的定义可知 G1中的每个结点与v互相可达 G2中的每个结点也与v互相可达故G1中的每个结点与G2中的每个结点通过v 能够互相可达 这与G1和G2是两个强分图矛盾因此G中每个结点只能位于一个强分图中 2020 3 29 连通有向图 例7 2 11求G的强分图 单向分图和弱分图 G的单向分图有 定理 简单有向图G中的每个结点和每条弧 至少位于一个单向分图中 2020 3 29 连通有向图 例7 2 11求G的强分图 单向分图和弱分图 G的弱分图有 定理 简单有向图G中的每个结点和每条弧恰位于一个弱分图中 2020 3 29 结点间的距离 三 结点间的距离定义 在图G中 若结点u可达结点v 它们之间可能存在不止一条链 路 在所有链中 最短链的长度称为结点u和v之间的距离 或短程线 测地线 记做 d 2020 3 29 结点间的距离 距离满足下面性质 d 0d 0d d d若u不可达v 则d 即使u和v互相可达 d未必等于d 2020 3 29 有向图在计算机中的应用 四 有向图在计算机中的应用这里给出一个简单有向图在计算机中的应用 利用资源分配图来纠正和发现死锁 2020 3 29 有向图在计算机中的应用 在多道程序的计算机系统中 同一时间内有多个程序需要同时执行 每个程序都共享计算机资源 如CPU 内存 外存 输入设备 编译系统等 操作系统将对这些资源分配给各个程序 当一个程序需要使用某种资源的时候 要向操作系统发出请求 操作系统必须保证这个请求得到满足 才能运行该程序 2020 3 29 有向图在计算机中的应用 对资源的请求可能发生冲突 发生死锁 例如 程序P1占有资源r1 请求资源r2程序P2占有资源r2 请求资源r1有冲突的请求必须要解决 可以利用有向图来模拟对资源的请求 从而帮助发现和纠正 死锁 状态 2020 3 29 有向图在计算机中的应用 令Pt P1 P2 P3 P4 是t时刻运行的程序集合Rt r1 r2 r3 r4 是t时刻所需要的的资源集合P1占有资源r4 请求资源r1P2占有资源r1 请求资源r2和r3P3占有资源r2 请求资源r3P4占有资源r3 请求资源r1和r4可得到资源分配图G如图所示 可证 t时刻系统处于死锁状态 G中包含多于一个结点的强分图 2020 3 29 有向图在计算机中的应用 t时刻系统处于死锁状态 G中包含多于一个结点的强分图解决办法 使G中的每个强分图中都是单个结点 2020年3月29日星期日 3x 1猜想 卡拉兹 20世纪30年代 汉堡大学的卡拉兹 Callatz 提出一个猜想 x0是一个自然数 若x0是偶数 则取x1 x0 2 若x0是奇数 则取x1 3x0 1 2 将x1应用上述规则得到x2 如此进行下去 则到达某一步 xk 1 东京大学的N 永内达 NabuoYoneda 用计算机检验了所有不超过240 1 2 1012的自然数 结果都符合卡拉兹的猜想 2020年3月29日星期日 3x 1猜想 卡拉兹 如果把一批自然数放在最高层 用3x 1问题的规则算出第二层的值 继而算出第三层的值 图中的结点是自然数 当数1算出数2时 则在图上画上有向边 得到的有向图称为卡拉兹有向图 如图所示 3x 1猜想中 卡拉兹图的最底层结点是1 2020 3 29 第三节图的矩阵表示 一 图的矩阵表示定义 给定简单图G V v1 v2 vn V中的结点按照下标由小到大编序 编序与矩阵形式有密切关系 则n阶方阵AG aij 称为图G的邻接矩阵 adjacencymatrix 其中 2020 3 29 邻接矩阵 例7 3 1图G 如图所示 2020 3 29 邻接矩阵 例7 3 2图G 如图所示 2020 3 29 邻接矩阵 对于仅仅结点编序不同的图 是同构的它们的邻接矩阵也是相似的G1 G2 存在置换矩阵P 使得AG2 P 1AG1P对于由结点编序不同引起的邻接矩阵的不同将被忽略任取图的任意一个邻接矩阵作为该图的矩阵表示 2020 3 29 邻接矩阵 图G的邻接矩阵AG可以展示图G的一些性质 若邻接矩阵AG的元素全是零 则G是若邻接矩阵AG的元素主对角线上全是0 其他元素全是1 则G是无向图G的邻接矩阵AG是在简单有向图的邻接矩阵中 第i行元素是由结点vi出发的弧所确定的 故第i行元素为1的数目 等于vi的 即d vi aik第j列元素是由到达结点vj的弧所确定的 故第j列元素为1的数目 等于vj的 即d vj akj 零图 连通的简单完全图 对称矩阵 出度 入度 2020 3 29 邻接矩阵 定理 设A为简单图G的邻接矩阵 则An中的i行j列的元素aijn等于G中联结vi和vj的长度为n的链 路 的数目证明 1 当n 1时 An A1 A 定理成立2 设n k时定理成立 即aijk为G中联结vi和vj的长度为k的链的数目3 当n k 1时 An Ak 1 Ak A 即aijk 1 airk arj根据假设可知 airk为G中联结vi和vr的长度为k的链的数目 arj为G中联结vr和vj的长度为1的链的数目 因此aijk 1为G中联结vi和vj的长度为k 1的链的数目 2020 3 29 邻接矩阵 例7 3 3图G 如图所示 求A A2 A3 A4 2020 3 29 邻接矩阵 由上面的定理可知 若要判断图G中结点vi到vj是否可达 可以利用G的邻接矩阵A 计算A A2 A3 An 若发现某个Ar r是正整数 中aijr 1 则表明vi到vj可达 由上一节的定理可知 对于含有n个结点的图G 任何基本链 路 的长度不大于 任何基本圈 回路 的长度不大于因此 仅考虑aijr 1 r n 即可 n 1 n 2020 3 29 邻接矩阵 因此 只要计算Bn bij A A2 A3 AnBn中元素bij表示vi到vj的长度小于等于n的不同路径的总数bij 0时 vi可达vj 若i j 则说明存在经过vi的回路bij 0时 vi不可达vj 若i j 则说明不存在经过vi的回路 2020 3 29 邻接矩阵 例7 3 4图G 如图所示 求Bn Bn A A2 A3 A4 2020 3 29 邻接矩阵 问题 如何判断某无向图G是否为连通图 求出Bn bij A A2 A3 An若有某个bij为0 i j 则说明结点vi和vj处于不同的连通分图中 图G为分离图 否则G为连通图 即非主对角线上元素都不为0 思考 主对角线上元素bii表示什么 2020 3 29 可达矩阵 若关心的只是结点间的可达性或结点间是否有链存在至于存在多少条链以及长度为多少无关紧要则可以使用可达矩阵P pij 来表示结点间的可达性 2020 3 29 可达矩阵 可达矩阵P pij 的计算之一 通过Bn可令Bn bij A A2 A3 An再将Bn中非零元素改为1 零元素不变 即可得到P 注意