圖同構的判定數(shù)學畢業(yè)論文

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

1、平頂山學院本科畢業(yè)論文（設計） 畢業(yè)論文(設計) 題 目: 圖同構的判定 院(系): 數(shù)學與信息科學學院 專業(yè)年級: 數(shù)學與應用數(shù)學 姓 名: 學 號: 指導教師: 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 中文摘要 本文對于兩圖的同構的判定方法進行探討，通過同構定義、鄰接矩陣、關聯(liá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、 目 錄 中文標題 中文摘要 關鍵詞 英文標題 英文摘要 關鍵詞 正文 1 1圖的同構定義 1 2圖同構判定及簡單應用 2 2.1用同構定義判定圖同構 2 2.2用鄰接矩陣判定圖同構 4 2.3用關聯(lián)度序列法判定同構 8 2.4用出入度序列法判定同構 10 3用不變量判定兩圖不同構 12 參考文獻 14 致謝 “圖論”是數(shù)學的一個分支,

6、它以圖為研究對象.圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關系.圖論是一門極有興趣的學問，其廣闊的應用領域涵蓋了人類學、計算機科學、化學、環(huán)境保護、電信領域等等.嚴格地講，圖論是組合數(shù)學的一個分支，例如，它交叉運用了拓撲學、群論和數(shù)論.圖論就是研究一些事物及它們之間關系的學科，現(xiàn)實世界中的許多事物能用圖來表示其拓撲結構，把實際問題的研究轉(zhuǎn)化為圖的研究，利用圖論的相關結論對這些問題作分析或判斷. 在抽象代數(shù)中，同構指的是一個保持結構的雙射.在更一般的范疇論語言中，同構指的是一個態(tài)

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

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

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

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

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

12、圖釘”連同“橡皮筋”取下,釘在平面上的其他位置,得到與另一個圖相同的結構和形狀,則這兩個圖一定同構.如上例1,把的結點1移至邊（2 , 3）的左下方,再把整個圖順時針旋轉(zhuǎn)90,即得到圖. 2.2 用鄰接矩陣判定圖同構 定義 設圖G=,V={}，令為頂點鄰接到頂點邊的條數(shù)，稱為G的鄰接矩陣，記作,或簡記為A. 通過例2圖表的提示以及定義2.2.1知道可以把點與點，邊與邊之間的一一對應用鄰接矩陣表示出來. 定理 如果圖和圖是同構的當且僅當對某一頂點的順序,他們的鄰接矩陣是一樣的. 例3 判定以下兩圖同構.

13、 分析 為證明圖同構，必須使結點，邊一一對應，保持結點鄰接性，此題兩圖都有5個頂點8條邊，1個結點2度，2個結點3度，2個結點4度，很顯然，c與2對應（都2度），又因為圖的對稱性，a與e 、b與d是對稱的，b與3度的a相鄰，3與3度的1、4相鄰，可以任意選，如選a與1相鄰，則可確定點的對應. 證明 取 ： , , , , . A (1) = , A (2) = 即A (1)= A (2)，由定理2.2.1知，以上兩圖同構. 例4 判定如下兩圖同構.

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

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

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

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

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

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

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

21、 （1） （2） （3） （4） 如上圖，很顯然，（1）（2）兩圖很容易發(fā)現(xiàn)頂點數(shù)不同，所以不同構，但是（3）（4）兩圖，不變量都相同，但是不管用哪種判定同構的方法都不能判定兩個圖同構.事實上，不變量是同構具有的性質(zhì)，即不變量不同，一定不同構，但同構時一定有不變量成立，可以綜述為以上命題為充分不必要條件.判定圖同構主要找點與邊的雙射函數(shù)，如果找不到一定可以找到不同的不變量，再判定圖同構時可以先試著判定圖不同構，這樣會方便許多.如不能找到不同的不變量

22、，則利用以上討論的幾種方法判定同構，在n很小時我們可以直觀的找到雙射函數(shù)，隨著n的增大，找點與點，邊與邊之間的對應困難增大，我們可以用鄰接矩陣，關聯(lián)度序列，出入度序列等方法判定.但是隨著n的增大,判定圖同構的時間復雜度就越大,所以我們?nèi)砸^續(xù)努力學習,探討出比較方便快捷的方法. 參考文獻 ［1］屈婉玲，耿素云，張立昂，離散數(shù)學［M］高等教育出版社，2008，277-278. ［2］陳曉紅，王敏麗，關于圖的同構方法的探討［J］大學數(shù)學，2006.4.22（2）. ［3］費本初,洪清華,謝繼國,線性代數(shù)基本概念圖示［M］蘭州大學出版社.1989. ［4］張效賢.圖構圖的等價條件［J］甘肅科學學報.2003.13(1). ［5］李　鋒,圖的同構判定算法:關聯(lián)度序列法及其應用[J],復旦學報:自然科學版, 2001, 40(3). ［6］李　鋒,商慧亮,有向圖的同構判定算法:出入度序列法[J],應用科學學報, 2002, 20(3), 258-262.