數(shù)學(xué)與應(yīng)用數(shù)學(xué)畢業(yè)論文-關(guān)聯(lián)矩陣地性質(zhì)及應(yīng)用

關(guān)聯(lián)矩陣的性質(zhì)及應(yīng)用作者：魏美玉指導(dǎo)老師：劉春奇摘要：用關(guān)聯(lián)矩陣來表示圖，不僅在理論上便于利用代數(shù)知識研究圖的性質(zhì)，構(gòu)造算法；而且也便于計(jì)算機(jī)處理，在實(shí)際應(yīng)用中也具有重要作用。關(guān)聯(lián)矩陣，用它來解決數(shù)學(xué)中的建模問題能使得問題更直觀，起到化繁為簡的作用。對于關(guān)聯(lián)矩陣的研究，以下陳述關(guān)聯(lián)矩陣的性質(zhì)，說明關(guān)聯(lián)矩陣性質(zhì)的應(yīng)用。主要收集有關(guān)關(guān)聯(lián)矩陣的性質(zhì)的應(yīng)用的資料，并就資料列出相對應(yīng)的性質(zhì)。關(guān)鍵詞：關(guān)聯(lián)矩陣；有向圖；無向圖；圖的矩陣在圖論中，任給一個圖（包括有向圖和無向圖），都可以根據(jù)其點(diǎn)與邊的關(guān)聯(lián)關(guān)系，作出圖關(guān)聯(lián)矩陣。一個圖的完全關(guān)聯(lián)矩陣的行刻畫了該圖的相應(yīng)頂點(diǎn)的關(guān)聯(lián)集，因此，完全關(guān)聯(lián)矩陣的行，給出了一個圖的全部關(guān)聯(lián)集。一個圖的完全關(guān)聯(lián)矩陣，描述了這個圖的全部頂點(diǎn)和邊的關(guān)聯(lián)關(guān)系，而一個圖的最基本的內(nèi)容就是這種關(guān)聯(lián)關(guān)系。因此，一個圖的完全關(guān)聯(lián)矩陣可以用來描述圖的特征。1關(guān)聯(lián)矩陣的基本概念1.1無向圖的完全關(guān)聯(lián)矩陣的定義給定無向圖，令=則由元素構(gòu)成的矩陣為圖的完全關(guān)聯(lián)矩陣（Completeincidencematrix）,記作。.例1求如圖1-1所示的圖的完全關(guān)聯(lián)矩陣.。用行表示頂點(diǎn)，列表示邊，由圖1-1可知（圖1-1）.=矩陣記號左邊的1,2,3,4,5表示圖的頂點(diǎn)，矩陣記號上面的表示圖的邊。這樣，第一行標(biāo)有1的那些元素，表示與頂點(diǎn)1關(guān)聯(lián)的邊，即頂點(diǎn)1的關(guān)聯(lián)集；第二行標(biāo)有1的那些元素，表示與頂點(diǎn)2關(guān)聯(lián)的所有邊，即頂點(diǎn)2的關(guān)聯(lián)集等等。一個圖的完全關(guān)聯(lián)矩陣的行刻畫了該圖的相應(yīng)頂點(diǎn)的關(guān)聯(lián)集，因此，完全關(guān)聯(lián)矩陣的行，給出了一個圖的全部關(guān)聯(lián)集。因?yàn)橥耆P(guān)聯(lián)矩陣的列表示圖的邊，又每一條邊有兩個端點(diǎn)，所以，在完全關(guān)聯(lián)矩陣的每一列中有兩個1，其余的元素均為零。一個圖的完全關(guān)聯(lián)矩陣，描述了這個圖的全部頂點(diǎn)和邊的關(guān)聯(lián)關(guān)系，而一個圖的最基本的內(nèi)容就是這種關(guān)聯(lián)關(guān)系。因此，一個圖的完全關(guān)聯(lián)矩陣可以用來描述圖的特征。1.2圖的關(guān)聯(lián)矩陣和參考點(diǎn)的定義在階連通的完全關(guān)聯(lián)矩陣中，劃去任一行后得到的矩陣，稱為圖的關(guān)聯(lián)矩陣（incidencematrix），記作。劃去的行所對應(yīng)的頂點(diǎn)稱為參考點(diǎn)（referencevertex）。例2在圖1所示的圖的完全關(guān)聯(lián)矩陣中去掉最后一行即得圖的一個關(guān)聯(lián)矩陣：頂點(diǎn)5是參考點(diǎn)。1.3大子陣的定義矩陣的一個階為的方陣，稱為矩陣的一個大子陣，大子陣定義的行列式稱為大行列式。1.4有向圖的完全關(guān)聯(lián)矩陣的定義設(shè)是有個頂點(diǎn)，條弧的有向圖，令則稱元素構(gòu)成的矩陣為有向圖的完全關(guān)聯(lián)矩陣，記作。從中去掉一行，且秩為的矩陣，稱為的關(guān)聯(lián)矩陣，記作。例3求如圖1-2所示的有向圖的完全關(guān)聯(lián)矩陣。（圖1-2）的完全關(guān)聯(lián)矩陣是的關(guān)聯(lián)矩陣是定點(diǎn)5為參考點(diǎn)。2關(guān)聯(lián)矩陣的性質(zhì)2.1無向圖的關(guān)聯(lián)矩陣的性質(zhì)引理2.1.1階圖是連通的當(dāng)且僅當(dāng)?shù)耐耆P(guān)聯(lián)矩陣的秩是。證明：（1）階連通圖的完全關(guān)聯(lián)矩陣的秩為。由線性代數(shù)知，一個矩陣的行向量組的秩就是這個矩陣的秩。把完全關(guān)聯(lián)矩陣的行看作是一個向量，那么完全關(guān)聯(lián)矩陣的行向量組就是圖的全部關(guān)聯(lián)集，由階連通圖恰有個線性無關(guān)的關(guān)聯(lián)集可知，完全關(guān)聯(lián)矩陣的秩為。（2）圖的完全關(guān)聯(lián)矩陣的秩等于的秩。設(shè)圖是由個分支組成的分離圖，的頂點(diǎn)數(shù)和邊數(shù)分別為和。調(diào)整的行和列的次序，使它滿足：最上面的行表示的頂點(diǎn)，接著的行表示的頂點(diǎn)，直到最下面的行表示的頂點(diǎn)；最左邊的列表示的邊，接著的列表示的邊，知道最右邊的列表示的邊。這樣把寫成如下形式的分塊矩陣：=其中是分支的完全關(guān)聯(lián)矩陣。因?yàn)槭沁B通的，所以的秩是，因此分塊矩陣的秩是，即的秩等于圖的秩。（3）因?yàn)橥耆P(guān)聯(lián)矩陣的所有的行表示了圖全部關(guān)聯(lián)集，故由圖中任意頂點(diǎn)的關(guān)聯(lián)集等于其余頂點(diǎn)關(guān)聯(lián)集的環(huán)合可知，矩陣的任一行，都可以表示成其余行的線性組合。因此，把矩陣的任意行劃掉后，所得的矩陣，實(shí)際上仍然包含了的全部內(nèi)容，也就是仍然可以描述圖的全部特征。引理2.1.2連通圖的關(guān)聯(lián)矩陣的一個大子陣是非奇異的充要條件為與這個大子陣的列相應(yīng)的邊，組成的一顆生成樹。證明：設(shè)是的一個大子陣，顯然是一個階方陣。如果是非奇異的，設(shè)與的列相應(yīng)的邊組成的子圖為.因?yàn)橛行?，故?yīng)有個頂點(diǎn)（包括參考點(diǎn)），有列，則有條邊。又因是非奇異的，即的秩是，所以是連通的，這就是說，是有個頂點(diǎn)，條的連通圖。因此是一顆生成樹。必要性得證。反之，如果的列所對應(yīng)的邊，組成的一顆生成樹。因?yàn)闃涫沁B通的，由定理1知，的秩是，故為非奇異。根據(jù)引理，連通圖中必存在生成樹與關(guān)聯(lián)矩陣的非奇異大子陣有一一對應(yīng)的關(guān)系。由此可以得出求圖的全部生成樹的一種方法：找出圖的關(guān)聯(lián)矩陣的全部非奇異大子陣，每一個大子陣的列所對應(yīng)的邊就組成的一顆生成樹。2.2有向圖的關(guān)聯(lián)矩陣的性質(zhì)引理2.2.1設(shè)有向圖有個頂點(diǎn)，那么的完全關(guān)聯(lián)矩陣的秩是。引理2.2.2階有向連通圖的關(guān)聯(lián)矩陣的一個大子陣是非奇異的充要條件為此大子陣的列對應(yīng)的一顆生成樹的樹枝。引理2.2.3設(shè)是有向圖的關(guān)聯(lián)矩陣的一非奇異大子陣，那么的行列式的值為1或-1。證明：由假設(shè)中至少有一列僅有一個非零元素。假如不然，的每一列均有兩個非零元素，則一個為1，另一個為-1。把的前行都加到最后一行，那么最后一行的元素均為零，這與是非奇異的假設(shè)矛盾。設(shè)中第列的元素除外，其余的元素均為零。把按第列展開，有（*）其中是中的余子式。子陣至少有一列僅有一個非零元素，否則可以推出，從而由（*），有，這與假設(shè)矛盾。設(shè)中第列除第行的元素為1或-1，其余元素均為零，則有其中是中元素的余子式。依此類推，可知。引理2.2.4畢內(nèi)-柯西定理設(shè)分別是矩陣則乘積的行列式是的所有對應(yīng)的大行列式乘積的和，即這里所謂的對應(yīng)大行列式分別是由得第列和的行組成，即若取的大行列式為列，則的對應(yīng)大行列式為行。引理2.2.5連通圖的全部生成樹的數(shù)目是其中為的關(guān)聯(lián)矩陣。證明：顯然，關(guān)聯(lián)矩陣滿足畢內(nèi)-柯西定理的條件，故由畢內(nèi)-柯西定理有（**）因?yàn)楫?dāng)且僅當(dāng)?shù)拇笞雨嚨牧袑?yīng)的一顆生成樹時，此大子陣才是非奇異的。再由引理2.3.3知，的非奇異大子陣的行列式的值為1或-1，于是由（**）式有生成樹的數(shù)目。例4求如圖2-1所示的有向圖的生成樹的數(shù)目。（圖2-2）的關(guān)聯(lián)矩陣是而于是順便指出，圖所示的基礎(chǔ)圖的生成樹的數(shù)目也是24。因此，對無向圖來說，只要對任意定向，再利用引理2.2.4可求出的生成樹的數(shù)目。2.3關(guān)聯(lián)矩陣和割矩陣、圈矩陣的關(guān)系引理2.3.1設(shè)，分別是圖的關(guān)聯(lián)矩陣和割集矩陣，那么存在一個非奇異矩陣使引理2.3.2連通圖的關(guān)聯(lián)矩陣和完全圈矩陣滿足,，其中，分別是，的轉(zhuǎn)置矩陣。證明：調(diào)整，的列的次序，使得和的列按相同的邊的次序排列。把，按行分塊，寫成列矩陣：，其中。根據(jù)分塊矩陣的乘法，有其中（***）我們來考察（***）式。顯然，當(dāng),只有當(dāng)表示邊與頂點(diǎn)關(guān)聯(lián),表示邊在第個環(huán)路中。于是表示頂點(diǎn)在第個環(huán)路中，從而頂點(diǎn)的度為偶數(shù)。又頂點(diǎn)在環(huán)路中的度就是等式（***）右端的非零項(xiàng)項(xiàng)數(shù)。因而有（模2加法)這就是說，的每一個元素均為零，于是從而又有引理2.3.3設(shè)分別是圖的關(guān)聯(lián)矩陣和圈矩陣，則,證明：調(diào)整完全圈矩陣的行的次序，使由定理6，有引理2.3.4設(shè)圖的關(guān)聯(lián)矩陣和基本圈矩陣分別寫成證明：其中對應(yīng)生成樹的連枝，那么由定理6，有于是因?yàn)槭欠瞧娈惖?，故有從而?關(guān)聯(lián)矩陣的應(yīng)用利用關(guān)聯(lián)矩陣解決一些數(shù)學(xué)方面的和實(shí)際應(yīng)用方面的問題，能使紛繁復(fù)雜的數(shù)量關(guān)系有條不紊的擺在人們面前，將問題化繁為簡，幫助人們找到解決問題的正確途徑。比如，關(guān)聯(lián)矩陣在解決數(shù)學(xué)方面的應(yīng)用中利用關(guān)聯(lián)矩陣來求出圖的全部生成樹。找出圖的關(guān)聯(lián)矩陣的全部非奇異大子陣，每一個大子陣的列所對應(yīng)的邊就組成的一顆生成樹。設(shè)計(jì)關(guān)聯(lián)矩陣智能分解方法，基于問題分解實(shí)現(xiàn)原理是將設(shè)計(jì)關(guān)聯(lián)矩陣，分解成塊狀對角陣，然后根據(jù)對較塊來分解設(shè)計(jì)問題。由圖的關(guān)聯(lián)矩陣，通過逐次極大全1子矩陣序列或元素全為1的極大對角塊矩陣，給出了物品分區(qū)的代數(shù)求法，關(guān)聯(lián)矩陣法等實(shí)際問題方面，關(guān)聯(lián)矩陣的應(yīng)用也很廣泛。結(jié)論：關(guān)聯(lián)矩陣的性質(zhì)及應(yīng)用還有很多，比如關(guān)聯(lián)矩陣和割集矩陣，圈矩陣間的關(guān)系，關(guān)聯(lián)矩陣在電學(xué)、計(jì)算機(jī)、和集合相容性檢驗(yàn)等方面和實(shí)際生活中應(yīng)用很廣泛?？傊?，關(guān)聯(lián)矩陣的作用作為數(shù)學(xué)基礎(chǔ)有很廣泛的用途，在不同的領(lǐng)域都能發(fā)揮其獨(dú)特的作用，只要應(yīng)用得好，肯定可以使原有的問題簡單切易于解決。參考文獻(xiàn)：[1]王朝陽.圖論.北京理工大學(xué)出版社（北京）.ISBN7-81045-245-2[2]管梅谷.有趣的圖論.山東科學(xué)技術(shù)出版社.1986（6）.[3]戴一齊，胡冠章，陳衛(wèi).圖論與代數(shù)結(jié)構(gòu)[M].北京清華大學(xué)出版社.1995[4]盧開澄，盧華明.圖論及其應(yīng)用[M].2版.北京清華大學(xué)出版社.1995[5]壽紀(jì)麟.數(shù)學(xué)建模[M].西安交通大學(xué)出版社.1996[6]胡慧蓉，王周敏.一種基于關(guān)系矩陣的關(guān)聯(lián)規(guī)則快速挖掘算法[J].計(jì)算機(jī)應(yīng)用.2005，（7）.1577-1579[7]陳樹柏.網(wǎng)絡(luò)圖論及其應(yīng)用.科學(xué)出版社.1982[8]孫慧泉.圖論及其應(yīng)用[M].北京科學(xué)出版社.2004[9]王與龍.等價關(guān)系與等價關(guān)系矩陣[J].蘭州工業(yè)高等?？茖W(xué)校學(xué)報.2005.3（1）.39-42[10]戴本祁，雷良?xì)J.由基本割集矩陣實(shí)現(xiàn)關(guān)聯(lián)矩陣的代數(shù)方法.江西工業(yè)大學(xué)學(xué)報.1990（4）謝辭光陰似箭，日月如棱。四年的時間，在我們漫長的人生旅途中是那么的短暫，但是，這短短的四年是最真誠的青春，是最純真的歲月，是最美麗的大學(xué)生活……我們的自學(xué)能力在這里得提升，我感謝所有的恩師：是您賦予我們最有意義的收獲；是您帶領(lǐng)我們走進(jìn)知識殿堂，使我們不但豐富了知識；是您給我們一個全新的角度去發(fā)現(xiàn)美、創(chuàng)造美、欣賞美，給我們美的眼睛去發(fā)現(xiàn)世界的美，感悟生活的美；是你教會我們珍惜友誼和時間；是您給了我們看世界的眼睛，是你們用博大的胸懷，給予我們最無私的關(guān)懷和奉獻(xiàn)。感謝各位老師在這幾年一直在生活中、組織上給予我的教導(dǎo)和無私的幫助，讓我在新疆農(nóng)業(yè)大學(xué)這個大舞臺上有鍛煉的能力、自我完善的平臺；感謝他們的教誨，讓我知道在社會上懂得怎樣去做好自己，端正自己的位置，為社會貢獻(xiàn)出我自己的力量。同時，經(jīng)過一個多