發(fā)布時間：2020-11-21 07:36

　　 圖的消圈數(shù)和不可分獨立數(shù)是圖劃分理論的兩類經(jīng)典問題,兩者之間有著千絲萬縷的聯(lián)系.它們在無線傳感器網(wǎng)絡(luò)和組合電路設(shè)計等領(lǐng)域中有著廣泛的應(yīng)用,近些年來受到了極大關(guān)注.本文主要研究圖的消圈數(shù)和不可分獨立數(shù)及其應(yīng)用.具體內(nèi)容如下:1.首先對圖論的一些基本概念和術(shù)語做了介紹.隨后,比較全面地列舉了與本文相關(guān)的消圈數(shù)和不可分獨立數(shù)問題的研究背景、發(fā)展現(xiàn)狀.最后給出了本文的主要結(jié)論.2.首先運用圖嵌入的方法給出了一個計算次3-正則圖的消圈數(shù)的公式.進一步,給出了在3-正則圖中(?)成立的充分必要條件.3.借助消圈數(shù)這一參量分別建立了滿足條件(?)的圖是Hamilton圖、泛圈圖和邊-Hamilton圖的充分條件.4.首先給出一個計算圖的不可分獨立數(shù)的公式,然后借助這個公式求得了超立方體(?)的不可分獨立數(shù).隨后,利用兩個圈的笛卡爾積(?)的消圈數(shù),給出了(?)的不可分獨立數(shù).與此同時,找到了(?)的最大不可分獨立集.最后,刻畫了次3-正則圖的最大不可分獨立集的分布,并對圖的最大虧格和不可分獨立數(shù)這兩者的關(guān)系做了進一步討論.5.首先借助最大割給出了計算圖二部頂點挫敗指標(biāo)的具體公式,然后利用此公式得到了一些圖類(包括稠密圖)的二部頂點挫敗指標(biāo)的上界或者精確值.同時,我們研究了五類組合圖的二部頂點挫敗指標(biāo).最后,對稠密圖的消圈數(shù)問題進行了探討.
【學(xué)位單位】：華東師范大學(xué)
【學(xué)位級別】：博士
【學(xué)位年份】：2020
【中圖分類】：O157.5
【部分圖文】：

第二章圖的消圈數(shù)與連通消圈數(shù)假設(shè)是這個點且()={,},易證=+連通且無三角形.若()≤2,通過歸納假設(shè),它有一個森林滿足||≥12(1)929≥()1.否則,是3-正則圖.而Bondy等人[12]證明了對任一個無三角形的次3-正則圖,()≥2|()|313.從而有一個森林滿足||≥23(1)13≥()1.在以上任何一種情形中,均有∪{}是中階數(shù)≥()的森林.斷言5.若有一個2-度點,則()≥().假設(shè)是個2-度點且()={,}.由斷言4可知和還有另外一個共同的鄰居,記為.結(jié)合斷言1,2,3,我們可以推導(dǎo)出()=()=()=3.接下來,分如下兩種情況來討論情況1.頂點和有除和外的第三個共同鄰居,記為.在這種情形下,由斷言3,()=3.假設(shè)和有除和以外的第三個共同鄰居,記為.若()=2,那么是由{,,,,,}作為頂點集構(gòu)成的邊數(shù)為8的次3-正則圖,并且={,,,}誘導(dǎo)出的一個森林(見圖2.2.3).不難驗證||≥62×8929.若()=3,則與的某條割邊關(guān)聯(lián),這與是2-連通這一假設(shè)矛盾.所以,頂點對與只有兩個共同的鄰居,那就是和.這樣,={,,}+連通且無三角形,從而它有森林滿足||≥32(5)929≥()2.因此,∪{,}是的一個誘導(dǎo)森林且||≥().圖2.2.3:()=2的情形.情況2.頂點和只有兩個共同的鄰居和.令和分別是和的第三個鄰居.從斷言3可知()=()=3.假設(shè)/∈(),={,,}++.顯然,連通且無三角形.由歸納假設(shè),有一個森林滿足||≥32(5)923≥()2.從而∪{,}是的一個森林·19·

第二章圖的消圈數(shù)與連通消圈數(shù)圖2.3.1展示了當(dāng)()的一個分支分別是4-圈,5-圈,4-路和5-路時,1,2,1的選取方式.圖2.3.1:的選取方法.接下來,我們利用定理2.10來證明()=()在3-正則Halin圖和廣義Petersen圖中均成立.Halin圖是由德國數(shù)學(xué)家Halin提出的極小3-連通平面圖.給定一棵樹,其內(nèi)部頂點度數(shù)至少為3.將嵌入到一個平面中,然后添加一些依次連接的葉子的邊來組成一個圈.由此得到的圖=∪即為Halin圖,其中稱為的特征樹,為的伴隨圈.我們把定理2.10應(yīng)用到3-正則Halin圖上,很容易得到()=().這是因為選取作為的一棵Xuong-樹后,()的唯一可能的奇連通分支至少包含3條邊.廣義Petersen圖,是由頂點集(,)={,:1≤≤}和邊集(,)={,+1,+:1≤≤}構(gòu)成的階數(shù)為2的圖,其中,正整數(shù)且>2.這里所有的下標(biāo)均取模.令是和的最大公約數(shù).為方便起見,記={:1≤≤},={:1≤≤}.Gao等人在文獻[33]中刻畫了廣義Petersen圖的內(nèi)部結(jié)構(gòu).引理2.3(Gao等[33])[]是由長度為的個圈組成,且每個圈均可表示為如下形式=++2···+(1),下標(biāo)取模,=1,2,...,.·21·

2:8,2與其Xuong-樹.
【相似文獻】

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

1 常立婷;師海忠;;基于超立方體和圈的細胞分裂生長網(wǎng)絡(luò)及其性質(zhì)[J];軟件;2017年09期

2 趙學(xué)峰,李喜平;廣義超立方體的點擴張[J];西北師范大學(xué)學(xué)報(自然科學(xué)版);2002年04期

3 王曉迪;;最優(yōu)對稱拉丁超立方體的構(gòu)造[J];系統(tǒng)科學(xué)與數(shù)學(xué);2020年02期

4 陳浩;張艷;;投影均勻分片拉丁超立方體設(shè)計[J];系統(tǒng)科學(xué)與數(shù)學(xué);2020年02期

5 金丹;劉紅美;張艷娟;;交換超立方體結(jié)構(gòu)性質(zhì)的一些注記[J];南陽理工學(xué)院學(xué)報;2018年02期

6 高煒;梁立;;塊轉(zhuǎn)換網(wǎng)絡(luò)和分級超立方體網(wǎng)絡(luò)的化學(xué)指標(biāo)計算[J];蘇州科技大學(xué)學(xué)報(自然科學(xué)版);2017年03期

7 曹瑾;肖力;徐俊明;;變形超立方體的圈和路嵌入(英文)[J];中國科學(xué)技術(shù)大學(xué)學(xué)報;2014年09期

8 蔣魯威;梁家榮;;扭立方體網(wǎng)絡(luò)到交換超立方體網(wǎng)絡(luò)嵌入問題研究[J];廣西科技大學(xué)學(xué)報;2014年03期

9 范漪涵;劉紅美;劉敏;;故障折疊超立方體中的路和圈(英文)[J];數(shù)學(xué)雜志;2013年03期

10 梁錦葉;梁家榮;;交換超立方體網(wǎng)絡(luò)的網(wǎng)絡(luò)嵌入研究[J];計算機工程與科學(xué);2011年08期

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

1 曹法赟;圖的消圈數(shù)與不可分獨立數(shù)[D];華東師范大學(xué);2020年

2 樊衛(wèi)北;交換超立方體和3-元n-立方體在網(wǎng)格與環(huán)繞中的嵌入[D];蘇州大學(xué);2019年

3 劉晗;超立方體排隊均衡下消防協(xié)同救援設(shè)施選址配置優(yōu)化研究[D];哈爾濱工業(yè)大學(xué);2018年

4 齊豪;扭曲超立方體和平面圖的結(jié)構(gòu)研究[D];浙江師范大學(xué);2018年

5 陳浩;復(fù)雜結(jié)構(gòu)拉丁超立方體設(shè)計的構(gòu)造[D];南開大學(xué);2013年

6 尹玉輝;拉丁超立方體設(shè)計的構(gòu)造與超飽和設(shè)計的分析[D];南開大學(xué);2013年

7 杜正中;容錯網(wǎng)絡(luò)的路和圈研究[D];中國科學(xué)技術(shù)大學(xué);2006年

8 王國軍;具有大量錯誤結(jié)點的超立方體網(wǎng)絡(luò)容錯模型和容錯路由算法研究[D];中南大學(xué);2002年

9 李顯勇;幾類光互連網(wǎng)絡(luò)的診斷性與容錯性[D];重慶大學(xué);2014年

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

1 景小飛;類超立方體關(guān)于極大局部連通性的容錯度[D];山西大學(xué);2019年

2 楊進霞;廣義b-基超立方體的控制參數(shù)及其圈積的Hamilton分解[D];西北師范大學(xué);2019年

3 殷世德;圖上的幾類量子游蕩的相關(guān)性質(zhì)研究[D];西北師范大學(xué);2019年

4 王垚;正交拉丁超立方體設(shè)計的子設(shè)計選擇[D];東北師范大學(xué);2019年

5 許萍;增增強超立方體的譜及其基爾霍夫指標(biāo)[D];新疆大學(xué);2019年

6 于雪;投影均勻下基于正交表的拉丁超立方體設(shè)計[D];東北師范大學(xué);2018年

7 李德賽;大規(guī)模網(wǎng)絡(luò)的容錯性分析[D];清華大學(xué);2017年

8 張偉華;兩類網(wǎng)絡(luò)的容錯偶泛圈性研究[D];蘭州理工大學(xué);2018年

9 范娜琪;類超立方體的限制弧連通度[D];山西大學(xué);2018年

10 李莉莉;超立方體及其變體結(jié)構(gòu)網(wǎng)絡(luò)的可靠性研究[D];西安電子科技大學(xué);2018年

本文編號：2892741