浅谈矩阵在离散数学中应用.docVIP

浅谈矩阵在离散数学中应用摘要：离散数学是计算机学科的一门重要的专业基础课，扎实的基础是非常重要的。本文就矩阵在离散数学中的各种应用展开讨论，并实例说明 关键词：矩阵；离散数学；运用 中图分类号：G642.4 文献标识码：A 文章编号：1007-9599 (2011) 23-0000-01 The Application of the Matrix in Discrete Mathematics Yuan Zhiwei (College of MathematicsComputer Science,Xiangfan University,Xiangyang 441053,China) Abstract:Discrete Mathematics is computer science an important professional basic course,a solid foundation is very important.In this paper,the matrix in the discrete mathematics to discuss a variety of applications and examples. Keywords:Matrix;Discrete mathematics;Use 引言：随着计算机科学的发展，重点研究有限系统的离散数学已经成为一门越发重要的科学，数字计算机本质上是一个有限结构，它的许多性质都可以在有限数学系统的框架下得到解释。矩阵是一种有力的数学工具，本文就矩阵在离散数学中的应用展开讨论，总结了矩阵在离散数学中的应用类型，以期对初学者和数学工作者在学习离散数学时提供学习辅导和参考资料 定义1给出m×n个数，按一定顺序排成一个m行、n列的矩形数表 此数表称为m行n列矩阵。常记A=，或A=（），或 有关应用及其举例 一、二元关系的表示 定义2设A，B为有限集，构造一个矩阵，以A的元素和B的元素分别标注其行与列，对于a∈A和b∈B。视a，b是否具有关系R，在a行和b列交叉处标上1或0.这样得到的矩阵称为关系矩阵 例如：A={1，2，3，4}，在A上定义二元关系R为大于关系，表示x大于y，采用列举法为R={，，，，，}.则关系矩阵为 二、图的表示和邻接矩阵 定义3设无向图G=，V={v1，v2，vn}，E={e1，e2，，em}。令为节点vi与边ej关联的次数，则称矩阵为G的关联矩阵，记为M（G） 例如：无向图G如下所示，则M（G）为： 定义4设图G=为有向图，V={v1，v2，vn}，即有n个节点，令是vi邻接到vj的边的数目，则称矩阵为G的邻接矩阵，记为A（G） 例如：有向图Ｇ如下 三、用矩阵求关系合成和偏序中的盖住关系 （一）关系合成 设和分别表示关系R和S的矩阵，令M=，则M中的非零元素表示其对应的元素具有关系。（其中加法“+”是逻辑加，即0+0=0，0+1=1，1+0=1，1+1=1.） 例如：R={，，，，}，S={，，，}求 解： （二）求解偏序中的盖住关系 同上，记为偏序集S的关系矩阵，将中的自反关系对应的元素全部置0且记该改变后的矩阵为，令M=，则中去掉M中为1的元素后所剩元素表示cov（S）. 例如：给定A={1，2，3}上的关系，R={，，，，，}，求出cov（R），并画出哈斯图 解： ，则cov（R）={，} 参考文献： [1]耿素云,屈婉玲,张立昂著.离散数学(第三版)[M].清华大学出版社,2004 [2]刘学数,袁磊,郑巧仙著.离散数学[M].武汉大学出版社,2006 [3]S.利普舒尔茨,M.利普森著.离散数学[M].科学出版社,2002 1