第八节 矩阵应用的两个例子.pptVIP

第八节 矩阵应用的两个例子 例　1 例　2 例 1 这个例子简要说明了方阵及其方幂在称 为图论的有关研究中的应用情况. 图 G = ( V , E ) 由点集 V 和边集 E 组成. 例如，以 V = { a , b , c , d , e } 为点集，以 E = { (a, b) , (a, c) , (a, d) , (b, c) , (b, d) , (d, e) , (e, e) } 为边集构成的图 G，如图 1 – 2 所示. a b c d e 图 1 – 2 一条边除了联结两个点外，也可以由某个点联结 自身构成，如 中的点 e 与边 ( e , e )，这种 边称为一个环. 由图 1 – 2 表示的这类“图”显然不同于函数的图 形，但它在各种科学和工业活动中广泛存在，如组 织机构图、电路图、电话网络图、煤气或天然气管 道图及城市交通或道路图等等. 与图有关的许多问题 涉及道路. 道路是一个点的序列，其相邻的点由边 联结. 道路的长度是指构成该道路的边的数量， a b c d e 图 1 – 2 如图 1 – 2 中， ( a , b , d , e ) 是 a 与 e 之间，长 度为 3 的一条道路. 对于不同的问题，可能是要求 我们找出两点之间的最短道路，也可能是确定已知 的一对点中，是否存在一条道路等等. 而后一类问 题在许多实际问题中经常出现，例如规定电话的呼 叫线路； 研究随机中断(例如由于闪电)对网络的影 响等. 下面我们将说明方阵及其方幂可用于解决有 关一个图中各类道路的存在问题. 为此，我们首先介绍用一种称为邻接矩阵的矩 阵表示图的方法. 图 G 的邻接矩阵 A(G) = ( aij ) 的元 aij 按下述方 法确定： 如果第 i 点与第 j 点之间有一条边，则 aij = 1 , 否则 aij = 0 ; 一般情况下， aii = 0 , 除非第 i 点上有一个环( 此时 aii = 1 ). 可见 A(G) 表明了图 G 中哪些点是邻接的. 因而，图 1 – 2 中的图 G 的邻接矩阵为 a b c d e 图 1 – 2 a a b b c c d d e e 从图 1 – 2 还可以看出：点 a 与 b 之间，除了有 一条长度为 1 的道路 ( a , b ) 边联结外，还可以由 a 经 c 或 d 由另外两条长度为 2 的道路与 b 联结，那 么，如何确定图 G 中有哪些点之间存在长度为 2 的 道路呢？ 可以证明： 如果 A(G) 是图 G 的邻接矩阵, 则 A2(G) 中的第 i 行第 j 列元 ( i ? j ) 的数值等于第 i 个点与第 j 个点之间长度为 2 的道路个数. a a b b c c d d e e a a b b c c d d e e A2(G) 的主对角线以外的正元，指出图 G 中哪 些不同的点对之间可由长度为 2 的道路联结. 可以看 出，只有点 c 与点 e 之间，不存在长度为 2 的道路. 同时，这些正元的数值还表明了不同的点对之间长 度为 2 的道路个数. 例如 a 与 b 之间有两条长度为 2 的道路，而 a 与 c 之间只有一条长度为 2 的道路. 类似地 a a b b c c d d e e 可以反映出图 G 中不同的点之间由长度为 3 的道路 联结的情况. 例 2 假设某城市的天气分为 3 种状态：晴、阴 和下雨. 又由统计资料表明，在某个季节期间，如果 今天晴，则明天晴的概率(即可能性)为 阴的概率 为 下雨的概率为 类似地，如果今天阴或下雨 则明天的天气出现各种状态又分别有另外的概率. 表 1.3 提供了这些数据. 表 1.3 今 天 明 天 晴 阴 下雨 晴 阴 下雨 由这些数据组成 3 ? 3 矩阵 A 的每一列分别表示为今天天气对应的明天天 气的状态概率，每一行分别对应明天天气的各种状 态. 例如第一行表示当今天天气为晴、阴、下雨时 , 明天天气为晴的概率分别为 和 第二列则表 示当今天为阴时，明天为晴、阴、下雨的概率分别 为 和 这些概率值称为转移概率，该矩阵称 为转移矩阵. 由于 A 的各列分别表示当今天天气处于晴、阴 或下雨的情况下，明天天气为晴、阴或下雨的概率. A 的各行分别表示当今天天气为晴、阴或下雨的不 同情况下，明天为晴、为阴或为下雨的概率. 因此， 如果设今天为晴、阴、下雨的概率分别为 p1(0) , p2(0) , p3(0) ; 又设 p1(1) 表示明天为晴的概率，则有 类似地，若设 p2(1) , p3(1) 分别表示明天阴和下雨的概 率，则由 A 的第二行与第三行，有 例如，当我们在清晨听到天气预报为：今天为阴或 为雨的概率均为 即 则 由上面 3 式可预测出明天的天气概率