天津理工大学：《离散数学》课程教学资源（PPT课件）第七章 图的基本概念 7.3 图的矩阵表示 7.4 最短路径及关键路劲 7.5 例题分析

第7章图的基本概念（3-5节）

第7章 图的基本概念 （3-5节）

内容介绍$7.1无向图及有向图$7.2通路、回路、图的连通性$ 7.3图的矩阵表示$ 7.4最短路径及关键路劲$ 7.5例题分析

内容介绍 ✓§7.1 无向图及有向图 ✓§7.2 通路、回路、图的连通性 ✓§7.3 图的矩阵表示 ✓§7.4 最短路径及关键路劲 ✓§7.5 例题分析

知识回顾1、彼此关联e,与谁关联及关联次数？16e与谁关联及关联次数？eVs与谁关联及关联次数？

知识回顾 1、彼此关联 e1与谁关联及关联次数？ e2与谁关联及关联次数？ v5与谁关联及关联次数？ v2 v1 v4 v3 v5 e1 e2 e3 e4 e5 e6

知识回顾2、彼此相邻有向图顶点相邻V2与谁相邻？v,呢？e

知识回顾 2、彼此相邻 v2与谁相邻？ v1呢？ 有向图顶点相邻 v2 v1 v5 v3 v4 e1 e2 e3 e4 e5 e6 e7 e8

知识回顾3、可达在有向图D中，若从顶点v,到v;存在通路，贝则称v,可达v；（v,到自身是可达的）2（1）V4可达vz吗？（2）Vz可达vs吗？.-

知识回顾 3、可达 （1）v4可达v2吗？ （2）v2可达v5吗？ v2 v1 v5 v3 v4 e1 e2 e3 e4 e5 e6 e7 e8 在有向图D中，若从顶点vi到vj存在通 路，则称vi可达vj （vi到自身是可达的）

S7.3图的矩阵表示1.无向图的关联矩阵设无向图G=，V={V1,...,VnJ,N2en}，令m;为顶点v,与边e;的EF[e1, e2' ...,关联次数，则称(mi)nxm为G的关联矩阵。记作M(G)v;与e;不关联0m;的取值为：v;与e;关联次数为12v;与e;关联次数为2

§7.3 图的矩阵表示 1.无向图的关联矩阵 设无向图G=，V={v1，v2，.，vn }， E ={e1，e2，.，en }，令mij为顶点vi与边ej的 关联次数，则称(mij)nxm为G的关联矩阵。记作 M(G) 0 vi与ej不关联 1 vi与ej关联次数为1 2 vi与ej关联次数为2 mij的取值为：

S7.3图的矩阵表示1.无向图的关联矩阵1SM/(G) =图7-10关联矩阵

§7.3 图的矩阵表示 1.无向图的关联矩阵 1 1 1 0 0 0 1 1 1 0 1 0 0 1 2 0 0 0 0 0 M（G）= 关联矩阵 v2 v1 v3 v4 e1 e2 e3 e4 图7-10 e5

S7.3图的矩阵表示1.无向图的关联矩阵关联矩阵性质：每一列恰好有两个1或一个22第i行元素之和为v的度数（3）所有元素之和等于2m。(4)第i行之和等于0，v,是孤立点。(5)第j列与第k列相同，e;与e为平行边

§7.3 图的矩阵表示 1.无向图的关联矩阵 关联矩阵性质： （1）每一列恰好有两个1或一个2 （2）第i行元素之和为vi的度数。 （3）所有元素之和等于2m。 （4）第i行之和等于0，vi是孤立点。 （5）第j列与第k列相同， ej与ek为平行边

S7.3图的矩阵表示2.有向图的关联矩阵设有向图D=，V={V1，V2'.，Vn}令：E[e1, e2' ...,enl,1，v为e;的始点0，v;与e;不关联mi-1，v;为e;的终点则称(m;)nxm为D的关联矩阵。记作M(D)

§7.3 图的矩阵表示 2.有向图的关联矩阵 则称(mij)nxm为D的关联矩阵。记作M(D) 1，vi为ej的始点 0，vi与ej不关联 -1，vi为ej的终点 mij = 设有向图D=，V={v1，v2，.，vn }， E ={e1，e2，.，en }，令：

S7.3图的矩阵表示2.有向图的关联矩阵-1M/(D)=V图7-11关联矩阵

§7.3 图的矩阵表示 2.有向图的关联矩阵 v1 v4 v2 e1 v3 e2 e3 e4 e5 图7-11 1 -1 0 0 0 -1 0 1 -1 1 0 0 0 0 -1 0 1 -1 1 0 M（D）= 关联矩阵