首页 矩阵在离散数学中的应用

矩阵在离散数学中的应用

举报
开通vip

矩阵在离散数学中的应用 第 17卷第 3期 2010年 9月 长沙民政职业技术学院学报 Journa l of Changsha Soc ialW ork Co llege Vo l� 17 No�3 Sep�2010 矩阵在离散数学中的应用 王 � 涛 (长沙民政职业技术学院, 湖南 长沙 � 410004) [摘 � 要 ] � 矩阵是线性代数的概念, 然而集合论和图论是离散数学的范畴, 从表面上看没有什么联系, 这篇文章把 矩阵和关系、关系的复合、关系的幂、关系的性质、关系的闭包以及有向图、图的通路和回路数有机地结合起来...

矩阵在离散数学中的应用
第 17卷第 3期 2010年 9月 长沙民政职业技术学院学报 Journa l of Changsha Soc ialW ork Co llege Vo l� 17 No�3 Sep�2010 矩阵在离散数学中的应用 王 � 涛 (长沙民政职业技术学院, 湖南 长沙 � 410004) [摘 � 要 ] � 矩阵是线性代数的概念, 然而集合论和图论是离散数学的范畴, 从表面上看没有什么联系, 这篇文章把 矩阵和关系、关系的复合、关系的幂、关系的性质、关系的闭包以及有向图、图的通路和回路数有机地结合起来, 另 辟蹊径, 打开了思路。 [关键词 ] � 矩阵; 离散数学; 集合论; 图论 [中图分类号 ] � O151� 2� � [文章标识码 ] � A� � [文章编号 ] � 1671- 5136 ( 2010) 03- 0101- 03 � � [收稿日期 ] � 2010- 08- 25 � � [作者简介 ] � 王 � 涛 ( 1972- ), 男, 江苏徐州人, 长沙民政职业技术学院文法系副教授、硕士。研究方向; 高职数学 教育。 � � �宇宙间的万物是相通的 �, 任何事物之间都存在 着这样或那样的联系,线性代数与离散数学之间同样 存在着相关性。特别是矩阵在集合论和图论中的应 用,使得集合论和图论中的某些问题变得容易理解。 � � 一、矩阵在集合论中的应用 1�关系矩阵 设非空有限集 A = { x1, x2, �, xm }, R是 A 上的关 系,则下列 n �n矩阵MR = ( r ij ) r ij = 1 xiRyj 0� 否则 � i, j= 1, 2, �, n 称为关系 R的关系矩阵。 如: 设 A = 1, 2, 3, 4 , R = �1, 1�, �1, 2�, �2, 3�, �2, 4�, �4, 2�是 A上的关系, 则 R的关系矩阵为 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 关系矩阵的引入是为了在计算机上实现二元关系 的表示、存储和运算。 2�利用矩阵的乘法运算关系的复合及关系的幂 如给定集合 A = < 1, 2, 3, 4, 5},在集合 A 上定义 两种关系。R = { < 1, 2> , < 3, 4> , < 2, 2> }, S = { < 4, 2> , < 2, 5> , < 3, 1> , < 1, 3> }求 R�S和 S�R的 矩阵。 MR�S = 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 � 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 = 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 M S�R = 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 � 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 = 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 利用矩阵的乘法运算关系的复合及关系的幂比利 用集合表达式要好,特别是对于复杂关系运算。 3�利用矩阵反应关系性质的特点 (以下都以 4阶 方阵为例 ) 自反关系: (主对角线元素都为 1) 1 1 1 1 反自反关系: (主对角线元素都为 0) 0 0 0 0 对称关系: (关于主对角线对称 ) 1 1 1 1 0 0 1 0 1 1 0 1 反对称关系: (不关于主对角线对称 ) 1 0 1 0 0 1 1 0 0 0 4�利用矩阵的运算求关系的闭包 设关系 R, � r (R ), � s(R ), � t (R )的关系矩阵分 别为M, M r, M s和M t,则 M r=M + E � � M s=M +M � M t=M +M 2 +M 3 + � E是和M 同阶的单位矩阵, M �是 M的转置矩阵。 如设 A = { a, b, c, d }, 给定 A 上的关系 R 为 R = { < a, b> , < b, a > , < b, c> , < c, d > } M r= 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 + 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 = 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 M s= 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 + 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 = 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 MR 2 = 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 + 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 = 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 MR 3 = 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 + 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 = 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 MR 4 = 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 + 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 = 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 M t(R ) = 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 � � 二、矩阵在图论中的应用 1、用邻接矩阵表示有向图 设有向图 D = < V、E > , V= { v1, v2, �vn }, |E | = m, D的邻接矩阵 A (D ) = ( a ( 3 )ij ) n � n. 其中 a ( 1)ij 指 v1邻接到 vj的边的条数 (非负整数。 如有向图 D (下图所示 ),其 A (D )。 A (D ) = 1 2 1 0 0 0 1 0 0 0 0 1 0 0 1 0 2�利用矩阵的乘法求 D中长度为 L 的通路数和 回路数 ( 1) 令 A 2 (D ) = A (D ) � A (D )矩阵乘法 = ( a ( 2 ) ji ) n � n 其中 ( a ( 2 )ji ) = �n k= 1 a ika jk aikajk = 1� vi� vk � vj有通路 0� vi� vk � vj无通路 a ( 2) ij 表示从 v i到 vj长度为 2的通路数 ( i= j)或回 路数 ( i= j)。 考虑 A 2 (D ),简记为 A t。 A l = A l- 1� A = ( a( l)ij ) n �n 其中 a ( l)ij = �n k = 1 a l- 1 ik a ( l) jk a ( l) ij表示从 vi到 vj长度为 l的通路数 ( i� j)或回 路数 ( i� j)。 � ij a ( l) ij 为 D中长度为 l的通路总数, 其中 � i a ( l) ij 为 D中长度为 l的回路总数。 ( 2) 设 B r = A + A 2 + �+ A r ( r� 1) 则 B r中元素 b( r)ij 为 D中 vi 到 vj 长度小于等于 r 的通路总数, � ij b ( r ) ij 为 D 中长度小于等于 r的通路总 数,其中 � i b ( r ) ij 为 D中长度小于等于 r的回路总数。 例 1� 在上面的有向图 D中, ( 1) 求 A 2, A 3, A 4。 ( 2) 求 v1到 v3长为 3的通路数, v2到 v4长为 4 的通路数, v3到自身长为 4的回路数, D中长为 2的通 路总数。 102 � 长沙民政职业技术学院学报 � � � � � � � � � � � � � � � � � 2010年 � 解: (1) A 2 = 1 2 3 1 0 0 0 1 0 0 1 0 0 0 0 1 , A 3 = 1 2 4 3 0 0 0 0 0 0 0 1 0 0 1 0 , A 4 = 1 2 6 4 0 0 0 1 0 0 1 0 0 0 0 1 ( 2) v1到 v3长为 3的通路数是 4, v2到 v4长为 3的通路数是 0, v3到自身长为 4的回路数是 1, D中长为 2的通路总数是 10(A 2中所有元素之 和 )。 � � 三、结束语 利用矩阵来解决离散数学中的一些问题是很方便 的,从中使得我们发现两学科之间的联系,同时也让我 们打开了思路,另辟蹊径。我们要不断地去发现学科 与学科之间的内在联系,发现更多的规律。 [参考文献 ] [ 1]赵致琢 �关于计算机科学与技术认知问题的研究简报 ( I, II) [ J]� 计算机研究与发展, 2001, 38( I) : 1� 15� [ 2]屈婉玲, 耿素云, 张立昂 �离散数学 [ M ] �北京: 高等教育 出版社, 2008� [ 3]裴娣娜等 �现代教学论 (第 2卷 ) [M ] �北京: 人民教育出 版杜, 2005�325� 376� (上接第 100页 ) 经计算可以得到六个边界点坐标分别为 A ( 5604�5, 8011�06 )、 B ( 7859�71, 7838�92 )、 C ( 8728�24, 8054�0175)、D ( 10551, 7262�2)、E ( 11970, 8565�0 ); 与 北纬 42�线的两 个交 点坐 标为 G ( 5211�55, 9236)、F( 11788�4, 9236)。 将以上重叠区域分割为 8个部分, 分别为 GKA、 KABH、AB、BH IC、ICDJ、JDEF、DE、EF。因此重叠部分 面积计算为: S23 = �sGA + SKABH + SAB + �sBC + �sCD + SJDEF + SDE + �sEF ( 2�3�4) 其中 SAB代表线段 AB下方弓形的面积, SDE代表 线段 DE下方弓形的面积, 而弧 GA、弧 BC、弧 CD、弧 EF的曲线方程见 2�3�4式。 代入实际数据得: S2 = S21 + S22 + S23 = 5�08 � 107 ( km 2 ) 所以测控覆盖率为: �= S2 /S1 = 13�58% ( 2�3�5) 另外,以上计算的只是 11个固定的测控点的测控 覆盖率,而神舟七号在发射和运行过程中还有 5艘远 望船舰。因为这 5艘船是可以随时变动地点的, 所以 我们近似认为其测控辐射的圆都是完全落在宽带中 的,则有 S/2 = S2 + 5�R 2gcz, 那么此时全部 16个测控点 的覆盖率为: �= S /2 /S1 = ( S2 + 5�R2gcz ) /S1 = 24�2% ( 2�3�6) 由以上的建模和分析,我们发现, 在发射过程中, 由于上升阶段火箭偏离发射中心的距离并不大而且附 近布设的测控点数目又多, 所以基本可以达到 100% 的测控率;而在运行阶段,测控的覆盖率维持在 13% 至 25%的范围,但是由于在本次神七发射过程中 �天 链一号 �中继卫星的同时发射,使得覆盖率远远上升, 达到了 60%以上,可以较好的完成测控任务。 [参考文献 ] [ 1]W�F�Luca. 离散与系统模型 [ M ]. 长沙:国防科技大学出版 社, 1996. [ 2]李庆扬, 关治,白峰杉. 数值计算原理 [M ]. 北京: 清华大学 出版社, 2000. [ 3]王正林, 刘明 � 精通 M atlab7 [ M ]. 北京: 电子工业出版 社, 2006. [ 4]姜启源, 谢金星,叶俊 �数学模型 [M ]. 北京:高等教育出版 社, 2003. 103� 第 3期 � � � � � � � � � � � � � � � � 王 � 涛: 矩阵在离散数学中的应用
本文档为【矩阵在离散数学中的应用】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_018690
暂无简介~
格式:pdf
大小:679KB
软件:PDF阅读器
页数:3
分类:其他高等教育
上传时间:2011-12-12
浏览量:56