謝爾賓斯基相關(guān)圖類的結(jié)構(gòu)性質(zhì).pdf

1、圖論的產(chǎn)生最早可追溯到十八世紀(jì)三十年代，其標(biāo)志性事件是瑞士數(shù)學(xué)家萊昂哈德·歐拉（Leonhard Euler，1707年4月15日～1783年9月18日）解決了哥尼斯堡七橋問題，這篇文章的發(fā)表被公認(rèn)為是圖論產(chǎn)生的里程碑。自二十世紀(jì)五十年代以來，計(jì)算機(jī)科學(xué)的迅猛發(fā)展大大地推動了圖論的發(fā)展。現(xiàn)在，圖論已經(jīng)成為離散數(shù)學(xué)的一個骨干分支，它不僅具有重要的理論價值，而且具有重要的應(yīng)用價值。其在化學(xué)、信息學(xué)、網(wǎng)絡(luò)設(shè)計(jì)、管理科學(xué)、通信工程、計(jì)算機(jī)科學(xué)以

2、及生物信息學(xué)等領(lǐng)域都得到了廣泛應(yīng)用。
　　圖的哈密爾頓性、染色理論以及最短路問題作為圖論中的經(jīng)典問題，得到了大量圖論專家的關(guān)注。本文主要研究謝爾賓斯基相關(guān)圖類的哈密爾頓性、染色理論以及最短路問題，其中染色理論包括路染色、線性染色以及2-距離染色。
　　謝爾賓斯基相關(guān)圖類與拓?fù)浞中卫碚?、漢諾塔數(shù)學(xué)理論及計(jì)算機(jī)科學(xué)等都有密切的聯(lián)系。下面，首先介紹謝爾賓斯基相關(guān)圖類S（n，k）、S+（n，k）、S++（n，k）和S[n，k]的定義

3、。
　　謝爾賓斯基圖S(n，k)（n，k≥1）的頂點(diǎn)集是由整數(shù)1，2,…，k的所有的n元組構(gòu)成的，即V（S（n，k））={1,…，k}n。兩個不同的頂點(diǎn)u=（u1，u2,…，un）和v=(v1，v2,…，vn)相鄰當(dāng)且僅當(dāng)存在一個h∈[1，n]使得下面三個條件成立:
　　(a)ut=vt，其中t∈{1，…，h-1};
　　(b)uh≠vh;
　　(c)ut=vh和vt=uh，其中t∈{h+1，…，n}。
　

4、　在S（n，k）中，頂點(diǎn)(i,…，i)，i∈{1,…，k}，稱為謝爾賓斯基圖S（n，k）的極點(diǎn);形如（i,j,…，j）或者（i，…，i，j）的頂點(diǎn)稱為S(n，k)的幾乎極點(diǎn)。把不屬于任何一個完全圖的邊稱為橋邊。
　　圖S+（n，k）（n，k≥1）是在謝爾賓斯基圖S(n，k)的基礎(chǔ)上，添加一個新的頂點(diǎn)ω和所有連接ω與S(n，k)的k個極點(diǎn)的邊得到的圖。
　　對于圖S++(n，k)，令S++(1，k)≌Kk+1;圖S++（n，k

5、）（n≥2，k≥1）的頂點(diǎn)集合V（S++（n，k））=V(S(n，k))∪V(S(n-1，k)），邊的集合E（S++（n，k））=E(S(n，k))∪E(S(n-1，k))UM，其中，M是一個含有k條邊的匹配，并且M中每條邊的兩個端點(diǎn)分別是S(n，k)的一個極點(diǎn)和S(n-1，k)的一個極點(diǎn)。
　　圖S[n，k]是通過收縮謝爾賓斯基圖S(n，k)中所有橋邊得到的圖。
　　給定一個圖G，如果G中的一條路遍歷了它所有頂點(diǎn)，則稱這條

6、路為圖G的一條哈密爾頓路。類似的，若圖G中的一個圈遍歷了它的所有頂點(diǎn)，則稱這個圈為圖G的一個哈密爾頓圈。若G中存在一個哈密爾頓圈，則稱G為哈密爾頓圖。
　　圖G的一個t-染色就是一個映射φ:V(G)→{1,…，t}。給定圖G的一個t-染色φ，我們用φ-1(i)記圖G中染色為i的頂點(diǎn)的集合，并把圖G中φ-1(i)的導(dǎo)出子圖記為G[φ-1(i)]。
　　如果每一個G[φ-1(i)]，i∈{1,…，t}，是圖G的一個獨(dú)立集，那么稱

7、φ為圖G的一個正常t-染色。圖G的色數(shù)x(G)就是使圖G存在一個正常t-染色的最小的t。
　　如果每一個G[φ-1(i)]，i∈{1,…，t}，是圖G的一個線性森林，那么稱φ為圖G的一個路t-染色，其中，線性森林指的是每個連通分支都為路的圖。圖G的點(diǎn)線性蔭度vla(G)就是使圖G存在一個路t-染色的最小t。換句話說，圖G的點(diǎn)線性蔭度vla(G)，就是劃分它的頂點(diǎn)集所需要的頂點(diǎn)子集的最小個數(shù)，同時滿足每個頂點(diǎn)子集在G中的導(dǎo)出子圖為一

8、個線性森林。
　　如果每一個G[φ-1(i)∪φ-1（j）]，i，j∈{1,…，t}，是圖G的一個線性森林，那么稱φ為圖G的一個線性t-染色。圖G的線性色數(shù)lc(G)就是使圖G存在一個線性t-染色的最小的t。
　　圖G的2-距離染色就是對圖G的頂點(diǎn)進(jìn)行染色使距離至多是2的頂點(diǎn)染不同的顏色。
　　給定一個圖G，對于任意兩個頂點(diǎn)u，v∈V(G)，u與v之間的最短路就是連通它們的長度最小的路。
　　本文討論了謝爾賓斯基

9、相關(guān)圖類S（n，k）、S+（n，k）、S++（n,k）和S[n，k]的哈密爾頓性、染色問題和最短路問題。具體說來，主要研究了謝爾賓斯基相關(guān)圖類的哈密爾頓性、路染色、線性染色與謝爾賓斯基圖S（n，k）的2-距離染色和最短路問題。本文內(nèi)容共分為四章。
　　第一章，首先，介紹了一些圖論中基本的概念、術(shù)語和符號;然后，給出了謝爾賓斯基相關(guān)圖類的定義及研究現(xiàn)狀;最后，列出了本文所得到的主要結(jié)果。
　　第二章，分別確定出了S(n，k)、

10、S+(n，k)和S++（n，k）中邊不交的哈密爾頓路和哈密爾頓圈的個數(shù)。
　　第三章，研究了謝爾賓斯基相關(guān)圖類的路t-染色、線性染色和2-距離染色。
　　第四章，主要討論了謝爾賓斯基圖S(n，k）中的最短路問題。完全確定出了Su={v∈V(S(n，k)）:在S（n，k）中存在兩條最短的u，v-路}，其中，u是S（n,k）的任意一個幾乎極點(diǎn)。
　　此外，對于S（n，3），我們找到了(n-3)·3n+3·2n對頂點(diǎn)使得每一