版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、近年來(lái),圖的支配理論已經(jīng)成為圖論最重要研究領(lǐng)域之一.一些學(xué)者發(fā)現(xiàn)無(wú)線網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一虛擬骨干網(wǎng)技術(shù),和圖的連通支配集有密切的關(guān)系.從那以后,支配集在研究無(wú)線網(wǎng)絡(luò)技術(shù)中占有重要的地位.
圖的[ j,k]-集的概念由Chellai等人在2013年提出.研究 j不小于1的[ j,k]-集的目的,來(lái)源于研究中需要一類(lèi)特殊的支配集,例如,作為計(jì)算機(jī)網(wǎng)絡(luò)中的服務(wù)器集合,或作為需要監(jiān)控場(chǎng)合的監(jiān)控設(shè)備集合,不僅要求它們能夠有效地工作,而且要
2、求它們能花費(fèi)盡可能小的代價(jià)有效地工作,換句話說(shuō),不要有太多的冗余設(shè)備.
在本文中,我們主要研究圖的[1,2]-集和連通[1,2]-集的性質(zhì)和算法.圖G的一個(gè)支配集S被稱為[1,2]-集,如果對(duì)圖G的任意頂點(diǎn)v,滿足v∈ V(G)\S,1≤|N(v)∩S|≤2.我們稱圖的G的元素最少的[1,2]-集的元素個(gè)數(shù)為[1,2]-支配數(shù),簡(jiǎn)稱[1,2]-數(shù).如果圖的[1,2]-集的導(dǎo)出子圖是連通的,那么稱這個(gè)[1,2]-集是圖G的連通[
3、1,2]-集.
首先,我們考慮滿足γ(G)=γ[1,2](G)的圖并給出這樣的一些圖類(lèi)蜘蛛圖和廣義Petersen圖P(n,1).
其次,我們研究了[1,2]-集和連通[1,2]-集之間的關(guān)系.我們研究了滿足連通支配集和連通[1,2]-集相等γc(G)=γc[1,2](G)或連通[1,2]-集等于頂點(diǎn)數(shù)n,即γc[1,2](G)=n的一些圖的結(jié)構(gòu)性質(zhì),并證明了二分圖的最小連通[1,2]-集問(wèn)題是一個(gè)NPC問(wèn)題.
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- [1,2]-Wittig重排反應(yīng)的研究及應(yīng)用.pdf
- 26940.局部半完全有向圖的(1,2)步競(jìng)爭(zhēng)圖與h強(qiáng)迫集的研究
- (1,2)-范例斷點(diǎn)距離的動(dòng)態(tài)規(guī)劃算法研究.pdf
- 不動(dòng)點(diǎn)集為RP(2m)xHP(2n+1)(m=1,2)的對(duì)合.pdf
- 完形填空1,2
- 探究《Реконструкция причалов №№1,2 морского порта Певек》的翻譯策略.pdf
- 高熵合金AlxCoCrFeNi(X=1,2)力學(xué)性質(zhì)的第一性原理研究.pdf
- 12破粉碎車(chē)間1,2剖面圖.dwg
- 不動(dòng)點(diǎn)集是Dold流形P(2m+1,2n+1)的對(duì)合.pdf
- 12破粉碎車(chē)間1,2剖面圖.dwg
- 15789.擴(kuò)充競(jìng)賽圖和圓有向圖的(1,2)步競(jìng)爭(zhēng)圖的研究
- 西方文明史1,2
- 仿真1,2最終稿.rar
- 1,2-dihydrophosphete衍生物的合成與光學(xué)性質(zhì)測(cè)定.pdf
- 仿真1,2最終稿.rar
- 零件1,2的程序.wps
- 反式1,2環(huán)己二醇的制備(1)
- 固定點(diǎn)集為Dold流形P(1,2n)的對(duì)合.pdf
- 取代芐基吡嗪鎓陽(yáng)離子對(duì)[Ni(mnt)2]n-(n=1,2)陰離子堆積方式的影響及性質(zhì)研究.pdf
- 零件1,2的程序.wps
評(píng)論
0/150
提交評(píng)論