淺談圖論與線性代數(shù)的聯(lián)系

孫燕玲

(濟(jì)南大學(xué) 泉城學(xué)院基礎(chǔ)教學(xué)部，山東 蓬萊 265600)

淺談圖論與線性代數(shù)的聯(lián)系

孫燕玲

(濟(jì)南大學(xué) 泉城學(xué)院基礎(chǔ)教學(xué)部，山東 蓬萊 265600)

圖論是數(shù)學(xué)的一個(gè)重要分支，它的應(yīng)用也十分廣泛，與此同時(shí)它與其他的數(shù)學(xué)分支也有著重要的聯(lián)系，本文主要討論圖論與線性代數(shù)的聯(lián)系，我們將運(yùn)用線性代數(shù)中的內(nèi)容解決圖論中的問題。

圖論；鄰接矩陣；線性代數(shù)

1引言

圖論在近二十年來(lái)發(fā)展十分迅速，應(yīng)用也比較廣泛，主要是研究圖的相關(guān)性質(zhì)。圖論是指由點(diǎn)和點(diǎn)與點(diǎn)之間的連線所形成的圖形，將這些圖形中的點(diǎn)和線賦予一些特定的意義，用這些點(diǎn)和線來(lái)描述事物間的關(guān)系，點(diǎn)指的是事物，線代表事物間的關(guān)系。

文章所涉及的只是圖論中的一些基本概念和理論，在方法上應(yīng)用線性代數(shù)中的內(nèi)容來(lái)研究圖的一些性質(zhì)。用線性代數(shù)中矩陣表示一個(gè)圖的各種關(guān)系，不僅是給出圖的一種表示方法，而且可以充分利用矩陣代數(shù)中的各種運(yùn)算，來(lái)研究圖的結(jié)構(gòu)特征及性質(zhì)，且便于計(jì)算機(jī)處理。用矩陣表示圖，必須首先將圖的頂點(diǎn)、邊等分別按照某種順序排列，然后并按照這種順序依次給定惟一標(biāo)號(hào)，使其成為標(biāo)號(hào)圖，最后給出其矩陣表示。用矩陣表示一個(gè)圖的各種關(guān)系，不僅是給出圖的一種表示方法，而且可以充分利用矩陣代數(shù)中的各種運(yùn)算，來(lái)研究圖的結(jié)構(gòu)特征及性質(zhì)，這樣便于用計(jì)算機(jī)處理圖。

2利用鄰接矩陣的乘法解決圖論中路徑問題

定義1設(shè)G=〈V,E〉是一個(gè)簡(jiǎn)單有向圖，V={v1,v2…,vn}A(G)=(aij)n×n，其中：

稱A(G)為G的鄰接矩陣。簡(jiǎn)記為A。

注：用A的冪求不同長(zhǎng)度通路(回路)的總數(shù)，下面我們通過一個(gè)例子來(lái)說(shuō)明相應(yīng)的問題。

例1 設(shè)G=〈V,E〉為簡(jiǎn)單有向圖，如下圖所示，寫出G的鄰接矩陣A，算出A2,A3,A4且確定v1到v2有多少條長(zhǎng)度為3的路?v1到v3有多少條長(zhǎng)度為2的路?v2到自身長(zhǎng)度為3和長(zhǎng)度為4的回路各多少條?

解：鄰接矩陣A和A2,A3,A4如下：

3利用行列式解決圖論中生成樹的問題

定義2設(shè)G=〈V，E〉是無(wú)向圖，V={v1,v2…,vp}E={e1,e2…eq}M(G)=(mij)p×q

稱M(G)為無(wú)向圖G的完全關(guān)聯(lián)矩陣。簡(jiǎn)記為M。

例2 求下面圖形的所有生成樹。

根據(jù)定義可以得出右圖中的完全關(guān)聯(lián)矩陣為

4用秩解決圖論中圖的連通性的問題

定理3若G為有向連通圖,B為G的關(guān)聯(lián)矩陣, 則秩(B)=n-1。

證：將關(guān)聯(lián)矩陣B的各行全部加到第k行，則第k行為零向量。記新得到的矩陣為B′, 則秩(Bk)=秩(B′)=秩(B)=n-1。

定理4設(shè)Bk為有向圖D的基本關(guān)聯(lián)矩陣，且C={e1,e2…,ek}是D中的一回路，則回路C的各邊對(duì)應(yīng)的矩陣Bk的各列必線性相關(guān).

證：設(shè)C由邊e1,e2,…ek組成,C對(duì)應(yīng)的關(guān)聯(lián)矩陣B的各列向量為a1,a2,…ak,則可驗(yàn)證a1+a2+…ak=0，故a1,a2,…ak線性相關(guān)。

推論若有向圖G的子圖H含有回路，則H對(duì)應(yīng)于任一基本關(guān)聯(lián)矩陣Bk的列向量組線性相關(guān)。

將矩陣和圖論聯(lián)系起來(lái)，能夠更簡(jiǎn)單的理解圖論的知識(shí)，對(duì)于理解題目的涵義也有影響。將圖論問題轉(zhuǎn)化為矩陣問題，在前人總結(jié)的經(jīng)驗(yàn)基礎(chǔ)上進(jìn)一步深化，將矩陣的知識(shí)運(yùn)用恰當(dāng)對(duì)于我們解決圖論問題也比較便利，給我們提供了解決圖論問題的另外一條思路，使得我們需要解決的問題得以簡(jiǎn)化。因此，研究圖論和線性代數(shù)之間的關(guān)系意義重大。

[1]卜月華.圖論及其應(yīng)用[M].南京:東南大學(xué)出版社，2002.

[2]劉亞國(guó).圖論鄰接矩陣的運(yùn)用[J].沂州師范學(xué)院學(xué)報(bào)，2008,(4).

[3]賈進(jìn)章,劉 進(jìn).基于鄰接矩陣圖的連通性判定性原則[J].2003,(2).

[責(zé)任編輯鮑艷]

DiscussionontheRelationbetweenGraphTheoryandLinearAlgebra

SUN Yan-ling

(CommonCoursesTeachingDepartmentofQuanzhouCollege,JinanUniversity,PenglaiShandong265600,China)

Graph theory is an important branch of mathematics and widely used, at the same time it has important connection with other branches of mathematics. This paper mainly discusses the relation between graph theory and linear algebra, and we will use contents in linear algebra to solve the problem in graph theory.

graph theory; adjacency matrix; linear algebra

2014-05-12

孫燕玲(1987-)，女，山東蓬萊人，濟(jì)南大學(xué)泉城學(xué)院基礎(chǔ)教學(xué)部助教，碩士研究生，主要從事圖論與組合優(yōu)化研究。

O151.2

A

1009-9042(2014)06-0092-02