第 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,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。