矩陣在離散數學中的應用

王 濤

(長沙民政職業技術學院,湖南 長沙 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-),男,江蘇徐州人,長沙民政職業技術學院文法系副教授、碩士。研究方向;高職數學教育。