王 濤

(長沙民政職業(yè)技術(shù)學(xué)院,湖南 長沙 410004)

矩陣在離散數(shù)學(xué)中的應(yīng)用

王 濤

(長沙民政職業(yè)技術(shù)學(xué)院,湖南 長沙 410004)

矩陣是線性代數(shù)的概念,然而集合論和圖論是離散數(shù)學(xué)的范疇,從表面上看沒有什么聯(lián)系,這篇文章把矩陣和關(guān)系、關(guān)系的復(fù)合、關(guān)系的冪、關(guān)系的性質(zhì)、關(guān)系的閉包以及有向圖、圖的通路和回路數(shù)有機(jī)地結(jié)合起來,另辟蹊徑,打開了思路。

矩陣;離散數(shù)學(xué);集合論;圖論

“宇宙間的萬物是相通的”,任何事物之間都存在著這樣或那樣的聯(lián)系,線性代數(shù)與離散數(shù)學(xué)之間同樣存在著相關(guān)性。特別是矩陣在集合論和圖論中的應(yīng)用,使得集合論和圖論中的某些問題變得容易理解。

一、矩陣在集合論中的應(yīng)用

1.關(guān)系矩陣

設(shè)非空有限集A={x1,x2,…,xm},R是A上的關(guān)系,則下列n×n矩陣MR=(rij)

關(guān)系矩陣的引入是為了在計算機(jī)上實(shí)現(xiàn)二元關(guān)系的表示、存儲和運(yùn)算。

2.利用矩陣的乘法運(yùn)算關(guān)系的復(fù)合及關(guān)系的冪

如給定集合A=<1,2,3,4,5},在集合A上定義兩種關(guān)系。R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>}求R∶S和S∶R的矩陣。

利用矩陣的乘法運(yùn)算關(guān)系的復(fù)合及關(guān)系的冪比利用集合表達(dá)式要好,特別是對于復(fù)雜關(guān)系運(yùn)算。

3.利用矩陣反應(yīng)關(guān)系性質(zhì)的特點(diǎn) (以下都以 4階方陣為例)

4.利用矩陣的運(yùn)算求關(guān)系的閉包

設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系矩陣分別為M,M r,M s和M t,則

E是和M同階的單位矩陣,M′是M的轉(zhuǎn)置矩陣。

如設(shè)A={a,b,c,d},給定A上的關(guān)系R為R={,,,}

二、矩陣在圖論中的應(yīng)用

1、用鄰接矩陣表示有向圖

設(shè)有向圖D=,V={v1,v2,…vn},|E|=m,D的鄰接矩陣A(D)=(ai(

j3

))n×n.

其中ai(

j1)指v1鄰接到vj的邊的條數(shù)(非負(fù)整數(shù)。如有向圖D(下圖所示),其A(D)。

2.利用矩陣的乘法求 D中長度為 L的通路數(shù)和回路數(shù)

(1)令A(yù)2(D)=A(D)·A(D)矩陣乘法

則Br中元素b(r)ij為D中vi到vj長度小于等于r的通路總數(shù),∑ijb(r)ij為D中長度小于等于r的通路總數(shù),其中 ∑ib(r)

ij為D中長度小于等于r的回路總數(shù)。

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

(1)求A2,A3,A4。

(2)求v1到v3長為 3的通路數(shù),v2到v4長為 4的通路數(shù),v3到自身長為 4的回路數(shù),D中長為 2的通路總數(shù)。

(2)v1到v3長為 3的通路數(shù)是 4,

v2到v4長為 3的通路數(shù)是 0,

v3到自身長為 4的回路數(shù)是 1,

D中長為 2的通路總數(shù)是 10(A2中所有元素之和)。

三、結(jié)束語

利用矩陣來解決離散數(shù)學(xué)中的一些問題是很方便的,從中使得我們發(fā)現(xiàn)兩學(xué)科之間的聯(lián)系,同時也讓我們打開了思路,另辟蹊徑。我們要不斷地去發(fā)現(xiàn)學(xué)科與學(xué)科之間的內(nèi)在聯(lián)系,發(fā)現(xiàn)更多的規(guī)律。

[1]趙致琢 .關(guān)于計算機(jī)科學(xué)與技術(shù)認(rèn)知問題的研究簡報 (I,II)[J].計算機(jī)研究與發(fā)展,2001,38(I):1—15.

[2]屈婉玲,耿素云,張立昂 .離散數(shù)學(xué) [M].北京:高等教育出版社,2008.

[3]裴娣娜等 .現(xiàn)代教學(xué)論 (第 2卷)[M].北京:人民教育出版杜,2005.325—376.

O151.2

A

1671-5136(2010)03-0101-03

2010-08-25

王 濤 (1972-),男,江蘇徐州人,長沙民政職業(yè)技術(shù)學(xué)院文法系副教授、碩士。研究方向;高職數(shù)學(xué)教育。