2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩38頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、本文論述了圖的頂點標(biāo)號?!  〗o定一個無向圖G,G的一個L(2,1)-labeling是指從其頂點集V(G)到非負(fù)整數(shù)集的一個映射f,滿足:|f(x)-f(y)|≥{21當(dāng)dG(x,y)=l當(dāng)dG(x,y)=2這里dG(u,v)表示u和v之間的距離,即u和v之間最短路的長度。象集合中的元素稱為標(biāo)號。若一個L(2,1)-labeling中的所有標(biāo)號都不超過整數(shù)k,則稱之為k-L(2,1)-labeling。圖G的L(2,1)-label

2、ing數(shù),記作λ(G),是使得圖G存在k-L(2,1)-labeling的最小整數(shù)k。特別地,若G的某個L(2,1)-labeling中的標(biāo)號是連續(xù)出現(xiàn)的,則稱之為G的一個No-holeL(2,1)-labeling。圖G的No-holeL(2,1)-labeling數(shù),記作-λ(G),是使得圖G存在No-holek-L(2,1)-labeling的最小整數(shù)k。由定義易知,如果一個n階圖G存在No-holeL(2,1)-labeling

3、,則λ(G)≤λ(G)≤n-1。  根據(jù)n階圖G的邊數(shù),連通分支數(shù)和直徑給出了Gc存在哈密頓路和哈密頓圈的充分條件,從而相應(yīng)地得到了G存在No-holeL(2,1)-labeling的充分條件。然后根據(jù)這三個參數(shù)刻畫了λ(G)=n-1的圖。主要結(jié)果有:(1)設(shè)G是階數(shù)n邊數(shù)m的簡單圖,如果m≤n-2或其連通分支數(shù)p(G)≥「(n+1)/2」或G是直徑d≥[n/2]+l的連通圖,則Gc有哈密頓路,從而G有No-holeL(2,1)-

4、labeling。(2)設(shè)G是n個頂點m條邊的圖,如果λ(G)=n-1,則n-2≤m≤(n-1)(n-2)/2。此外對任意滿足n≥3且n-2≤m≤(n-1)(n-2)/2的整數(shù)n和m,存在階數(shù)n邊數(shù)m的簡單圖G使得λ(G)=n-l,并且邊數(shù)為n-2和(n-1)(n-2)/2的圖是確定的。(3)設(shè)G是n階簡單圖,如果λ(G)=n-l,則p(G)≤[n/2]。此外對任意滿足n≥4且1≤p≤[n/2]的整數(shù)n和p,存在階數(shù)n連通分支數(shù)p的簡單

5、圖G使得λ(G)=n-1,并且分支數(shù)為「n/2]的圖是確定的。(4)設(shè)G是階數(shù)n≥6直徑d的連通圖,如果λ(G)=n-1,則2≤d≤[n/2]+l。此外對任意滿足n≥6且2≤d≤[n/2」+l的整數(shù)n和d,存在階數(shù)n直徑d的簡單圖G使得-λ(G)=n-1。(5)對任意滿足2≤k≤n-l的整數(shù)n和k,存在一個n階簡單圖G使得-λ(G)=k。 給定一個無向圖G及整數(shù)j≥k,G的一個L(j,k)-labeling是指從其頂點集V(G)

6、到非負(fù)整數(shù)集的一個映射f,滿足:|f(x)-f(y)|≥{jk當(dāng)dG(x,y)=2當(dāng)dG(x,y)=1若一個L(j,k)-labeling中的所有標(biāo)號都不超過整數(shù)t,則稱之為t-L(j,k)-labeling。圖G的L(j,k)-labeling數(shù),記作λj,k(G),是使得圖G存在t-L(j,k)-labeling的最小整數(shù)t。有向圖D的L(j,k)-labeling數(shù)記作-λj,k(D),其定義類似于無向圖G,只需將其中dG(u,v

7、)變?yōu)镈中從u到v的有向距離。 G.J.Chang等人[21-22]根據(jù)有向圖D中最長有向路的長度l(D)研究有向圖的L(j,k)-labeling問題,得到了一些非常好的結(jié)果。 證明了:(1)對任意一個有向圖D有-λj,k(D)≤(-x(D)-1)j,這里-x(D)表示D的有向著色數(shù),并且界是可達(dá)到的;(2)對任意一個有向圖D,如果它不含有向圈或者其最長有向圈長度為l(D)+1,則-λj,k(D)≤lj,并且界是可達(dá)到

8、的。最后我們對l(D)=3且所含最長有向圈長不等于3的有向圖D給出了設(shè)置其3j-L(j,k)-labeling的一個有效算法。 研究了圖的L(3,2,1)-labeling問題。主要結(jié)果有:(1)設(shè)Pn為n個頂點的路,則當(dāng)n=1時,λ3(Pn)=0;n=2時,λ3(Pn)=3;n=3,4時,λ3(Pn)=5;n=5,6,7時,λ3(Pn)=6;n≥8時,λ3(Pn)=7。(2)設(shè)Cn為n個頂點的圈,則當(dāng)n=3,4,5時,λ3(C

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論