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

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

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

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

2:8,2與其Xuong-樹.
【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：2892741