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

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

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

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

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