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

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