【摘要】：控制集是圖論的一個(gè)重要概念,它是指圖中的一個(gè)點(diǎn)集,使得圖中其它任何一點(diǎn)在該點(diǎn)集都至少有一個(gè)鄰點(diǎn).圖的配對(duì)控制集問(wèn)題和電力控制集問(wèn)題是兩類重要的控制集問(wèn)題.本文對(duì)這兩類控制集問(wèn)題展開(kāi)研究.設(shè)圖G =(V,E)為無(wú)孤立頂點(diǎn)的簡(jiǎn)單圖.S(?)V是G的一個(gè)配對(duì)控制集當(dāng)且僅當(dāng)V\S中每個(gè)頂點(diǎn)都與S中某點(diǎn)相鄰,并旦G[S]有完美匹配.圖G的配對(duì)控制數(shù),記γpr(G),定義為min{|S|| S為G的配對(duì)控制集}.設(shè)圖G =(V,E)為簡(jiǎn)單圖.S(?)V是G的一個(gè)電力控制集當(dāng)且僅當(dāng)V中所有的點(diǎn)可以通過(guò)下面兩種方式獲得信息:(1)如果v ∈ S,那么v傳遞信息給自己和所有的鄰點(diǎn).(2)如果一個(gè)有信息的點(diǎn)υ僅有唯一一個(gè)鄰點(diǎn)u沒(méi)有信息,那么v傳遞信息給u.圖G的電力控制數(shù),記γp(G),定義為min{|S|| S為G的電力控制集}.k-電力控制集問(wèn)題是電力控制集問(wèn)題的自然推廣.設(shè)圖G =(V,E)為簡(jiǎn)單圖,k是非負(fù)整數(shù).S(?)V是G的一個(gè)k-電力控制集當(dāng)且僅當(dāng)V中所有的點(diǎn)可以通過(guò)下面兩種方式獲得信息:(1)如果v ∈ S,那么v傳遞信息給自己和所有的鄰點(diǎn).(2)如果一個(gè)有信息的點(diǎn)v至多有k個(gè)鄰點(diǎn)沒(méi)有信息,那么v傳遞信息給自己所有沒(méi)有信息的鄰點(diǎn).類似地,圖G的k-電力控制數(shù),記γp,k(G),定義為min{|S|| S為G的k-電力控制集}.當(dāng)k = 0時(shí),k-電力控制集問(wèn)題就是控制集問(wèn)題.當(dāng)k = 1時(shí),k-電力控制集問(wèn)題就是電力控制集問(wèn)題.在圖的控制集問(wèn)題的研究中,確定控制數(shù)的上界是一個(gè)主流研究方向,無(wú)爪圖是圖論研究的重要圖類.本文第一章介紹配對(duì)控制集問(wèn)題和電力控制集問(wèn)題的背景和研究現(xiàn)狀.在第二章和第三章,我們分別對(duì)無(wú)爪圖的配對(duì)控制數(shù)和電力控制數(shù)的上界進(jìn)行了探討.Goddard和Henning在2009年提出猜想:令G(?)P是一個(gè)n階連通圖,在這里P表示Petersen圖.若δ(G)≥3,則γpr(G)≤4n/7.這是配對(duì)控制數(shù)上界研究的一個(gè)重要猜想.本文第二章對(duì)無(wú)爪圖的配對(duì)控制集問(wèn)題展開(kāi)研究.我們證明了:令G是一個(gè)n階無(wú)爪圖,若δ(G)≥ 4,則γpr(G)≤n/2 并且這個(gè)上界是可達(dá)的(見(jiàn)定理2.1.1).該結(jié)果改進(jìn)了 Cao和Shan等人2016年的結(jié)果.Dorbec等人在2013年提出猜想:令G =(V,E)是一個(gè)n階r-正則連通圖,其中≥ 1,r ≥ 3.若G(?)Kr,r,則γp,k(G)≤n/r+1,其中Kr,r是完全二部圖.Dorbec等人證明了該猜想對(duì)k = 1,r = 3的情形成立.在本文第三章中,我們首先找到一系列r-正則無(wú)爪圖(r ≥ 4為偶數(shù))作為反例,部分否定了 Dorbec等人的猜想.然后,我們研究4-正則無(wú)爪圖的電力控制數(shù)的上界,證明了:若G =(V,E)是一個(gè)n階4-正則連通無(wú)爪圖,則γp(G)≤n+1/5,并且這個(gè)上界是可達(dá)的(見(jiàn)定理3.1.1).
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.5
【圖文】：

圖 1: 棋盤(pán)本專著 [50, 52], 專著中較為系統(tǒng)地闡述了有關(guān)圖的控圖控制集的定義. 是圖 的頂點(diǎn)集的一個(gè)子集, 對(duì)每個(gè) 中的點(diǎn)和 相鄰, 則稱 是 的一個(gè)控制集.圖 = ( , ) 的一個(gè)控制集有如下等價(jià)定義: 對(duì)于每個(gè) ∈ ;中的點(diǎn) , | [ ] ∩ | ≥ 1; 中的點(diǎn) , | ( ) ∩ | ≥ 1.果 是圖 的一個(gè)控制集, 那么任意點(diǎn)集 ′ 也是

【相似文獻(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)樹(shù)狀網(wǎng)絡(luò)中r-控制集問(wèn)題和k-中心問(wèn)題[J];運(yùn)籌學(xué)學(xué)報(bào);2009年02期

4 羅永萍;楊愛(ài)民;;有向路和有向圈的控制集數(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 陳磊;圖中配對(duì)控制集問(wèn)題的機(jī)械化算法研究[D];華東師范大學(xué);2010年

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

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

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

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

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

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

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

10 王超;圖的配對(duì)控制數(shù)和彩虹控制數(shù)研究[D];華東師范大學(xué);2015年

相關(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)：2795179