畢業(yè)設(shè)計論文關(guān)于圖的Fielder向量及其應(yīng)用

1、    題 目 關(guān)于圖的fielder向量及其應(yīng)用 學(xué)生姓名 學(xué)號 所在學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院 專業(yè)班級 數(shù)教1102班 指導(dǎo)教師 完成地點 陜西理工學(xué)院 2015年06月12日本科畢業(yè)論文任務(wù)書院(系) 數(shù)學(xué)與計算機科學(xué)學(xué)院 專業(yè)班級 數(shù)教1102班 學(xué)生姓名 一、畢業(yè)論文題目 關(guān)于圖的fielder向量及其應(yīng)用 二、畢業(yè)論文工作自 2015 年 3 月_ 10_日 起至 2014 年 6 月 20 日止三、畢業(yè)論文進行地點: 陜西理工學(xué)院 四、畢業(yè)論文內(nèi)容要求：利用已有的計算fielder向量的一種新方法,并了解圖的fielder向量在刻畫圖的結(jié)構(gòu)及其連通

2、性方面的應(yīng)運用.要求：（1）論文內(nèi)容要條理清楚、文字表達要準確、推理過程要準確無誤;（2）論文格式要按照學(xué)院要求的規(guī)范格式嚴格書寫;（3）論文字數(shù)（包括符號）不少于6000字;（4）獨立完成畢業(yè)論文,嚴禁弄虛作假和整篇抄襲他人成果;論文的電子版必須自己動手輸入文字和符號,所用的圖像（或圖形）也必須自己畫,嚴禁復(fù)制粘貼他人的文字、符號和圖像等.指 導(dǎo) 教 師 系(教 研 室) 系(教研室)主任簽名 批準日期 接受設(shè)計任務(wù)開始執(zhí)行日期 學(xué)生簽名 關(guān)于圖的fielder向量及其應(yīng)用(陜理工學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院數(shù)教1102班,陜西 漢中 723000)指導(dǎo)教師： 【摘要】 基于圖的fielder向

3、量方法,本文總結(jié)了求圖的fielder向量的方法,討論了圖的fielder向量與圖的連通性的關(guān)系,并用實例說明了該方法在判斷圖的連通性方面的應(yīng)用. 【關(guān)鍵詞】 fielder向量;laplace矩陣;特征值;特征向量;圖的連通性1 引 言在圖論中,有很多性質(zhì),人們?yōu)榱烁由钊氲牧私鈭D論,開始研究圖的性質(zhì),文獻1-5,7-8,11中都有體現(xiàn).圖的fielder向量就是圖的眾多性質(zhì)之一.圖的fielder向量是圖的laplace矩陣的次小特征值所對應(yīng)的特征向量,在參考文獻1,15中有提及.然而要計算圖的fielder向量就必須通過圖的laplace矩陣來計算,在參考文獻1,4-5,8中因均有提及.

4、此外,圖的fielder向量可以解決和圖論有關(guān)的許多問題,其中包括在文獻1和11中提及的圖的連通性、矩陣的重排、圖分割、蛋白質(zhì)分析與數(shù)據(jù)挖掘、機器學(xué)習(xí)與網(wǎng)絡(luò)搜索等.本文總結(jié)和概括例求fielder向量的方法和步驟.先給出的是圖的laplace矩陣的有關(guān)概念以及求法,利用laplace矩陣的次小特征值求其所對應(yīng)的特征向量（即圖的fielder向量）,再利用其判斷圖的連通性.2 預(yù)備知識2.1 圖的概念稱數(shù)學(xué)結(jié)構(gòu)為一個圖,其中是非空集合,是從集合到的一個映射,則稱是一個以為頂集合.以為邊集合的有向圖,中的元素稱為圖的頂點,中的元素稱為的邊,稱為g的關(guān)聯(lián)函數(shù),若,則簡寫為;稱是有向邊的尾,為有向邊的

5、頭.若,時,稱為有限圖,否則為無限圖6.一般,把中的元素表示成中的元素,記做.所以就可以簡單的記為.（1） 邊的端點：時,稱頂與是邊的端點.（2） 邊與頂相關(guān)聯(lián)：若邊的端點是與,則稱與,相關(guān)聯(lián).（3） 鄰頂：同一條邊的兩個端點叫做鄰頂.（4） 鄰邊：與同一個頂點相關(guān)聯(lián)的兩條邊叫做鄰邊.（5） 環(huán)：只與一個頂相關(guān)聯(lián)的邊叫做環(huán).（6） 重邊：,則稱與是重邊.（7） 單圖：無環(huán)無重邊的圖.（8） 完全圖：任二頂皆相鄰的圖,記之為.(完全圖有兩個特點：如果完全圖有個頂點,則每個頂點的度都是.如果完全圖有個頂點,則邊的總數(shù)為)3.（9） 二分圖：,且中任二頂不相鄰,中任二頂不相鄰,則稱為二分圖;若中每個

6、頂皆與中一切頂相鄰,則稱為完全二分圖,記成,其中8.（10） 階：表示圖中頂點個數(shù),記為.（11） 頂點的度：某個頂點關(guān)聯(lián)的邊的條數(shù)（環(huán)的個數(shù)）. 定義16在頂邊交錯鏈中,;且,則稱是的一條道路.其中允許或,.稱是的起點,是的終點,為路長,稱為的內(nèi)點,各邊相異的道路稱為行跡,各頂相異的道路稱為軌道,記成.起點與終點重合的道路稱為回路;起點與終點重合的軌道稱為圈,長的圈稱為階圈;兩頂?shù)木嚯x是指與為起止點的最短軌道之長度,記成;如果存在道路以為起止頂,則稱與在圖中連通.若圖中任意兩個頂點皆連通,則稱圖為連通圖.2.2 圖的性質(zhì)2.2.1 同構(gòu)如果圖和圖的頂點集分別是和,且他們可以一一對應(yīng)起來,并且

7、這種對應(yīng)是保持邊的,即就是存在雙射,使得當(dāng)且僅當(dāng),就稱圖和圖是同構(gòu)的,并且稱是它們之間的同構(gòu)映射.我們一般認為同構(gòu)的圖是一樣的,如何判斷兩個圖是同構(gòu)的是圖論中一個非常重要的問題9.2.2.2 子圖如果圖滿足,就稱是的子圖,階數(shù)等于的子圖稱為圖的支撐圖,若,則用表示由生成的子圖,也稱導(dǎo)出子圖.其頂點集為,中兩點相鄰且僅當(dāng)它們在圖中相鄰3.2.2.3 連通圖如果無向圖中任意兩點之間都至少存在一條路相連,則稱這樣的圖為連通圖,圖中的極大連通子圖稱為聯(lián)通分支,若圖是連通圖,則它只有一個聯(lián)通分支,就是它本身;若圖不是連通圖,則聯(lián)通分支大于13.2.2.4 圖的定向在無向圖中,與頂點關(guān)聯(lián)的邊的數(shù)目稱為頂點

8、的度,記做.如果將它的每條邊都給定一個方向,使其成為一個有向圖,我們把這種做法叫做無向圖的一個定向.圖中的邊,假設(shè)我們規(guī)定它的方向是由點指向點,則把頂點叫做邊的起點,把頂點叫做這條邊的終點.在這個有向圖中,以頂點為起點的有向邊的數(shù)目稱為是頂點的出度,記為,以頂點為點的有向邊的數(shù)目稱為頂點的入度,記做,在不引起混淆的前提下一般都把它們記做和.如果與頂點關(guān)聯(lián)的邊在定向中都是以為起點,則我們就把稱為有向圖的一個源;同樣的,如果與頂點關(guān)聯(lián)的邊在定向中都是以為終點,則我們把稱作是有向圖的一個匯,在給一個無向圖的邊定向后,如果定向圖中不含有向圈,則我們把這個定向稱作是無圈定向10.3 圖的fielder向

9、量3.1 laplace矩陣3.1.1 鄰接矩陣設(shè)是無向圖,我們根據(jù)的頂與頂點之間是否相鄰,編寫一個方陣,1表示相鄰,0表示不相鄰,嚴格定義如下7： 稱為無向圖的鄰接矩陣,其中, (3-1)例1 求圖-1的鄰接矩陣圖-1 解 圖-1的鄰接矩陣為一般而言,任何圖的鄰接陣的主對角線皆為零,完全圖的充要條件是其鄰接矩陣除主對角線外,其余元素皆為1.每個圖的鄰接矩陣皆為關(guān)于主對角線的0-1對稱矩陣. 對于有多個頂點的簡單無向圖,其頂點集為邊集為.令為圖的鄰接矩陣,其中時,頂點與有邊連接;否則,.3.1.2 度矩陣 設(shè)是無向圖,根據(jù)的每個頂點關(guān)聯(lián)的邊的條數(shù),構(gòu)成一個方陣,其中表示頂點的度數(shù).圖-1的度矩

10、陣為. 顯然,圖的度矩陣是對角陣,只有對角線上的元素非零,其余元素均為零. 一般的對于有多個頂點的簡單無向圖,設(shè)其頂點集為,邊集為 .則為的頂點度矩陣,其中是頂點的度數(shù)2.3.1.3 laplace矩陣 由上述所給的鄰接矩陣以及頂點度矩陣可以的到laplace矩陣如下14：, (3-2)其中就是度矩陣,就是鄰接矩陣.圖-1的laplace矩陣為： = - =.圖的laplace矩陣有一個很好的性質(zhì),即laplace矩陣的每一行和每一列之和為零.3.1.4 fielder向量令表示頂點的度,表示的第大的度,即有3, (3-3)或表示圖的頂點數(shù).在圖的拉普拉斯矩陣中, (3-4)是圖的度對角矩陣.

11、對圖的每一條邊,取其一個端點為始點,另一個端點為終點,這一過程稱為給圖一個定向.當(dāng)圖取定義定向時其定向關(guān)聯(lián)矩陣定義為,其中2,= (3-5) 則(其中是的轉(zhuǎn)置矩陣)且與的定向無關(guān).容易證明：是一個半正定的、對稱的實矩陣,且它的每一行的行和為零,因此又是奇異的1.假設(shè)它的特征值按照從小到大的順序排列為13, (3-6)稱為圖的第大拉普拉斯特征值.設(shè)是圖的相應(yīng)于的一個特征向量,則中的分量可以與圖的頂點之間建立一個一 一對應(yīng)關(guān)系,稱為給的點賦值.我們常將對應(yīng)于點的中的分量記為）或.特別地,假如x是相應(yīng)于的單位特征向量,則有2. (3-7)對的每個分量取絕對值,得到一個新的向量記作.fielder證明

12、11：圖是聯(lián)通的當(dāng)且僅當(dāng)?shù)牡诙€最小的拉普拉斯特征值.因此, fielder稱為圖的代數(shù)連通度,記為.稱對應(yīng)于的特征向量為fielder向量.對于例1中的簡單圖,根據(jù)定義求出它的拉普拉斯第二小特征值,繼而求出其所對應(yīng)的特征向量,亦即fielder向量.由圖-1可知則矩陣的特征多項式為 = = =,所以特征值是=4,=3（二重）,=2.由此可知該圖的拉普拉斯矩陣的最小特征值是2,第二小特征值是3,那么我們把3代入其次方程組得到方程組則該方程組的系數(shù)矩陣為則它的增廣矩陣為因為系數(shù)矩陣的秩為=4,增廣矩陣的秩為=4,所以=4.故方程組有唯一解=0,從而圖的fielder向量為,即為零向量. 例2 求

13、圖-2的fielder向量 圖-2 解 由圖可知圖的鄰接矩陣為,度矩陣為laplace矩陣為容易求得,圖的laplace矩陣的所有特征值,按從大到小的順序排列為：,=1（二重）,.于是圖的laplace矩陣的第二小特征值為,把帶入下面的齊次方程組得到方程組解得,.所以此圖的fielder向量為（其中為任意實數(shù)）.求fielder向量的步驟可以歸納如下：第一步：寫出圖的鄰接矩陣和度矩陣.第二步：用圖的度矩陣和鄰接矩陣做差求出圖的laplace矩陣即.第三步：求出laplace矩陣的所有特征值,并按從大到小的順序排列,則就是圖的laplace矩陣的次小特征值.第四步：根據(jù)第三步求出次小特征值求其所

14、對應(yīng)的特征向量即就是所要求的fielder向量.4 運用圖的fielder向量判斷圖的連通性由前面的fielder證明可知,圖是聯(lián)通的當(dāng)且僅當(dāng)?shù)牡诙€最小的拉普拉斯特征值 (即圖的fielder向量所對應(yīng)的特征值）.因此,被fielder稱為是圖的代數(shù)連通度,記為.下面我們給出兩個通過比較與0的大小關(guān)系來判斷圖的連通性：例3 判斷圖-3的連通性： 圖-3解 由圖可知圖的鄰接矩陣為度矩陣為則圖的laplace矩陣為則由求得laplace矩陣的所有特征值,按從大到小的順序為=4（二重）,=3,=2,.很明顯圖的laplace矩陣的第二小特征值（fielder向量所對應(yīng)特征值）為所以該圖是聯(lián)通圖.例

15、4 判斷圖-2的連通性 圖-2 解 由圖可知圖的鄰接矩陣為度矩陣為 laplace矩陣為則通過求圖的laplace矩陣的所有特征值,按從大到小的順序排列為,=1（二重）,.即圖的laplace矩陣的第二小特征值為 亦即,所以該圖是連通圖.5 基于fielder向量的基因表達譜數(shù)據(jù)分類方法利用基因表達數(shù)據(jù)進行癌癥的分類與識別是當(dāng)前生物信息學(xué)研究的主要方向之一.很多科學(xué)家嘗試將一種基于圖的fielder向量的聚類算法引入到基因表達譜數(shù)據(jù)的腫瘤分類中來.該方法將分屬不同類的所有樣本通過高斯權(quán)構(gòu)造laplace完全圖, 經(jīng)svd分解后獲得fielder向量,利用各個樣本所對應(yīng)的fielder向量的分量

16、的符號差異來進行基因表達譜數(shù)據(jù)的分類.通過模擬數(shù)據(jù)仿真實驗和對白血病兩個亞型(all與aml)及結(jié)腸癌真實數(shù)據(jù)實驗12.6 結(jié)束語圖的fielder向量即就是圖的laplace矩陣的次小特征值所對應(yīng)的向量.在fielder向量的應(yīng)用中較為普遍的是通過fielder向量所對應(yīng)的特征值與零的大小關(guān)系來判斷圖的連通性,當(dāng)時,圖是連通的;相反當(dāng)時,圖是不連通的.參考文獻1 尚文.圖的最大和次小拉普拉斯特征值a.碩士論文.成都:電子科技大學(xué),2005,31-38.2 郭繼明.圖的拉普拉斯特征值d.博士學(xué)位論文.上海:同濟大學(xué)理學(xué)院,2006,3-4.3 梁昊.圖的拉普拉斯矩陣和臨界群d.博士學(xué)位論文.中

17、國科學(xué)技術(shù)大學(xué),2009,4-5.4 張曉東,李炯生. 樹的laplace矩陣的最大和次大特征值 j .中國科學(xué)技術(shù)大學(xué)學(xué)報, 1998, 28( 5): 513- 518.5 郭曙光.單圈圖的laplace矩陣的最大特征值 j .高校應(yīng)用數(shù)學(xué)學(xué)報, 2001, 16a: 131- 136.6 王樹禾.圖論m.北京:科學(xué)出版社,20009,10-11.7 孫房,徐美進,支路.圖的擬拉普拉斯矩陣的永久式j(luò).遼寧工業(yè)大學(xué)學(xué)報,2008,28(6):1-2.8 張海霞.關(guān)于圖的laplace特征值a.碩士論文.大連理工大學(xué),2005,4-15.9 李鋒,陸韜.任意圖同構(gòu)判定及其應(yīng)用j.上海:復(fù)旦大學(xué)

18、學(xué)報,2006,45(4):1-2.10 張雪飛,王世英.完全偶圖的定想圖j.山西大學(xué)學(xué)報,2013,26(3):2-3.11 龔世才.圖的特征向量的組合結(jié)構(gòu)d.博士學(xué)位論文.安徽大學(xué),2010,1-3.12 王年,莊振華,唐俊,蘇亮亮.基于fielder向量的基因表達譜數(shù)據(jù)分類方法j.中國生物雜志,2010,30(12):82-86.13 lijianxi ,guo ji-ming .the smallest values of algebraic connectivity for unicyclic graphsj.journal of zhangzhou normal university,zhangzhou fujian,china,2010,1635:1-2.14 zhangxiao dong,two sharp upper bounds for the laplace eigenvaluesj.linear algebra and its applicati-ons, 2004,376:2