矩阵在离散数学中的应用

王 涛

(长沙民政职业技术学院,湖南 长沙 410004)

矩阵在离散数学中的应用

王 涛

(长沙民政职业技术学院,湖南 长沙 410004)

矩阵是线性代数的概念,然而集合论和图论是离散数学的范畴,从表面上看没有什么联系,这篇文章把矩阵和关系、关系的复合、关系的幂、关系的性质、关系的闭包以及有向图、图的通路和回路数有机地结合起来,另辟蹊径,打开了思路。

矩阵;离散数学;集合论;图论

“宇宙间的万物是相通的”,任何事物之间都存在着这样或那样的联系,线性代数与离散数学之间同样存在着相关性。特别是矩阵在集合论和图论中的应用,使得集合论和图论中的某些问题变得容易理解。

一、矩阵在集合论中的应用

1.关系矩阵

设非空有限集A={x1,x2,…,xm},R是A上的关系,则下列n×n矩阵MR=(rij)

关系矩阵的引入是为了在计算机上实现二元关系的表示、存储和运算。

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的矩阵。

利用矩阵的乘法运算关系的复合及关系的幂比利用集合表达式要好,特别是对于复杂关系运算。

3.利用矩阵反应关系性质的特点 (以下都以 4阶方阵为例)

4.利用矩阵的运算求关系的闭包

设关系R,r(R),s(R),t(R)的关系矩阵分别为M,M r,M s和M t,则

E是和M同阶的单位矩阵,M′是M的转置矩阵。

如设A={a,b,c,d},给定A上的关系R为R={,,,}

二、矩阵在图论中的应用

1、用邻接矩阵表示有向图

设有向图D=,V={v1,v2,…vn},|E|=m,D的邻接矩阵A(D)=(ai(

j3

))n×n.

其中ai(

j1)指v1邻接到vj的边的条数(非负整数。如有向图D(下图所示),其A(D)。

2.利用矩阵的乘法求 D中长度为 L的通路数和回路数

(1)令A2(D)=A(D)·A(D)矩阵乘法

则Br中元素b(r)ij为D中vi到vj长度小于等于r的通路总数,∑ijb(r)ij为D中长度小于等于r的通路总数,其中 ∑ib(r)

ij为D中长度小于等于r的回路总数。

例 1 在上面的有向图D中,

(1)求A2,A3,A4。

(2)求v1到v3长为 3的通路数,v2到v4长为 4的通路数,v3到自身长为 4的回路数,D中长为 2的通路总数。

(2)v1到v3长为 3的通路数是 4,

v2到v4长为 3的通路数是 0,

v3到自身长为 4的回路数是 1,

D中长为 2的通路总数是 10(A2中所有元素之和)。

三、结束语

利用矩阵来解决离散数学中的一些问题是很方便的,从中使得我们发现两学科之间的联系,同时也让我们打开了思路,另辟蹊径。我们要不断地去发现学科与学科之间的内在联系,发现更多的规律。

[1]赵致琢 .关于计算机科学与技术认知问题的研究简报 (I,II)[J].计算机研究与发展,2001,38(I):1—15.

[2]屈婉玲,耿素云,张立昂 .离散数学 [M].北京:高等教育出版社,2008.

[3]裴娣娜等 .现代教学论 (第 2卷)[M].北京:人民教育出版杜,2005.325—376.

O151.2

A

1671-5136(2010)03-0101-03

2010-08-25

王 涛 (1972-),男,江苏徐州人,长沙民政职业技术学院文法系副教授、硕士。研究方向;高职数学教育。