【摘要】：圖的連通性在圖論的研究領(lǐng)域中是很重要的,它們對(duì)圖論的發(fā)展有著重大的影響和推動(dòng)作用.k-可收縮邊是研究連通圖的構(gòu)造的強(qiáng)有力工具,在使用歸納證明連通圖的性質(zhì)也起著重要作用.k-樹圖是k連通圖的一種,其有著諸多有趣的組合性質(zhì).很多NP-困難問題在有限的k-樹圖中都有多項(xiàng)式算法.本文以論文[2,7]為基礎(chǔ),定義了一個(gè)與k-樹圖G對(duì)應(yīng)的新圖T(G),單純點(diǎn)集合S(G),RP-運(yùn)算.研究了它們的性質(zhì)、特征及與GC之間的關(guān)系,對(duì)k-樹圖的可收縮邊導(dǎo)出子圖的結(jié)構(gòu)進(jìn)行了研究,給出了k-樹圖可收縮邊數(shù)目的下界,完全解決了k-樹圖可收縮邊導(dǎo)出子圖的連通度問題.主要結(jié)果有：1.k-樹圖可收縮邊的計(jì)數(shù).本文引入關(guān)于k-樹的一個(gè)新的參數(shù)T(G),得到了k-樹圖G可收縮邊數(shù)目更一般的下界與不可收縮邊的數(shù)目的范圍,并完全刻畫了可收縮邊數(shù)目恰為|G|+K-2的k-樹圖的結(jié)構(gòu)特征.給出了T(G)中任意兩點(diǎn)的距離與G中兩點(diǎn)之間的距離關(guān)系式.2.k-樹圖收縮邊導(dǎo)出子圖的連通性.本文引入單純點(diǎn)集合S(G)的概念,證明了κ(GC)=δ(Gc),當(dāng)3≤δ(GC) k,Gc是超連通.3.k-樹圖導(dǎo)出圖T(G)的結(jié)構(gòu)特征.本文引入RP-運(yùn)算,證明了Gc是k-正則當(dāng)且僅當(dāng)G是由兩個(gè)特殊的k-樹圖通過RP-運(yùn)算得到.
【學(xué)位授予單位】：廣西師范學(xué)院
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 王金超;谷風(fēng);;圖的鄰接樹圖是哈密爾頓的[J];蘭州交通大學(xué)學(xué)報(bào);2007年03期

2 魏二玲;劉彥佩;;(鄰接)樹圖的同構(gòu)及平面性[J];數(shù)學(xué)進(jìn)展;2009年02期

3 申石虎;;樹圖[J];東北重型機(jī)械學(xué)院學(xué)報(bào);1980年01期

4 卜月華;;完全鄰接樹圖的特征[J];浙江師范學(xué)院學(xué)報(bào)(自然科學(xué)版);1988年02期

5 黃容坤;;文圖和樹圖在概率中的應(yīng)用[J];河池師專學(xué)報(bào)(理科);1991年03期

6 劉儒英;關(guān)于不可約的T形樹圖[J];青海師專學(xué)報(bào);1997年02期

7 楊春德;樹圖集散函數(shù)與中心的性質(zhì)[J];重慶郵電學(xué)院學(xué)報(bào);1998年03期

8 牛秋成;;利用樹圖法解排列題[J];數(shù)學(xué)學(xué)習(xí)與研究;2011年11期

9 張?zhí)m菊;鄰接樹圖是哈密爾頓圖猜想的一個(gè)等價(jià)命題(英文)[J];應(yīng)用數(shù)學(xué);2000年04期

10 李明哲;階數(shù)最小的A(H)=4的非樹圖[J];哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào);2003年05期

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

1 黃樂賢;K-樹圖的可收縮邊[D];廣西師范學(xué)院;2015年

2 劉秀國(guó);偽樹圖的譜矩序列[D];湖北大學(xué);2011年

3 杜建偉;1-樹圖的鄰點(diǎn)可區(qū)別全染色[D];山西大學(xué);2006年

4 高晶;樹理論在分組測(cè)試中的應(yīng)用[D];中國(guó)地質(zhì)大學(xué)（北京）;2010年

5 李劍鋒;可由其拉普拉斯譜確定的一些樹圖[D];湖南師范大學(xué);2008年

6 白建甜;幾類樹圖的能量及超能量圖[D];廣東工業(yè)大學(xué);2008年

7 卞彩鳳;準(zhǔn)樹圖的最大廣義Randi（？）指標(biāo)[D];廈門大學(xué);2009年

8 崔日升;廣義Randi（？）指標(biāo)在樹圖上的最大化問題[D];南開大學(xué);2009年

9 劉鑫;有限樹圖上擴(kuò)散算子的Borg-Levinson型定理[D];南京理工大學(xué);2010年

10 謝筍;三角樹圖和K_4樹圖的Hosoya指標(biāo)和Merrifield-Simmons指標(biāo)研究[D];青海師范大學(xué);2015年

，

本文編號(hào)：2513470