關(guān)于輪圖的猜測數(shù)畢業(yè)論文-文庫吧資料
2025-06-24 20:01本頁面
【正文】 。cp()/whel?下面考慮 的最大獨立數(shù)。\{}whelCn?因此， 的團覆蓋數(shù)滿足()whel()cp()13)/2/whelGn????而 為 的 團覆蓋。1. 當 為偶數(shù)時首先， 中沒有頂點數(shù)大于 3 的完全子圖(團)。定義 設(shè) 為如下定義頂點集和邊集的無向圖，(,)DVE?， ( ) ()??0,???10, 1mod )|0, )niini???????????2?此時，稱 為無向輪圖，記為 。 □g=lG推論 有向輪圖的猜測數(shù)為()1:g()2whel kGn????????當當證明：由定理 和引理顯然成立。1k?m(,)nmE?(1od,)E??則 變成有向無圈圖，因此， 。V()whel?? g(),1whelGns???因此， 。0k?刪除頂點 0,則 變成有向無圈圖。(4)whelG???lk圖 2 有向輪圖 (4)whelG??的鄰接矩陣為(4)2whelGk???()(4)01001whelGA???????????記 ，則 且 。gl k?證明： (必要性)反證法：假設(shè) ，只需證明 。(,)VE?)whelG??記 ，它表示頂點 的入出{ | (1od ,), 1}kininEin?????n變化數(shù)。()?三．輪圖的猜測數(shù)（一）有向輪圖的猜測數(shù)在這一節(jié)中，我們考慮有向圈上添加一個頂點并與它連接所有頂點，這類圖定義為輪圖。()nK?N定義 若有一團集 覆蓋了圖 的所有邊，即圖 中每一條至少屬??| GG于一個 ，這時我們稱團集中的團的個數(shù)為團覆蓋數(shù)，記為 。定義 設(shè) 為無向圖，節(jié)點集 且 ，則稱(,)GVE?V??()()EV?????為圖 的導出子圖。0ija?0ija?2. 無向圖的猜測數(shù)我們可以把無向圖視為雙向邊有向圖、無向圖的猜測數(shù)定義為對應(yīng)雙向邊有向圖的猜測數(shù)。定理 [6] 設(shè) 為有向圖，對 有D??0,1S?(2)s()())lgD????其中 表示有向圖 中點不相交的圈數(shù)的最大值， 表示有向圖 中把()? ()D變?yōu)闊o圈的最小刪除邊數(shù)。 □G例 設(shè) 為頂點數(shù)為 的有向圈，則有向圈的猜測數(shù)為nC??n()g(,)(,)1lnssC?????證明：當 時， 可以視為 的剖分圖。令??.uwvFf??G?()??(,)(),.uvwufxfx??則 為有向圖 的一個策略，且??,.uvFf?G因此， 。令 ，其中 和 為??,.uvFf???,.uwvFf???f?v()(), (.)wuvfxfx?則 為 的猜測策略，并且顯然有 。()VG?推論 設(shè)有向圖 為由圖 刪除一頂點得到的圖，即 ，則有?G??\Gv??()g(,)(,)g(,)1ss???定理 設(shè)有向圖 為由圖 剖分一點得到的圖，則有?()(,)(,)s??證明：設(shè) 且邊 ，并設(shè) 為在圖 的邊 上添加一個,()uvVG?,uvEG?(,)uv頂點 得到的圖，即 。則 和 可Fl Fl視為 的猜測策略和線性猜測策略。NGg(,)Gs?（三）關(guān)于猜測數(shù)的一些結(jié)論1. 有向圖的猜測數(shù)先考慮子圖和剖分圖的猜測數(shù)。1ms 猜測成功的概率為 1ms???1Prms?中 間 節(jié) 點 都 猜 對 ?信息流問題 有解。則與它對應(yīng)的有向圖 的猜測策略為 ，NG??*1212,.,.mnFffg?()1122 1121211(,.,)..(,.,.,)guesreallrealnlguesreallreallrealrelmnmzfxxzzfxxzz???212121212,.,.,..(,.,.,)guesreallreallrealrelnguesreallreallrealreln nmxxzz顯然上述策略 與 一一對應(yīng)。G （a） (b) (c) (d)圖 1 網(wǎng)絡(luò)編碼到猜測數(shù)問題的轉(zhuǎn)化定理 [3] 信息流問題 的解與有向圖 上成功猜測的概率至少為??,NSNG的猜測策略一一對應(yīng)，其中 表示有向圖 的頂點數(shù)。我們先把網(wǎng)絡(luò) 的源節(jié)點和匯節(jié)點一一結(jié)合起來，然后由恒等映射可以得到有向圖N。定義 設(shè) 給定的網(wǎng)絡(luò)， 為編碼集( )，如果利用網(wǎng)絡(luò)編碼可以實現(xiàn)源NSSs?節(jié)點到所有匯節(jié)點的組播，則稱信息流問題 可解，并把這種策略稱為信息??,N流問題 的解。 □1(nisg(K,)s?例 設(shè) 為無圈有向圖，則Dg(,)0lDs（二）網(wǎng)絡(luò)編碼與猜測數(shù)這一節(jié)中我們將介紹網(wǎng)絡(luò)編碼與猜測數(shù)問題的對應(yīng)關(guān)系。()Fixs??g(K,)s?下面證明 。設(shè) 為所有人的真值向量，則所有人 猜對當且僅當??01,.ncc?? iv ?i,ci?fi(c)?F(c)??c?Fix()因此，猜測策略 下所有人猜對的概率為()g(,)ix()Pr(|)GsnnwiS例 完全圖 的猜測數(shù)為K1n?， ()g(,)(,)1lnss??2s??證明：首先證明 。ptix()稱 為有向圖 的線性猜測數(shù)，其中 表示所有(,)ali()linerl slinearFGs? linearF均為線性映射的策略。1njjds??定義 設(shè) 為有向圖 的一個猜測策略，F(xiàn)(,)GVE稱為猜測策略 的固定點集。并把向量函數(shù) 稱之為有向圖jdjv12(,.):nFfS的一個猜測策略，其中 ， ，G12(),).ncfc???01,.ncc??。此時，希望所有人猜對的(,)vw?vvw概率達到最大值。假設(shè)每一點的(,)GVE?值均屬于 ，其中 。在這一策略下，所有人猜對的概率等于所有人的值之和被 整除的概率，即s()Pr()1/wins?我們把這游戲推廣到一般有向圖中。那么，我們可以采用以下n?策略使得上述概率達到最大值。如果所有人都猜對了自己的值，則稱猜測成功，否則就算猜測失敗。其次，對于無向輪圖，以構(gòu)造一個
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1