《圖同構(gòu)的判定數(shù)學(xué)畢業(yè)論文》由會(huì)員分享，可在線閱讀，更多相關(guān)《圖同構(gòu)的判定數(shù)學(xué)畢業(yè)論文（21頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、平頂山學(xué)院本科畢業(yè)論文（設(shè)計(jì)） 畢業(yè)論文(設(shè)計(jì))題 目: 圖同構(gòu)的判定 院(系): 數(shù)學(xué)與信息科學(xué)學(xué)院 專(zhuān)業(yè)年級(jí): 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 姓 名: 學(xué) 號(hào): 指導(dǎo)教師: 2009年 04月 2日17 Thesis (design)Subject: Isomorphism Judgment of Graphs College: Mathematics and Information Science Major and Grade: Mathematics and Applied Mathematics, Grade 2005 Name: No.: Advisor: April 2 , 20093中文摘
2、要本文對(duì)于兩圖的同構(gòu)的判定方法進(jìn)行探討，通過(guò)同構(gòu)定義、鄰接矩陣、關(guān)聯(lián)度序列、出入度序列等方法判定兩圖同構(gòu)與否，并給出簡(jiǎn)單的應(yīng)用.關(guān)鍵詞 : 圖，同構(gòu)，鄰接矩陣，關(guān)聯(lián)度序列，出入度序列.AbstractAn interesting problem is to determine whether two graphs are isomorphic. The following is about some ways of the isomorphism definition,the adjacent matrix, the interrelatedness sequence,leaves in-de
3、gree sequence to show that two simple graphs are isomorphic or not, and meanwhile gives some simple application.Key words : graphs, isomorphism ，adjacent matrix，the interrelatedness sequence, leaves in-degree sequence .目 錄中文標(biāo)題 中文摘要 關(guān)鍵詞 英文標(biāo)題 英文摘要 關(guān)鍵詞 正文 11圖的同構(gòu)定義 12圖同構(gòu)判定及簡(jiǎn)單應(yīng)用 22.1用同構(gòu)定義判定圖同構(gòu) 22.2用鄰接矩陣判
4、定圖同構(gòu) 42.3用關(guān)聯(lián)度序列法判定同構(gòu) 82.4用出入度序列法判定同構(gòu) 103用不變量判定兩圖不同構(gòu) 12參考文獻(xiàn) 14致謝 “圖論”是數(shù)學(xué)的一個(gè)分支,它以圖為研究對(duì)象.圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系.圖論是一門(mén)極有興趣的學(xué)問(wèn)，其廣闊的應(yīng)用領(lǐng)域涵蓋了人類(lèi)學(xué)、計(jì)算機(jī)科學(xué)、化學(xué)、環(huán)境保護(hù)、電信領(lǐng)域等等.嚴(yán)格地講，圖論是組合數(shù)學(xué)的一個(gè)分支，例如，它交叉運(yùn)用了拓?fù)鋵W(xué)、群論和數(shù)論.圖論就是研究一些事物及它們之間關(guān)系的學(xué)科，現(xiàn)實(shí)世界中的許多事物能用圖來(lái)表示其拓?fù)浣Y(jié)構(gòu)，把實(shí)際問(wèn)
5、題的研究轉(zhuǎn)化為圖的研究，利用圖論的相關(guān)結(jié)論對(duì)這些問(wèn)題作分析或判斷.在抽象代數(shù)中，同構(gòu)指的是一個(gè)保持結(jié)構(gòu)的雙射.在更一般的范疇論語(yǔ)言中，同構(gòu)指的是一個(gè)態(tài)射，且存在另一個(gè)態(tài)射，使得兩者的復(fù)合是一個(gè)恒等態(tài)射.正式的表述是：同構(gòu)是在數(shù)學(xué)對(duì)象之間定義的一類(lèi)映射,它能揭示出在這些對(duì)象的屬性之間存在的關(guān)系.若兩個(gè)數(shù)學(xué)結(jié)構(gòu)之間存在同構(gòu)映射，那么這兩個(gè)結(jié)構(gòu)叫做是同構(gòu)的.一般來(lái)說(shuō)，如果忽略掉同構(gòu)的對(duì)象的屬性的具體定義，單從結(jié)構(gòu)上講，同構(gòu)的對(duì)象是完全等價(jià)的.在數(shù)學(xué)中研究同構(gòu)的主要目的是為了把數(shù)學(xué)理論應(yīng)用于不同的領(lǐng)域.如果兩個(gè)結(jié)構(gòu)是同構(gòu)的，那么其上的對(duì)象會(huì)有相似的屬性，對(duì)某個(gè)結(jié)構(gòu)成立的命題在另一個(gè)結(jié)構(gòu)上也就成立.因此
6、，如果在某個(gè)數(shù)學(xué)領(lǐng)域發(fā)現(xiàn)了一個(gè)對(duì)象結(jié)構(gòu)同構(gòu)于某個(gè)結(jié)構(gòu)，且對(duì)于該結(jié)構(gòu)已經(jīng)證明了很多定理，那么這些定理馬上就可以應(yīng)用到該領(lǐng)域.如果某些數(shù)學(xué)方法可以用于該結(jié)構(gòu)，那么這些方法也可以用于新領(lǐng)域的結(jié)構(gòu).圖的同構(gòu)是圖論學(xué)科中的基本問(wèn)題之一,屬于圖論中多個(gè)NP一完全問(wèn)題之一.所謂圖的同構(gòu),簡(jiǎn)單地說(shuō),就是兩個(gè)表示的關(guān)聯(lián)關(guān)系完全相同，圖同構(gòu)與抽象代數(shù)中提到的同構(gòu)密切聯(lián)系，兩個(gè)圖同構(gòu)意味著兩個(gè)圖具有完全相同的結(jié)構(gòu)特征，即如果能識(shí)別出兩個(gè)或多個(gè)圖是同構(gòu)的，則可以把這些圖的研究歸結(jié)為一個(gè)圖的研究，因此，對(duì)同構(gòu)圖的探討，無(wú)疑會(huì)給圖論中許多問(wèn)題的研究帶來(lái)方便.1.圖的同構(gòu)定義定義 設(shè)V和E是有限集合,且V不是空集,如果E是
7、 （, ）| V且V的子集,則稱(chēng)G=為無(wú)向圖;如果E是VV (集合的笛卡兒乘積)的子集,則稱(chēng)G=為有向圖。無(wú)向圖和有向圖統(tǒng)稱(chēng)為圖,其中V的元素稱(chēng)為圖G的結(jié)點(diǎn), E的元素稱(chēng)為圖G的邊,圖G的結(jié)點(diǎn)數(shù)目稱(chēng)為它的階.定義 設(shè)，為兩個(gè)無(wú)向圖（兩個(gè)有向圖），若存在雙射函數(shù),使得 ,當(dāng)且僅當(dāng) (當(dāng)且僅當(dāng))并且與（與）的重?cái)?shù)相同，則稱(chēng)和同構(gòu)，記作,稱(chēng)作到的同構(gòu)函數(shù).圖之間的同構(gòu)關(guān)系構(gòu)成全體圖集合上的特殊二元關(guān)系等價(jià)關(guān)系，事實(shí)上，(1) (自反性);(2)若,則 (對(duì)稱(chēng)性);(3)若,則 (傳遞性).在這個(gè)等價(jià)關(guān)系的每一個(gè)等價(jià)類(lèi)中的圖都是同構(gòu)的.2.圖同構(gòu)判定及簡(jiǎn)單應(yīng)用2.1用同構(gòu)定義判定圖同構(gòu)由于圖包括無(wú)向圖
8、和有向圖,所以可以把圖同構(gòu)的定義重新定義為無(wú)向圖同構(gòu)和有向圖同構(gòu),即1)若無(wú)向圖和的頂點(diǎn)之間保持一一對(duì)應(yīng),邊之間也保持一一對(duì)應(yīng),則兩圖同構(gòu).2) 若有向圖和的頂點(diǎn)之間保持一一對(duì)應(yīng),邊之間保持一一對(duì)應(yīng),而且對(duì)應(yīng)點(diǎn)與對(duì)應(yīng)邊之間保持相同的關(guān)聯(lián)關(guān)系,則兩圖同構(gòu).例1 判定下面兩個(gè)圖，同構(gòu). ， 證明 取 , ， , .以上是點(diǎn)的對(duì)應(yīng)，下面是邊的對(duì)應(yīng): 綜上所述，為雙射函數(shù)，根據(jù)同構(gòu)的定義，同構(gòu).例2 判定下面兩圖同構(gòu). 證明 取 ： , , , .以上是點(diǎn)的對(duì)應(yīng)，下面是邊的對(duì)應(yīng): 綜上所述，g 為雙射函數(shù)，根據(jù)圖同構(gòu)定義，以上兩圖同構(gòu).總之,通過(guò)圖同構(gòu)定義，只要找到點(diǎn)與點(diǎn)，邊與邊之間的一一對(duì)應(yīng)，并且它
9、們之間保持相同的關(guān)聯(lián)關(guān)系,就可判定兩圖同構(gòu).但有時(shí)為了方便找對(duì)應(yīng)關(guān)系，可以先列個(gè)圖表表示結(jié)點(diǎn)間的關(guān)聯(lián)度.如例2,可以通過(guò)表1觀察到點(diǎn)對(duì)應(yīng)：或，然后再找邊對(duì)應(yīng)，就可以判定兩圖同構(gòu).表1 通過(guò)圖同構(gòu)定義，了解同構(gòu)可以用直觀扮析方法:把線看作可伸縮的橡皮筋,把點(diǎn)看作固定這些橡皮筋的圖釘.如果把一個(gè)圖的某些“圖釘”連同“橡皮筋”取下,釘在平面上的其他位置,得到與另一個(gè)圖相同的結(jié)構(gòu)和形狀,則這兩個(gè)圖一定同構(gòu).如上例1,把的結(jié)點(diǎn)1移至邊（2 , 3）的左下方,再把整個(gè)圖順時(shí)針旋轉(zhuǎn)90,即得到圖.2.2 用鄰接矩陣判定圖同構(gòu)定義 設(shè)圖G=,V=，令為頂點(diǎn)鄰接到頂點(diǎn)邊的條數(shù)，稱(chēng)為G的鄰接矩陣，記作,或簡(jiǎn)記為A
10、. 通過(guò)例2圖表的提示以及定義2.2.1知道可以把點(diǎn)與點(diǎn)，邊與邊之間的一一對(duì)應(yīng)用鄰接矩陣表示出來(lái).定理 如果圖和圖是同構(gòu)的當(dāng)且僅當(dāng)對(duì)某一頂點(diǎn)的順序,他們的鄰接矩陣是一樣的.例3 判定以下兩圖同構(gòu). 分析 為證明圖同構(gòu)，必須使結(jié)點(diǎn)，邊一一對(duì)應(yīng)，保持結(jié)點(diǎn)鄰接性，此題兩圖都有5個(gè)頂點(diǎn)8條邊，1個(gè)結(jié)點(diǎn)2度，2個(gè)結(jié)點(diǎn)3度，2個(gè)結(jié)點(diǎn)4度，很顯然，c與2對(duì)應(yīng)（都2度），又因?yàn)閳D的對(duì)稱(chēng)性，a與e 、b與d是對(duì)稱(chēng)的，b與3度的a相鄰，3與3度的1、4相鄰，可以任意選，如選a與1相鄰，則可確定點(diǎn)的對(duì)應(yīng).證明 取 ： , , , , .A (1) = , A (2) = 即A (1)= A (2)，由定理2.2.1
11、知，以上兩圖同構(gòu).例4 判定如下兩圖同構(gòu). 證明 取 ： , , , , , , . A(1)= , A(2) =即A (1)= A (2)，由定理2.2.1知，以上兩圖同構(gòu). 定義 對(duì)矩陣A= 施行第1種初等行(或列)變換,是指交換矩陣A的2行(或2列).交換A的第行和第行記為,交換A的第列和第j列記為.定義 設(shè)A= 是一個(gè)n階方陣,對(duì)任意選定的正整數(shù),如果對(duì)矩陣A同時(shí)進(jìn)行第一種初等變換與第一種初等列變換得到B,則稱(chēng)對(duì)A施行了一次對(duì)稱(chēng)變換得到矩陣B.記為.定理 n階標(biāo)定圖與同構(gòu)的充要條件是存在的同構(gòu)變換,使得化成.一般而言,待判定圖頂點(diǎn)對(duì)應(yīng)關(guān)系是未知的,而同構(gòu)判定正是要找出這樣的對(duì)應(yīng)關(guān)系.通
12、過(guò)定理2.2.2很容易判定圖同構(gòu),即,先寫(xiě)出與的與,然后調(diào)整的行序和列序(行的交換與列的交換),如能使,則,如所有可能的行交換與列交換都不能使,則判定與兩圖不同構(gòu).例3(續(xù))分析 在例3中,首先找到點(diǎn)的對(duì)應(yīng),在利用定理2.2.1判定圖同構(gòu).而給出定理2.2.2之后,發(fā)現(xiàn)判定圖同構(gòu)時(shí)用定理2.2.2方便了很多,即,不必先找到點(diǎn)的對(duì)應(yīng), 直接把鄰接矩陣寫(xiě)出就可以了.證明 = , = =由定理2.2.2知，兩圖同構(gòu).在以上例題中,也可找到點(diǎn)的對(duì)應(yīng).2.3 用關(guān)聯(lián)度序列判定同構(gòu)定義 如果無(wú)向圖G中n(1nN,N為G的數(shù))個(gè)點(diǎn)以及連接于這n個(gè)點(diǎn)之間的邊組成的子圖是連通的,那么,這個(gè)子圖稱(chēng)為圖G的n點(diǎn)連通
13、子圖,記為, 是這n個(gè)點(diǎn)的集合.定義在無(wú)向圖G中,與一個(gè)n點(diǎn)連通子圖相連接的邊(不包括的內(nèi)部邊)稱(chēng)為關(guān)聯(lián)邊.關(guān)聯(lián)邊的邊數(shù)稱(chēng)為的關(guān)聯(lián)度,記作.定義若無(wú)向圖G的n點(diǎn)連通子圖一共有P個(gè),則將這P個(gè)n點(diǎn)連通子圖的關(guān)聯(lián)度按從大到小的順序排列起來(lái)所得到的有序集合稱(chēng)為n點(diǎn)連通子圖的關(guān)聯(lián)度序列,記為.定理 與同構(gòu)的充要條件是, 與的n點(diǎn)連通子圖的關(guān)聯(lián)度序列分別為與,那么對(duì)所有的n都有= ,n=1,2,N-1.這里N是圖或的點(diǎn)數(shù).例1(續(xù))證明 , , , .即 . , , , .即 . , , , , .即 . , , , , .即 . , , , .即 . , , , .即 .由于 , ,所以?xún)蓤D同構(gòu).用此
14、定理2.3.1的逆否命題判定不同構(gòu)時(shí)比較方便，只要找到一個(gè)，即可.例4 判定如下兩圖同構(gòu). 證明 即. 即.即 .,即.即 .即 .雖然 , ，但是即兩圖不同構(gòu).2.4 用出入度序列法判定同構(gòu)定義在有向圖G中,與一個(gè)n點(diǎn)連通子圖G()相連接的邊(不包括G()的內(nèi)部邊)稱(chēng)為關(guān)聯(lián)邊.關(guān)聯(lián)邊中方向指向這個(gè)子圖的邊稱(chēng)為入邊，方向離開(kāi)這個(gè)子圖的邊稱(chēng)為出邊，入邊的數(shù)目稱(chēng)為G()的入度,記作，出邊的數(shù)目稱(chēng)為G()的出度，記為.定義 若有向圖G的n點(diǎn)連通子圖一共有P個(gè),則將這P個(gè)n點(diǎn)連通子圖的出度按從大到小的順序排列起來(lái)所得到的有序集合稱(chēng)為n點(diǎn)連通子圖的出度序列,記為；將這P個(gè)n點(diǎn)連通子圖的入度按從大到小的順
15、序排列起來(lái)所得到的有序集合稱(chēng)為n點(diǎn)連通子圖的入度序列,記為.定理 有向圖與同構(gòu)的充要條件是與的n點(diǎn)連通子圖的入度和出度序列分別為，,和,，那么對(duì)任一n都有，,這里N是圖與的點(diǎn)數(shù).例5 判定如下兩圖同構(gòu). 證明 即 .即 . 即 .即 . 即 .即 .即 .即 . 即 .即. 即. 即.由于所以?xún)蓤D同構(gòu).3. 用不變量判定兩圖不同構(gòu)對(duì)于兩圖和,我們可以找到一個(gè)的特性, 并不具備,則兩圖不同構(gòu)，但如果和是同構(gòu)的應(yīng)該具有這個(gè)特性,這個(gè)特性稱(chēng)為不變量,更精確地說(shuō),一個(gè)特性P是不變量當(dāng)和是同構(gòu)圖時(shí),如果具有特性P,那么也具有特性P.命題3.1 同構(gòu)的圖具有的頂點(diǎn)數(shù)是不變量.命題3.2 同構(gòu)的圖具有的邊數(shù)
16、是不變量.命題3.3 同構(gòu)的圖具有的頂點(diǎn)度是不變量.命題3.4 同構(gòu)的圖度數(shù)相同的結(jié)點(diǎn)數(shù)是不變量.命題3.5 同構(gòu)的圖邊數(shù)相同的回路數(shù)目是不變量.對(duì)于給定的圖如果這些不變量有任一不同，則不同構(gòu)，但是這些不變量相同，也不意味著兩圖一定同構(gòu).例如： （1） （2） （3） （4）如上圖，很顯然，（1）（2）兩圖很容易發(fā)現(xiàn)頂點(diǎn)數(shù)不同，所以不同構(gòu)，但是（3）（4）兩圖，不變量都相同，但是不管用哪種判定同構(gòu)的方法都不能判定兩個(gè)圖同構(gòu).事實(shí)上，不變量是同構(gòu)具有的性質(zhì)，即不變量不同，一定不同構(gòu)，但同構(gòu)時(shí)一定有不變量成立，可以綜述為以上命題為充分不必要條件.判定圖同構(gòu)主要找點(diǎn)與邊的雙射函數(shù)，如果找不到一定可以
17、找到不同的不變量，再判定圖同構(gòu)時(shí)可以先試著判定圖不同構(gòu)，這樣會(huì)方便許多.如不能找到不同的不變量，則利用以上討論的幾種方法判定同構(gòu)，在n很小時(shí)我們可以直觀的找到雙射函數(shù)，隨著n的增大，找點(diǎn)與點(diǎn)，邊與邊之間的對(duì)應(yīng)困難增大，我們可以用鄰接矩陣，關(guān)聯(lián)度序列，出入度序列等方法判定.但是隨著n的增大,判定圖同構(gòu)的時(shí)間復(fù)雜度就越大,所以我們?nèi)砸^續(xù)努力學(xué)習(xí),探討出比較方便快捷的方法.參考文獻(xiàn)1屈婉玲，耿素云，張立昂，離散數(shù)學(xué)M高等教育出版社，2008，277-278.2陳曉紅，王敏麗，關(guān)于圖的同構(gòu)方法的探討J大學(xué)數(shù)學(xué)，2006.4.22（2）.3費(fèi)本初,洪清華,謝繼國(guó),線性代數(shù)基本概念圖示M蘭州大學(xué)出版社.1989.4張效賢.圖構(gòu)圖的等價(jià)條件J甘肅科學(xué)學(xué)報(bào).2003.13(1). 5李鋒,圖的同構(gòu)判定算法:關(guān)聯(lián)度序列法及其應(yīng)用J,復(fù)旦學(xué)報(bào):自然科學(xué)版, 2001, 40(3).6李鋒,商慧亮,有向圖的同構(gòu)判定算法:出入度序列法J,應(yīng)用科學(xué)學(xué)報(bào), 2002, 20(3), 258-262.
圖同構(gòu)的判定數(shù)學(xué)畢業(yè)論文
