用矩陣判斷哈密頓圖的一個(gè)充要條件

1、廣西民族學(xué)院學(xué)報(bào) (自然科學(xué)版 第 7卷第 1期 JOURNAL OF GUANGXI UNIVERSITY FOR NATIONALITIES V ol. 7No. 1 2001年 2月 (Natural Science Edition Feb. 2001文章編號(hào) :1007-0311(2001 01-0009-02用矩陣判斷哈密頓圖的一個(gè)充要條件 *姚源果(廣西右江民族師范高等?？茖W(xué)校 數(shù)學(xué)系 , 廣西 百色 533000摘 要 :給出了一個(gè)從圖的鄰接矩陣來判斷有限無向連通圖是否是哈密頓圖的充分必要條件 .關(guān)鍵詞 :圖論 ; 哈密頓圖 ; 鄰接矩陣 ; 充要條件中圖分類號(hào) :O151121

2、文獻(xiàn)標(biāo)識(shí)碼 :A尋找一個(gè)像判斷歐拉圖那樣簡(jiǎn)單的充要條件來判斷哈密頓圖是非常困難的 , 判斷哈密頓圖的充要條件仍然是圖論中尚未解決的問題 . 既然圖論與計(jì)算機(jī)聯(lián)系的紐帶是矩陣 , 那么可以設(shè)想通過矩陣來尋求一個(gè)判斷哈密頓圖的充要條件 .1定義定義 1設(shè) G =3V, E 4是有限無向圖 , 點(diǎn)集 V的元數(shù)為 n , 如果 n 階正方矩陣 A (G =b ij 滿足下面條件 :b ij = 0, 當(dāng) v i 與 v j 不相鄰 1, 當(dāng) v i 與 v j 相鄰則 A (G 稱為圖 G 的鄰接矩陣 .例 1圖 1所示圖 G 的鄰接矩陣為 A (G = 01111 10100 11011 10101

3、 1011圖 1無向連通圖 A定義 2設(shè) A =a i j 是 一 個(gè) n 階方 陣 , 若 W (A =E j1j2, jna 1j1a 2j2, a njn(其中 j 1j 2, j n 是 1, 2, 3, , , n 的所有全排列且和式中任意一項(xiàng)不能同時(shí)出 現(xiàn) b ij 和 b j i , 則稱 W (A 為矩陣 A 的奇異和 . 2定理及證明定理 1設(shè) G =3V , E 4是一個(gè)沒有自回路的有 限無向連通圖 , V 的元數(shù)為 n, A (G =b ij (i, j = 1, 2, 3, , , n 是 G 的鄰接矩陣 , 則 G 是哈密頓圖的 充分必要條件是 A (G 的奇異和 W

4、 (A 不等于 0. 證明 :必要性 ( 若圖 G 是哈密頓圖 , 則 G 存在 一條 哈密 頓回 路 , 不妨 設(shè)這 條哈 密 頓回 路 為*收稿日期 :2000-08-15.作者簡(jiǎn)介 :姚源果 (1974- , 男 , 廣西田林人 , 廣西右江民族師范高等?？茖W(xué)校數(shù)學(xué)系助教 .(v 1, v 2, v 3, , v n , v 1 , 即 v 1與 v 2, v 2與 v 3, v 3與 v 4, , v n-1與 v n , v n 與 v 1都有邊相連 . A (G =b ij 是 G 的鄰接矩陣 , 所以 b 12=b 23=b 34=, =b n-1n=b n 1=1, 即 b 1

5、2b 23b 34, b n-1n b n 1=1.由鄰接矩 陣的定義知 , 任意 b ij =1或 0. 所以 W (A (G X 0.充分性 (a A (G =b ij 是 G 的鄰接矩陣 , 若 W (A (G X 0, 而這個(gè)和式和每一項(xiàng)都是 1或 0, 所以必存在某一項(xiàng)為 1, 假設(shè) b 1j 1b 2j 2, b nj n =1則有b 1j 1=b 2j 2=, =b nj n =1所以在圖 G 中 , 存在 n 條邊 :(v 1-v j 1 , (v 2-v j 2 , , , (v n -v j n 因圖 G 沒有自回路 , 則 1X j 1, 2X j 2, , , n X

6、j n . 而 j 1, j 2, , , j n 互不相等 , 是 1, 2, , , n 的全排列 , 且 b ij 各 b j i 不同時(shí)出現(xiàn) , 即上述 n 條邊不重復(fù) . 顯然上述 n 條邊能構(gòu)成一條哈密頓回路 , 即圖 G 是哈密頓圖 .3 例題例 2 判斷下面圖 2和圖 3是否是哈密頓圖 . 圖 2無向連通圖 B 圖 3無向連通圖 C圖 2 無向連通圖 B 圖 3 無向連通圖 C解 :(1 圖 1的鄰接矩陣A(G 1 =01100110100011101100001011000110011001001010011所以 W(A(G 1 =X 0即圖 G 1是哈密頓圖(2 圖 2的鄰

7、接矩陣A(G 2 =000101000110000001001100011011000110010000001100001010 所以 W(A(G 2 =0即圖 G 2不是哈密頓圖 .4 結(jié)論定理 1雖然只是給出沒有自回路的有限無向連 通圖是否是哈密頓圖的判斷條件 , 但對(duì)于存在自回路 的圖只要將自回路刪除即可 , 因?yàn)樽曰芈凡荒茏鳛楣?密頓回路的一部分 , 對(duì)判斷哈密頓圖沒有任何影響 . 再者 , 如果是有向圖 , 也可完全使用定理 1, 只要注意 一下鄰接矩陣的定義就可以了 .使用矩陣來判斷一個(gè)圖是否是哈密頓圖肯定不 夠直觀 , 甚至更復(fù)雜 , 但對(duì)于計(jì)算機(jī)來說卻是方便處 理 , 事實(shí)上

8、, 依照定理 1很容易編寫一段計(jì)算機(jī)程序 來判斷任意圖是否是哈密頓圖 .參 考 文 獻(xiàn) 1馬振華 . 離散數(shù)學(xué)導(dǎo)引 M . 北京 :清華大學(xué)出版社 , 1993. 2前田渡 , 伊東正安 . 陶 思雨 , 王 緝惠 譯 . 現(xiàn)代圖 論基礎(chǔ) M . 北京 :高等教育出版社 , 1987.責(zé)任編輯 黃祖賓 責(zé)任校對(duì) 曹滿仙 Judging an Essential and Prerequisite Condition of Hamiton Diagram by MatrixYA O Yuan -guo(Dept. o f M athematics of Youj iang Teachers College f or N ationalities of Guangx i , Beise 533000, ChinaAbstract:Proving w hether finite connective diag ram w ithout direction is the essential and prerequisite con -dition of H amiton diagram by contig