若干圖類的子樹或塊割點(diǎn)子樹計(jì)數(shù)算法研究.pdf

1、圖論和算法是計(jì)算機(jī)學(xué)科的主要研究領(lǐng)域，它們?yōu)榻鉀Q眾多科學(xué)問題提供理論依據(jù)和實(shí)施方案。子樹數(shù)和BC-子樹數(shù)是兩個(gè)重要的圖結(jié)構(gòu)化拓?fù)鋮?shù)，跟混合網(wǎng)絡(luò)局部可靠性及化合物的物理和化學(xué)性質(zhì)關(guān)系密切。本文基于圖論，通過Tutte和新的三元Tutte多項(xiàng)式和結(jié)構(gòu)分析的方法，研究樹、單圈圖、無公共邊的雙圈圖、以及與PM2.5中重要的致癌物質(zhì)分子對(duì)應(yīng)的六元素環(huán)螺鏈圖、聚苯六角鏈圖、六角形鏈圖和聚亞苯基鏈圖的子樹或BC-子樹計(jì)數(shù)算法問題，取得如下研究成果:

2、
　　(1)給出了新的三元Tutte多項(xiàng)式，并通過樹“收縮”操作，給出了樹的含給定頂點(diǎn)且所有葉子到該頂點(diǎn)的距離都是奇（偶）數(shù)的子樹的計(jì)數(shù)算法，并進(jìn)一步給出了樹的所有、含任給一個(gè)、兩個(gè)頂點(diǎn)的BC-子樹的計(jì)數(shù)算法，確定了n個(gè)頂點(diǎn)樹中具有最大和最小BC-子樹數(shù)的樹分別為星樹和路徑，給出了廣義Bethe樹的子樹及BC-子樹數(shù)，提出BC-子樹密度的概念并分析了樹枝狀分子圖的BC-子樹密度漸進(jìn)特性。
　　(2)基于新的三元Tutte多項(xiàng)

3、式和樹的BC-子樹的計(jì)數(shù)算法，針對(duì)單圈圖和無公共邊雙圈圖，給出了含給定頂點(diǎn)且所有葉子到該頂點(diǎn)的距離都是奇（偶）數(shù)的子樹的計(jì)數(shù)算法，在此基礎(chǔ)上，給出了計(jì)算單圈和無公共邊的雙圈圖的全部、含任意一個(gè)、兩個(gè)頂點(diǎn)的BC-子樹的生成函數(shù)的計(jì)數(shù)算法，并給出相應(yīng)算法實(shí)現(xiàn)的實(shí)例分析。
　　(3)針對(duì)六元素環(huán)螺鏈圖Gn和聚苯六角鏈圖(G)n，通過Tutte和新的三元Tutte多項(xiàng)式、圈權(quán)重的“收縮傳遞”及結(jié)構(gòu)分析的方法，首先給出Gn（(G)n）的含割

4、點(diǎn)cn（尾點(diǎn)tn）的子樹及含cn(tn)且所有的葉子到cn(tn)的距離分別是奇數(shù)和偶數(shù)的子樹的生成函數(shù)，然后推導(dǎo)出它們的子樹和BC-子樹的生成函數(shù)，給出了它們關(guān)于子樹(BC-)子樹數(shù)間的關(guān)系、極值、極圖結(jié)構(gòu)，首次將Wiener和子樹數(shù)指標(biāo)的“反序”關(guān)系證明推廣到分子鏈圖上，并分析了這兩類鏈圖的子樹和BC-子樹密度。
　　(4)針對(duì)六角形鏈圖Gn、聚亞苯基鏈圖(G)n，通過Tutte多項(xiàng)式和結(jié)構(gòu)分析的方法，首先給出Gn（(G)n以