本文關(guān)鍵詞：若干圖類的子樹(shù)或塊割點(diǎn)子樹(shù)計(jì)數(shù)算法研究

  更多相關(guān)文章： 樹(shù) 圈鏈圖 子樹(shù) 塊割點(diǎn)子樹(shù) 計(jì)數(shù)算法

【摘要】：圖論和算法是計(jì)算機(jī)學(xué)科的主要研究領(lǐng)域,它們?yōu)榻鉀Q眾多科學(xué)問(wèn)題提供理論依據(jù)和實(shí)施方案。子樹(shù)數(shù)和BC-子樹(shù)數(shù)是兩個(gè)重要的圖結(jié)構(gòu)化拓?fù)鋮?shù),跟混合網(wǎng)絡(luò)局部可靠性及化合物的物理和化學(xué)性質(zhì)關(guān)系密切。本文基于圖論,通過(guò)Tutte和新的三元Tutte多項(xiàng)式和結(jié)構(gòu)分析的方法,研究樹(shù)、單圈圖、無(wú)公共邊的雙圈圖、以及與PM2.5中重要的致癌物質(zhì)分子對(duì)應(yīng)的六元素環(huán)螺鏈圖、聚苯六角鏈圖、六角形鏈圖和聚亞苯基鏈圖的子樹(shù)或BC-子樹(shù)計(jì)數(shù)算法問(wèn)題,取得如下研究成果：(1)給出了新的三元Tutte多項(xiàng)式,并通過(guò)樹(shù)“收縮”操作,給出了樹(shù)的含給定頂點(diǎn)且所有葉子到該頂點(diǎn)的距離都是奇(偶)數(shù)的子樹(shù)的計(jì)數(shù)算法,并進(jìn)一步給出了樹(shù)的所有、含任給一個(gè)、兩個(gè)頂點(diǎn)的BC-子樹(shù)的計(jì)數(shù)算法,確定了n個(gè)頂點(diǎn)樹(shù)中具有最大和最小BC-子樹(shù)數(shù)的樹(shù)分別為星樹(shù)和路徑,給出了廣義Bethe樹(shù)的子樹(shù)及BC-子樹(shù)數(shù),提出BC-子樹(shù)密度的概念并分析了樹(shù)枝狀分子圖的BC-子樹(shù)密度漸進(jìn)特性。(2)基于新的三元Tutte多項(xiàng)式和樹(shù)的BC-子樹(shù)的計(jì)數(shù)算法,針對(duì)單圈圖和無(wú)公共邊雙圈圖,給出了含給定頂點(diǎn)且所有葉子到該頂點(diǎn)的距離都是奇(偶)數(shù)的子樹(shù)的計(jì)數(shù)算法,在此基礎(chǔ)上,給出了計(jì)算單圈和無(wú)公共邊的雙圈圖的全部、含任意一個(gè)、兩個(gè)頂點(diǎn)的BC-子樹(shù)的生成函數(shù)的計(jì)數(shù)算法,并給出相應(yīng)算法實(shí)現(xiàn)的實(shí)例分析。(3)針對(duì)六元素環(huán)螺鏈圖G。和聚苯六角鏈圖(?),通過(guò)Tutte和新的三元Tutte多項(xiàng)式、圈權(quán)重的“收縮傳遞”及結(jié)構(gòu)分析的方法,首先給出Gn(Gn)的含割點(diǎn)C仡(尾點(diǎn)tn)的子樹(shù)及含cn(tn)且所有的葉子到cn(tn)的距離分別是奇數(shù)和偶數(shù)的子樹(shù)的生成函數(shù),然后推導(dǎo)出它們的子樹(shù)和BC-子樹(shù)的生成函數(shù),給出了它們關(guān)于子樹(shù)(BC-)子樹(shù)數(shù)間的關(guān)系、極值、極圖結(jié)構(gòu),首次將Wiener和子樹(shù)數(shù)指標(biāo)的“反序”關(guān)系證明推廣到分子鏈圖上,并分析了這兩類鏈圖的子樹(shù)和BC-子樹(shù)密度。(4)針對(duì)六角形鏈圖Gn、聚亞苯基鏈圖瓦,通過(guò)Tutte多項(xiàng)式和結(jié)構(gòu)分析的方法,首先給出Gn(Gn)以及輔助圖(?)-1)的含相鄰六元素圈的公共邊(un,vn)(相鄰四和六元素圈的公共邊(un,vn)及(pn-1,qn-1))的子樹(shù)的生成函數(shù),然后推導(dǎo)出它們子樹(shù)的生成函數(shù),在此基礎(chǔ)上給出兩類鏈圖的基于樹(shù)收縮(TCB)的子樹(shù)計(jì)數(shù)算法,并給出了兩類鏈圖關(guān)于子樹(shù)數(shù)的極值、極值圖及子樹(shù)密度分析。
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前4條

1 袁超;柴毅;;復(fù)雜網(wǎng)絡(luò)的局部社團(tuán)結(jié)構(gòu)挖掘算法[J];自動(dòng)化學(xué)報(bào);2014年05期

2 朱瑩;任立紅;丁永生;Kongsuwan Kritaya;;背包問(wèn)題DNA算法的反應(yīng)設(shè)計(jì)及其生物實(shí)現(xiàn)(英文)[J];計(jì)算機(jī)學(xué)報(bào);2008年12期

3 張蓮珠 ,田豐;Extremal hexagonal chains concerning largest eigenvalue[J];Science in China,Ser.A;2001年09期

4 李曉明;網(wǎng)絡(luò)可靠性綜合的現(xiàn)狀及其展望[J];計(jì)算機(jī)學(xué)報(bào);1990年09期

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前3條

1 張修梅;圖的結(jié)構(gòu)與圖的子樹(shù)個(gè)數(shù)[D];上海交通大學(xué);2014年

2 王炳波;復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)度量指標(biāo)及應(yīng)用研究[D];西安電子科技大學(xué);2014年

3 崔衛(wèi)紅;基于圖論的面向?qū)ο蟮母叻直媛视跋穹指罘椒ㄑ芯縖D];武漢大學(xué);2010年

，

本文編號(hào)：1276818