第二類型雙圈圖的距離矩陣的行列式畢業(yè)設(shè)計(jì)論文

1、本 科 生 畢 業(yè) 設(shè) 計(jì)（論文）（ 2013 屆）理學(xué)院題 目： 第二類型雙圈圖的距離矩陣的行列式 專業(yè)班級(jí)： 信息與計(jì)算科學(xué) 2013 年 5 月 15 日本科生畢業(yè)設(shè)計(jì)（論文）誠信承諾書我謹(jǐn)在此承諾：本人所寫的畢業(yè)設(shè)計(jì)（論文）第一類型雙圈圖的距離矩陣的行列式均系本人獨(dú)立完成，沒有抄襲行為，凡涉及其它作者的觀點(diǎn)和材料，均作了引用注釋，如出現(xiàn)抄襲及侵犯他人知識(shí)產(chǎn)權(quán)的情況，后果由本人承擔(dān)。 承諾人（簽名）： 年 月 日 關(guān)于第二類型雙圈圖的距離矩陣的行列式摘要 在圖論中，圖形都有自己的距離矩陣，距離矩陣即是是一個(gè)包含一組點(diǎn)兩兩之間距離的矩陣(即二維數(shù)組)。因此給定n個(gè)歐幾里得空間中的點(diǎn), 其距

2、離矩陣就是一個(gè)非負(fù)實(shí)數(shù)作為元素的nn的對(duì)稱矩陣。最簡(jiǎn)單的圖形就是樹，是由個(gè)頂點(diǎn)和條邊組成的一個(gè)不存在回路的圖。本文主要研究的是第二類型雙圈圖，即由個(gè)頂點(diǎn)和條邊組成的存在兩個(gè)回路且兩個(gè)回路之間沒有相交點(diǎn)的圖形。我們的主要工作就是通過matlab計(jì)算各個(gè)第二類型雙圈圖的距離矩陣的行列式并通過生成函數(shù)尋找其中的規(guī)律。關(guān)鍵詞 距離矩陣;樹;第二類型雙圈圖;生成函數(shù)on the determinant of the second typ graphsabstract：in graph theory, the graphics have their own distance matrix, distanc

3、e matrix that contains a set point or two between distance matrix (two-dimensional array). therefore, given n points in the euclidean space, the distance matrix is a non-negative real numbers as elements of n n symmetric matrix. the most simple graph is a tree, consisting of a non-existent by the ve

4、rtices and edges in the circuit of fig. this paper studies the second type of bicyclic graphs, graphics there is no point of intersection between the two loops and two loops composed by vertices and edges. our main job is to calculate the determinant of the matrix of distance of the second type of b

5、icyclic graphs by useing matlab and by the generating function to find the law.顯示對(duì)應(yīng)的拉丁字符的拼音keywords：distance matrices,tree,the second type of bicyclic graphs,generating function目 錄1 研究背景.62 基本概念.63 預(yù)備知識(shí).74 第二類型雙圈圖的行列式 .10 4.1數(shù)據(jù)計(jì)算. 10 4.2數(shù)據(jù)處理. 13參考文獻(xiàn).16致謝.171研究背景 圖論從誕生至今已逾300年，在很多方面都有應(yīng)用。隨著現(xiàn)在技術(shù)的發(fā)展，代數(shù)圖

6、論是現(xiàn)在圖論中的一個(gè)主要研究領(lǐng)域，也已有很長的歷史。圖論的代數(shù)表示形式主要有： 1.圖的laplace矩陣2.圖的鄰接矩陣研究者不斷嘗試圖的其它矩陣表示.1.正規(guī)laplace矩陣2.混合圖laplace矩陣3.無符號(hào)laplace矩陣 近年來，圖的距離矩陣越來越受到人們的關(guān)注，很多人已經(jīng)對(duì)它進(jìn)行了研究，其中最主要的是在1971年，graham和pollack證明了樹的距離矩陣的行列式是一個(gè)定值，即2005年，r.bapat,s.j.kirkland和m.neumann等進(jìn)一步研究了賦權(quán)樹和單圈圖的距離矩陣。本文安排如下：首先我們給出與本篇論文相關(guān)的一些概念和理論，如樹、單圈圖、雙圈圖、距離矩

7、陣、生成函數(shù)。接下來我們將計(jì)算基本的第二類型雙圈圖以及通過加邊而生成的圖形的距離矩陣的行列式并尋找它們之間的規(guī)律。2基本概念2.1 距離矩陣 對(duì)于一個(gè)圖(圖1)，我們可以根據(jù)圖各個(gè)點(diǎn)之間的距離關(guān)系列出它的距離矩陣，其中：其中表示和之間的距離。 圖12.2 樹 在圖論中，樹(圖2)是任意兩個(gè)頂點(diǎn)間有且只有一條路徑的圖。 或者說，只要沒有回路的連通圖就是樹。 定義：如果一個(gè)無向簡(jiǎn)單圖滿足以下相互等價(jià)的條件之一，那么就是一棵樹。(1) 是沒有回路的連通圖。(2) 沒有回路，但是在內(nèi)添加任意一條邊，就會(huì)形成一個(gè)回路。(3) 是連通的，但是如果去掉一條邊，就不再連通。(4) 是連通的，并且3頂點(diǎn)的完全圖

8、不是的子圖。(5) 內(nèi)的任意兩個(gè)頂點(diǎn)能被唯一路徑所連通。(6) 是連通的，有條邊，并且沒有簡(jiǎn)單回路。 圖22.3 單圈圖定義：在圖論中，單圈圖即是由個(gè)頂點(diǎn)和條邊組成的存在一個(gè)回路的圖(圖3，圖4)。 圖3 圖4 定理1.1 d是有個(gè)頂點(diǎn)的圈的距離矩陣，然后定理 1.2 g是一個(gè)有個(gè)頂點(diǎn)且長度為的單圈圖。是g的距離矩陣。則，同時(shí)的慣性由給出。定理1.3 g是一個(gè)有個(gè)頂點(diǎn)切長度為的單圈圖。d是g的距離矩陣。則d的慣量是。2.4 雙圈圖一個(gè)含有條邊的連通圖稱為雙圈圖。第一類型雙圈圖：即由個(gè)頂點(diǎn)和條邊組成的存在兩個(gè)回路且兩個(gè)回路之間沒有相交邊的圖(圖5)。 圖5第二類型雙圈圖：即由個(gè)頂點(diǎn)和條邊組成的存

9、在兩個(gè)回路且兩個(gè)回路之間沒有相交點(diǎn)的圖(圖6). 圖63預(yù)備知識(shí)定理1. 距離矩陣的行列式，記作，數(shù)域上的矩陣的初等行變換是指下列三種變換：1)以中一個(gè)非零的數(shù)乘矩陣的某一行；2)把矩陣的某一行的倍加到另一行，這里是中任意一個(gè)數(shù)；3)互換矩陣中兩行的位置。定理2. 把一矩陣的行列互換，所得到的矩陣稱為的轉(zhuǎn)置，記為。定理3. 有時(shí)候我們把一個(gè)大矩陣看成是由一些小矩陣組成的，就如矩陣是由數(shù)組組成的一樣，特別是在運(yùn)算中，把這些小矩陣當(dāng)作數(shù)一樣來處理，這就是所謂的矩陣的分塊。定理4.生成函數(shù):設(shè)數(shù)列的生成函數(shù)，數(shù)列的生成函數(shù)，我們可以得到以下生成函數(shù)的性質(zhì)：性質(zhì)1 若 ，則。性質(zhì)2 若，則。性質(zhì)3若，

10、則。4第二類型雙圈圖的距離矩陣的行列式4.1數(shù)據(jù)計(jì)算首先我們研究最基本的第二類型雙圈圖(圖7)，以后我們可以再研究類似圖8這類的圖形。 圖7 圖8我們把稱為基本圖形，首先我們?cè)谏霞右粭l邊，計(jì)算其距離矩陣的行列式的值，然后依次計(jì)算加兩條邊和加三條邊的距離矩陣的行列式的值。然后猜想這些行列式的之間的關(guān)系。接下來我們可以計(jì)算以下各個(gè)加邊的第二類型雙圈圖的距離矩陣的行列式并尋找它們的規(guī)律。 以下是加兩條邊的情況： 接下來是加三條邊條邊的各種情況： 通過計(jì)算圖形編號(hào)行列式值-32-32-32-32-32-32-32圖像編號(hào)行列式的值8080 8080808080808080808080808080從上面

11、的計(jì)算結(jié)果可以知道對(duì)于一個(gè)基本的第二類型雙圈圖，只要加上的邊的個(gè)數(shù)是相同的，則他的距離矩陣的行列式的值是不變的。4.2數(shù)據(jù)處理接下來我們可以先研究下面這個(gè)圖形。 對(duì)于的距離矩陣的行列式，我們用表示行向量，表示值都是1的行向量，是一個(gè)行列式，是的轉(zhuǎn)置 。=圖和的距離矩陣的行列式正好可以表示為和，如果把的距離矩陣的行列式表達(dá)式記為，則和的距離矩陣的行列式分別為和，即。所以，可以得到。根據(jù)之前計(jì)算的結(jié)果，可以證明該表達(dá)式是正確的。接下來我們用生成函數(shù)求解遞推關(guān)系令 則有將代入上式并整理，得設(shè)其中，為待定系數(shù)，通過比較等式兩邊的常數(shù)項(xiàng)與一次項(xiàng)系數(shù)，可得所以，因此 對(duì)于這類加三條邊的第二類型雙圈圖，將代

12、入上式可得；與之前的計(jì)算結(jié)果一致,所以 為通項(xiàng)公式。參考文獻(xiàn)1 r.b. bapat, the laplacian matrix of a graph, math. student 65 (1996) 214223.2 n. dyn, w.a. light, e.w. cheney, interpolation by piecewise-linear radial basis functions i, j. approx. theory 59 (1989) 202223.3 r.l. graham, h.o. pollack, on the addressing problem for loo

13、p switching, bell system tech. j. 50(1971) 24952519.4 r.l. graham, l. lovsz, distance matrix polynomials of trees, adv. math. 29 (1) (1978) 6088.5 edward j. kaplan, mathematical programming and games, john wiley, 1982.6 r. merris, the distance spectrum of a tree, j. graph theory 14 (3) (1990) 365369

14、.7 r. merris, laplacian matrices of graphs: a survey, linear algebra appl. 197/198 (1994) 143176.8 t. parthasarathy, g. ravindran, n-matrices, linear algebra appl. 139 (1990) 89102.9 l. reid, x. sun, distance matrices and ridge function interpolation, can. j. math. 45 (6) (1993)13131323.10 x. sun, solvability of multivariate interpolation by radial or related functions, j. approx. theory 72(3) (1993) 252267.11王蕚芳,石生明,高等代數(shù)m.高等教育出版社,2003:290.12王貴平,王衍,任嘉辰. 圖論算法理論、實(shí)現(xiàn)及應(yīng)用m,北京：北京大學(xué)出版社,2011：88.13許胤龍，孫淑玲，組合數(shù)學(xué)引論m.中國科學(xué)技術(shù)大學(xué)出版社，2010：4.14胡良劍，孫曉君，matlab數(shù)學(xué)實(shí)驗(yàn)m.高等教育出版社，2006:6.致謝本論文在選題和撰寫過程中