圖同構(gòu)的判定數(shù)學(xué)畢業(yè)論文

《圖同構(gòu)的判定數(shù)學(xué)畢業(yè)論文》由會員分享，可在線閱讀，更多相關(guān)《圖同構(gòu)的判定數(shù)學(xué)畢業(yè)論文（21頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、平頂山學(xué)院本科畢業(yè)論文（設(shè)計(jì)） 畢業(yè)論文(設(shè)計(jì)) 題 目: 圖同構(gòu)的判定 院(系): 數(shù)學(xué)與信息科學(xué)學(xué)院 專業(yè)年級: 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 姓 名: 學(xué) 號: 指導(dǎo)教師: 2009年 04月 2日 17 Thesis

2、(design) Subject: Isomorphism Judgment of Graphs College: Mathematics and Information Science Major and Grade: Mathematics and Applied Mathematics, Grade 2005 Name: No.: Advisor:

3、 April 2 , 2009 3 中文摘要 本文對于兩圖的同構(gòu)的判定方法進(jìn)行探討，通過同構(gòu)定義、鄰接矩陣、關(guān)聯(lián)度序列、出入度序列等方法判定兩圖同構(gòu)與否，并給出簡單的應(yīng)用. 關(guān)鍵詞 : 圖，同構(gòu)，鄰接矩陣，關(guān)聯(lián)度序列，出入度序列. Abstract An interesting problem is to determine whether two graphs are isomorphic. The following is about some ways of the isomorphism

4、 definition,the adjacent matrix, the interrelatedness sequence,leaves in-degree 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 .

5、 目 錄 中文標(biāo)題 中文摘要 關(guān)鍵詞 英文標(biāo)題 英文摘要 關(guān)鍵詞 正文 1 1圖的同構(gòu)定義 1 2圖同構(gòu)判定及簡單應(yīng)用 2 2.1用同構(gòu)定義判定圖同構(gòu) 2 2.2用鄰接矩陣判定圖同構(gòu) 4 2.3用關(guān)聯(lián)度序列法判定同構(gòu) 8 2.4用出入度序列法判定同構(gòu) 10 3用不變量判定兩圖不同構(gòu) 12 參考文獻(xiàn) 14 致謝 “圖論”是數(shù)學(xué)的一個(gè)分支,

6、它以圖為研究對象.圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系.圖論是一門極有興趣的學(xué)問，其廣闊的應(yīng)用領(lǐng)域涵蓋了人類學(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í)世界中的許多事物能用圖來表示其拓?fù)浣Y(jié)構(gòu)，把實(shí)際問題的研究轉(zhuǎn)化為圖的研究，利用圖論的相關(guān)結(jié)論對這些問題作分析或判斷. 在抽象代數(shù)中，同構(gòu)指的是一個(gè)保持結(jié)構(gòu)的雙射.在更一般的范疇論語言中，同構(gòu)指的是一個(gè)態(tài)

7、射，且存在另一個(gè)態(tài)射，使得兩者的復(fù)合是一個(gè)恒等態(tài)射.正式的表述是：同構(gòu)是在數(shù)學(xué)對象之間定義的一類映射,它能揭示出在這些對象的屬性之間存在的關(guān)系.若兩個(gè)數(shù)學(xué)結(jié)構(gòu)之間存在同構(gòu)映射，那么這兩個(gè)結(jié)構(gòu)叫做是同構(gòu)的.一般來說，如果忽略掉同構(gòu)的對象的屬性的具體定義，單從結(jié)構(gòu)上講，同構(gòu)的對象是完全等價(jià)的.在數(shù)學(xué)中研究同構(gòu)的主要目的是為了把數(shù)學(xué)理論應(yīng)用于不同的領(lǐng)域.如果兩個(gè)結(jié)構(gòu)是同構(gòu)的，那么其上的對象會有相似的屬性，對某個(gè)結(jié)構(gòu)成立的命題在另一個(gè)結(jié)構(gòu)上也就成立.因此，如果在某個(gè)數(shù)學(xué)領(lǐng)域發(fā)現(xiàn)了一個(gè)對象結(jié)構(gòu)同構(gòu)于某個(gè)結(jié)構(gòu)，且對于該結(jié)構(gòu)已經(jīng)證明了很多定理，那么這些定理馬上就可以應(yīng)用到該領(lǐng)域.如果某些數(shù)學(xué)方法可以用于該結(jié)

8、構(gòu)，那么這些方法也可以用于新領(lǐng)域的結(jié)構(gòu). 圖的同構(gòu)是圖論學(xué)科中的基本問題之一,屬于圖論中多個(gè)NP一完全問題之一.所謂圖的同構(gòu),簡單地說,就是兩個(gè)表示的關(guān)聯(lián)關(guān)系完全相同，圖同構(gòu)與抽象代數(shù)中提到的同構(gòu)密切聯(lián)系，兩個(gè)圖同構(gòu)意味著兩個(gè)圖具有完全相同的結(jié)構(gòu)特征，即如果能識別出兩個(gè)或多個(gè)圖是同構(gòu)的，則可以把這些圖的研究歸結(jié)為一個(gè)圖的研究，因此，對同構(gòu)圖的探討，無疑會給圖論中許多問題的研究帶來方便. 1.圖的同構(gòu)定義 定義 設(shè)V和E是有限集合,且V不是空集,如果E是{ （, ）| ∈V且∈V}的子集,則稱G=為無向圖;如果E是VV (集合的笛卡兒乘積)的子集,則稱G=為有

9、向圖。無向圖和有向圖統(tǒng)稱為圖,其中V的元素稱為圖G的結(jié)點(diǎn), E的元素稱為圖G的邊,圖G的結(jié)點(diǎn)數(shù)目稱為它的階. 定義 設(shè)，為兩個(gè)無向圖（兩個(gè)有向圖），若存在雙射函數(shù),使得 ,當(dāng)且僅當(dāng) (<,>當(dāng)且僅當(dāng))并且與（與）的重?cái)?shù)相同，則稱和同構(gòu)，記作,稱作到的同構(gòu)函數(shù). 圖之間的同構(gòu)關(guān)系構(gòu)成全體圖集合上的特殊二元關(guān)系——等價(jià)關(guān)系，事實(shí)上， (1) ≌ (自反性); (2)若≌,則≌ (對稱性); (3)若≌,≌,則≌ (傳遞性). 在這個(gè)等價(jià)關(guān)系的每一個(gè)等價(jià)類中的圖都是同構(gòu)的. 2.圖同構(gòu)判定及簡單應(yīng)用 2.1用同構(gòu)定義判定圖同構(gòu) 由于圖包括無向圖和有向圖,所以可以把圖同構(gòu)的定義重新

10、定義為無向圖同構(gòu)和有向圖同構(gòu),即 1)若無向圖和的頂點(diǎn)之間保持一一對應(yīng),邊之間也保持一一對應(yīng),則兩圖同構(gòu). 2) 若有向圖和的頂點(diǎn)之間保持一一對應(yīng),邊之間保持一一對應(yīng),而且對應(yīng)點(diǎn)與對應(yīng)邊之間保持相同的關(guān)聯(lián)關(guān)系,則兩圖同構(gòu). 例1 判定下面兩個(gè)圖，同構(gòu). ， 證明 取 , ， , . 以上是點(diǎn)的對應(yīng)，下面是邊的對應(yīng): 綜上所述，為雙射函數(shù)，根據(jù)同構(gòu)的定義，同構(gòu). 例2 判定下面兩圖同構(gòu).

11、 證明 取 ： , , , . 以上是點(diǎn)的對應(yīng)，下面是邊的對應(yīng): 綜上所述，g 為雙射函數(shù)，根據(jù)圖同構(gòu)定義，以上兩圖同構(gòu). 總之,通過圖同構(gòu)定義，只要找到點(diǎn)與點(diǎn)，邊與邊之間的一一對應(yīng)，并且它們之間保持相同的關(guān)聯(lián)關(guān)系,就可判定兩圖同構(gòu).但有時(shí)為了方便找對應(yīng)關(guān)系，可以先列個(gè)圖表表示結(jié)點(diǎn)間的關(guān)聯(lián)度.如例2,可以通過表1觀察到點(diǎn)對應(yīng)：或，然后再找邊對應(yīng)，就可以判定兩圖同構(gòu). 表1 通過圖同構(gòu)定義，了解同構(gòu)可以用直觀扮析方法:把線看作可伸縮的橡皮筋,把點(diǎn)看作固定這些橡皮筋的圖釘.如果把一個(gè)圖的某些“

12、圖釘”連同“橡皮筋”取下,釘在平面上的其他位置,得到與另一個(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ù)，稱為G的鄰接矩陣，記作,或簡記為A. 通過例2圖表的提示以及定義2.2.1知道可以把點(diǎn)與點(diǎn)，邊與邊之間的一一對應(yīng)用鄰接矩陣表示出來. 定理 如果圖和圖是同構(gòu)的當(dāng)且僅當(dāng)對某一頂點(diǎn)的順序,他們的鄰接矩陣是一樣的. 例3 判定以下兩圖同構(gòu).

13、 分析 為證明圖同構(gòu)，必須使結(jié)點(diǎn)，邊一一對應(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對應(yīng)（都2度），又因?yàn)閳D的對稱性，a與e 、b與d是對稱的，b與3度的a相鄰，3與3度的1、4相鄰，可以任意選，如選a與1相鄰，則可確定點(diǎn)的對應(yīng). 證明 取 ： , , , , . A (1) = , A (2) = 即A (1)= A (2)，由定理2.2.1知，以上兩圖同構(gòu). 例4 判定如下兩圖同構(gòu).

14、 證明 取 ： , , , , , , . A(1)= , A(2) = 即A (1)= A (2)，由定理2.2.1知，以上兩圖同構(gòu). 定義 對矩陣A= 施行第1種初等行(或列)變換,是指交換矩陣A的2行(或2列).交換A的第行和第行記為,交換A的第列和第j列記為. 定義 設(shè)A= 是一個(gè)n階方陣,對任意選定的正整數(shù),如果對矩陣A同時(shí)進(jìn)行第一種初等變換與第一種初等列變換得到B,則稱對A施行了一次對稱變換得到矩陣B

15、.記為. 定理 n階標(biāo)定圖與同構(gòu)的充要條件是存在的同構(gòu)變換,使得化成. 一般而言,待判定圖頂點(diǎn)對應(yīng)關(guān)系是未知的,而同構(gòu)判定正是要找出這樣的對應(yīng)關(guān)系.通過定理2.2.2很容易判定圖同構(gòu),即,先寫出與的與,然后調(diào)整的行序和列序(行的交換與列的交換),如能使,則,如所有可能的行交換與列交換都不能使,則判定與兩圖不同構(gòu). 例3(續(xù)) 分析 在例3中,首先找到點(diǎn)的對應(yīng),在利用定理2.2.1判定圖同構(gòu).而給出定理2.2.2之后,發(fā)現(xiàn)判定圖同構(gòu)時(shí)用定理2.2.2方便了很多,即,不必先找到點(diǎn)的對應(yīng), 直接把鄰接矩陣寫出就可以了. 證明 = , = = = 由定理2.2.2知，兩圖同

16、構(gòu). 在以上例題中,也可找到點(diǎn)的對應(yīng). 2.3 用關(guān)聯(lián)度序列判定同構(gòu) 定義 如果無向圖G中n(1≤n

17、=1,2,…,N-1.這里N是圖或的點(diǎn)數(shù). 例1(續(xù)) 證明 , , , . 即 . , , , . 即 . , , , , . 即 . , , , , . 即 . , , , . 即 . , , , . 即 . 由于 , ,所以兩圖同構(gòu). 用此定理2.3.1的逆否命題判定不同構(gòu)時(shí)比較方便，只要找到一個(gè)，即可. 例4 判定如下兩圖同構(gòu).

18、 證明 即. 即. 即 . , 即. 即 . 即 . 雖然 , ，但是即兩圖不同構(gòu). 2.4 用出入度序列法判定同構(gòu) 定義　在有向圖G中,與一個(gè)n點(diǎn)連通子圖G()相連接的邊(不包括G()的內(nèi)部邊)稱為關(guān)聯(lián)邊.關(guān)聯(lián)邊中方向指向這個(gè)子圖的邊稱為入邊，方向離開這個(gè)子圖的邊稱為出邊，入邊的數(shù)目稱為G()的入度,記作，出邊的數(shù)目稱為G()的出度，記為. 定義 若有向圖G的n點(diǎn)連通子圖一共有P個(gè),則將這P個(gè)n點(diǎn)連通子圖的出度按從大到小的順序排列起來所得到的有序集合稱為n點(diǎn)連通子圖的出度序列,記

19、為；將這P個(gè)n點(diǎn)連通子圖的入度按從大到小的順序排列起來所得到的有序集合稱為n點(diǎn)連通子圖的入度序列,記為. 定理　 有向圖與同構(gòu)的充要條件是與的n點(diǎn)連通子圖的入度和出度序列分別為，,和,，那么對任一n都有，，,這里N是圖與的點(diǎn)數(shù). 例5 判定如下兩圖同構(gòu). 證明 即 . 即 . 即 . 即 . 即 . 即 . 即 . 即 . 即 . 即. 即. 即. 由于所以兩圖同構(gòu). 3. 用不變

20、量判定兩圖不同構(gòu) 對于兩圖和,我們可以找到一個(gè)的特性, 并不具備,則兩圖不同 構(gòu)，但如果和是同構(gòu)的應(yīng)該具有這個(gè)特性,這個(gè)特性稱為不變量,更精確地說,一個(gè)特性P是不變量當(dāng)和是同構(gòu)圖時(shí),如果具有特性P,那么也具有特性P. 命題3.1 同構(gòu)的圖具有的頂點(diǎn)數(shù)是不變量. 命題3.2 同構(gòu)的圖具有的邊數(shù)是不變量. 命題3.3 同構(gòu)的圖具有的頂點(diǎn)度是不變量. 命題3.4 同構(gòu)的圖度數(shù)相同的結(jié)點(diǎn)數(shù)是不變量. 命題3.5 同構(gòu)的圖邊數(shù)相同的回路數(shù)目是不變量. 對于給定的圖如果這些不變量有任一不同，則不同構(gòu)，但是這些不變量相同，也不意味著兩圖一定同構(gòu).例如：

21、 （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ù)，如果找不到一定可以找到不同的不變量，再判定圖同構(gòu)時(shí)可以先試著判定圖不同構(gòu)，這樣會方便許多.如不能找到不同的不變量

22、，則利用以上討論的幾種方法判定同構(gòu)，在n很小時(shí)我們可以直觀的找到雙射函數(shù)，隨著n的增大，找點(diǎn)與點(diǎn)，邊與邊之間的對應(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)本初,洪清華,謝繼國,線性代數(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.