發(fā)布時(shí)間：2020-04-22 00:30

【摘要】：圖的電力控制集問(wèn)題來(lái)源于電力網(wǎng)絡(luò)系統(tǒng)中如何選擇安排最少檢測(cè)儀器的節(jié)點(diǎn)位置問(wèn)題,電力控制集問(wèn)題是控制集問(wèn)題延伸出的一個(gè)重要研究分支。設(shè)G=(V,E)為一個(gè)簡(jiǎn)單圖,s(?)V為一個(gè)頂點(diǎn)子集,若滿足V\s中每個(gè)點(diǎn)都與S中至少一個(gè)點(diǎn)相鄰,稱S為圖G的控制集,圖G的控制數(shù)γ(G)是其控制集的最小基數(shù),控制集問(wèn)題就是確定圖上控制數(shù)。S(?)V是圖G的電力控制集,當(dāng)且僅當(dāng)V中每個(gè)點(diǎn)通過(guò)如下兩種方式可以獲得信息:(1)任意v∈ S,傳遞信息給其本身,同時(shí)也傳遞信息給其所有的鄰居點(diǎn);(2)一旦v獲取到信息,且只有一個(gè)未獲取信息的鄰居點(diǎn),則v傳遞信息給該鄰居點(diǎn)。圖G的電力控制數(shù)γ_p(G)為電力控制集的最小基數(shù)。電力控制集問(wèn)題就是確定圖上電力控制數(shù)。設(shè)k為非負(fù)整數(shù),圖G的k-電力控制集S的定義與電力控制集相似,僅將第二種獲得信息方式更改為:一旦v獲取到信息,并且v至多還有k個(gè)未獲取信息的鄰居點(diǎn),則v傳遞信息給這些鄰居點(diǎn)。圖G的k-電力控制數(shù)γ_(kp)(G)為k-電力控制集的最小基數(shù),k-電力控制集問(wèn)題就是確定圖上k-電力控制數(shù)。當(dāng)k=0時(shí),為控制集問(wèn)題;當(dāng)k=1時(shí),為電力控制集問(wèn)題。在實(shí)際電力網(wǎng)絡(luò)系統(tǒng)操作中,由于不同節(jié)點(diǎn)設(shè)置監(jiān)測(cè)儀器的成本存在差異,因此研究帶權(quán)值圖的電力控制集問(wèn)題具有更強(qiáng)的現(xiàn)實(shí)意義。給定點(diǎn)權(quán)值圖G=(V,E,w),w是定義在點(diǎn)上的權(quán)重,對(duì)于任意v ∈ V,w(v)≥0。圖G的帶權(quán)值k-電力控制數(shù)γkpw(G)=min {Σ_(v∈s) w(v)|S為G的一個(gè)kk-電力控制集}。本文對(duì)一些特殊圖類上尋找?guī)?quán)值k-電力控制數(shù)有效算法進(jìn)行了研究,主要工作包括以下幾個(gè)部分:本文第一章介紹了控制集、電力控制集、帶權(quán)值控制集類問(wèn)題研究背景及現(xiàn)狀。T.W.Haynes等人已經(jīng)證明電力控制集問(wèn)題在一般圖上的NP-困難性,人們也探討了一些特殊圖類上各類控制集問(wèn)題的多項(xiàng)式時(shí)間算法。在帶權(quán)值的特殊圖類上,各類控制集問(wèn)題的算法也被大家所關(guān)注。本文第二章研究點(diǎn)權(quán)值樹上k-電力控制集問(wèn)題,以定理2.1的結(jié)論為基礎(chǔ),從樹序列的頂點(diǎn)順序出發(fā),采用動(dòng)態(tài)規(guī)劃的技術(shù)給出了求解點(diǎn)權(quán)值樹上k-電力控制數(shù)的線性時(shí)間算法,并且證明了該算法的正確性。本文第三章研究了點(diǎn)權(quán)值仙人掌圖上k-電力控制集問(wèn)題,定理3.1給出了求解點(diǎn)權(quán)值圈上k-電力控制集問(wèn)題的理論方法。再以圈和樹上的思想方法為基礎(chǔ),給出求解點(diǎn)權(quán)值仙人掌圖上k-電力控制數(shù)的有效算法,算法復(fù)雜度為O(m + bn),其中m為邊數(shù),n為頂點(diǎn)數(shù),b為圖中的長(zhǎng)度大于等于3的圈數(shù),并證明了算法的正確性。
【圖文】：

圖(Cactus graph)。人掌圖 G，有如下等價(jià)命題：通圖 G 稱為仙人掌圖；通圖 G 上任意兩個(gè)長(zhǎng)度大于等于 3 的圈，最多只有一個(gè)公通圖 G 上每條邊都至多在一個(gè)圈上。意的仙人掌圖，其上的點(diǎn)都可以被分成下述三類[10]： 類頂點(diǎn)：只在一個(gè)圈上，且度為 2； 類頂點(diǎn)：不在任何一個(gè)圈上； 類頂點(diǎn)：至少在一個(gè)圈上，且度大于等于 3。2 左圖給出了仙人掌圖的一個(gè)示例，，及各頂點(diǎn)的類型。

圖 1.3：三類圖之間關(guān)系的概念之一，對(duì)于各類控制集問(wèn)題，樹一。Cockayne 等人[13]采用標(biāo)號(hào)的方法ng[16]則采用動(dòng)態(tài)規(guī)劃的方式給出樹上給出了樹上電力控制集問(wèn)題線性時(shí)間算制集問(wèn)題線性時(shí)間算法；其他一些關(guān)于,29,35,40,42,45,52 等]�？刂萍瘑�(wèn)題的研究也得到學(xué)者們較多關(guān),46,49,53 等]。
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 蘇亞娟;;超圖的連通邊控制集問(wèn)題一個(gè)貪婪算法[J];現(xiàn)代商貿(mào)工業(yè);2012年18期

2 馬文凱;李德英;張昭;;構(gòu)建最小k重控制集的概率算法[J];中國(guó)科學(xué):數(shù)學(xué);2011年08期

3 李建平;劉旭;朱娟萍;;賦權(quán)樹狀網(wǎng)絡(luò)中r-控制集問(wèn)題和k-中心問(wèn)題[J];運(yùn)籌學(xué)學(xué)報(bào);2009年02期

4 羅永萍;楊愛民;;有向路和有向圈的控制集數(shù)[J];高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào);2007年01期

5 皮軍德;林浩;;直線簇上區(qū)間圖的最小全控制集和最小配對(duì)控制集[J];河南科學(xué);2007年04期

6 王光源;方奇志;;k-控制集對(duì)策[J];中國(guó)海洋大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年S2期

7 阿勇嘎,斯欽;圖的臨界控制集與優(yōu)控制集[J];寶雞文理學(xué)院學(xué)報(bào)(自然科學(xué)版);2004年04期

8 陳方淦,孫良;平面圖選擇控制集問(wèn)題的復(fù)雜性分析及算法設(shè)計(jì)[J];北京理工大學(xué)學(xué)報(bào);2003年03期

9 王春香,毛經(jīng)中,陳晶晶;關(guān)于邊控制集的一些結(jié)論[J];華中師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年02期

10 于崇智;關(guān)于集控制集的若干結(jié)論[J];華東交通大學(xué)學(xué)報(bào);1997年01期

相關(guān)重要報(bào)紙文章 前2條

1 宦建新　通訊員　沈維強(qiáng);浙江“食品安全科技專項(xiàng)”取得成果[N];科技日?qǐng)?bào);2005年

2 石家莊市畜牧水產(chǎn)局 趙洪明　強(qiáng)慧勤 王榮申 張濤 李釗;養(yǎng)殖投入品控制集成技術(shù)[N];河北科技報(bào);2013年

相關(guān)博士學(xué)位論文 前10條

1 毛睿;圖的配對(duì)控制集問(wèn)題和電力控制集問(wèn)題的研究[D];華東師范大學(xué);2018年

2 劉星;有源前端變流器的有限控制集模型預(yù)測(cè)控制研究[D];大連海事大學(xué);2018年

3 陳磊;圖中配對(duì)控制集問(wèn)題的機(jī)械化算法研究[D];華東師范大學(xué);2010年

4 黃佳;圖的控制穩(wěn)定性研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2007年

5 劉清海;幾類組合優(yōu)化問(wèn)題的算法研究[D];新疆大學(xué);2012年

6 陳星;幾類圖的連通性和控制集[D];新疆大學(xué);2011年

7 李憲越;關(guān)于一些網(wǎng)絡(luò)最優(yōu)化問(wèn)題的近似算法的研究[D];蘭州大學(xué);2009年

8 趙維勝;關(guān)于樹的控制問(wèn)題與強(qiáng)乘積圖約束數(shù)的研究[D];蘭州大學(xué);2015年

9 胡夫濤;圖的約束數(shù)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2012年

10 陸由;圖的控制理論研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 周瑜;點(diǎn)權(quán)值圖的k-電力控制集問(wèn)題的算法研究[D];華東師范大學(xué);2018年

2 于俊英;阿基米德鋪砌圖中定位控制集的研究[D];河北師范大學(xué);2018年

3 趙利芬;關(guān)于圖的控制集劃分[D];華東交通大學(xué);2015年

4 李秀英;求最小2連通r步控制集的兩種算法[D];新疆大學(xué);2011年

5 羅傳文;無(wú)線網(wǎng)絡(luò)中連通控制集的算法設(shè)計(jì)與分析[D];曲阜師范大學(xué);2016年

6 秦云龍;連通控制集的構(gòu)造與維護(hù)算法研究[D];曲阜師范大學(xué);2010年

7 陳春霞;關(guān)于路和圈的驗(yàn)證碼和定位控制集問(wèn)題[D];華東師范大學(xué);2009年

8 盛斌;立方圖的配對(duì)控制集問(wèn)題上界[D];華東師范大學(xué);2013年

9 丁玲玲;圖的控制集問(wèn)題的近似算法研究[D];中國(guó)海洋大學(xué);2008年

10 何永能;圖的電力控制集問(wèn)題[D];華東師范大學(xué);2012年

本文編號(hào)：2635917