發(fā)布時(shí)間：2021-01-07 20:09

　　集合覆蓋問題是組合優(yōu)化領(lǐng)域中的經(jīng)典問題,它指的是在給定的集族中選一個(gè)階數(shù)最小子集族來覆蓋所有給定的元素.該問題不僅具有很高的理論價(jià)值,隨著無線網(wǎng)絡(luò)的發(fā)展更具有了越來越廣泛的應(yīng)用背景.本文主要研究的是集合覆蓋的兩種變形:最小賦權(quán)部分連通集合覆蓋問題（MVW PCSC）和在線3-路點(diǎn)覆蓋問題（online VCP3）.對(duì)于MWPCSC問題,給定元素集合U,集合族S,權(quán)函數(shù)c:S → Q+,以集合族中集合作為點(diǎn)集的連通圖GS,正整數(shù)k≤|U|,其目標(biāo)是找到一個(gè)最小權(quán)的子集族S’（?）S使得由S’導(dǎo)出的子圖連通,且|US∈S’S|≥k.當(dāng)GS滿足任意兩個(gè)有公共元素的集合在Gs中的跳數(shù)（hop distance）不超過r時(shí),這個(gè)問題被稱為r-hopPCSC.對(duì)最小權(quán)的1-hopPCSC,我們給出了一個(gè)O(ln（m+ n）-近似算法;對(duì)最小基數(shù)下r-hopPCSC,我們給出了一個(gè)O（ln（m + n））-近似算法.和前人的結(jié)果比較,我們的方法要簡(jiǎn)單的多.對(duì)于特殊集合覆蓋問題——3-路點(diǎn)覆蓋,給定圖G（V,E）,當(dāng)圖G中的每一條3個(gè)點(diǎn)的路至少有一個(gè)點(diǎn)在C中時(shí),我們稱C是一個(gè)3-路點(diǎn)覆蓋.本文考慮的是... 

【文章來源】：浙江師范大學(xué)浙江省

【文章頁數(shù)】：44 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖４．２：斷言２的圖示．用黑色的邊代替將會(huì)導(dǎo)出一個(gè)更大的３－路匹配．??

圖４．３：斷言３．?１．的證明圖示??

廁匪??⑷?（ｂ）??圖４．３：斷言３．?１．的證明圖示??斷言３．２．?Ｉｆ?Ｐ?ｅ?Ｍｉ，那么Ｘ?△?－?２，?Ｐ的硬幣能分擔(dān)到Ｐ＇上．??設(shè)尸＇＝．在ｃＰ，?＝?｜ｉ＼＾ｌｕＫ，（＼／（Ｐ）＼Ｃ）｜?＝?△?－?１的假設(shè)下，我們推出矛盾．??首先，考慮?＜?是ｎＣ？中的唯一點(diǎn)．如果ｕ?由于％己經(jīng)有三個(gè)鄰??點(diǎn)在Ｖ（Ｍ）中（如圖４．４⑷），那么丨￣婦，㈨）｜?＜?Ａ－３？結(jié)合｜ｉＶＫｌＵｉｒ，（｛ｚ４，４｝）｜?＝??｜」Ｖ／ｓ：ｌＵ／ｌ￡＂＇（＇ｌ’（／：＞）＼（７）｜?＝?Ａ?－?１，可知?（圮）｜?２?２．令為中兩點(diǎn)？那??么（＾／＾｛叩仰，１��；丨＋⑴是一個(gè)比ｉＵ更大的３－路匹酉己如果??■ｕ?＝?％


本文編號(hào)：2963165