度序列與樹、超樹.pdf

1、“可圖度序列問題”是圖論中很有名而又較復(fù)雜的問題，國內(nèi)外關(guān)于這個問題的結(jié)論很多，但涉及研究“可樹度序列問題”以及“可超樹度序列問題”卻很少。而對于超圖中的線性超樹，由于它自身結(jié)構(gòu)的特殊性，目前還沒有得到對其懸掛邊數(shù)目進行精確計算的有效算法以及關(guān)于特殊標號含圈廣義線性超樹計數(shù)方面的結(jié)論。鑒于此，本文分別在樹、狹義超樹、廣義超樹三部分中做了下列幾個方面的工作。 首先，從分析樹與其葉子總數(shù)之間的關(guān)系入手，通過引入分枝點并借助構(gòu)造證明的

2、思想，得到了判斷可樹度序列的充要條件和一系列推論，并且按照同樣的方法把它推廣到研究森林和樹形圖中。 其次，根據(jù)在研究超圖的過程中常用到的推廣延伸的思想，把圖論中研究可樹度序列的方法，通過分析超樹與其孤立點總數(shù)之間的關(guān)系，推廣應(yīng)用到研究狹義超樹和廣義超樹中。在其中主要利用超樹的對應(yīng)二部圖作為研究的橋梁，來達到刻劃線性超樹的頂點與超邊結(jié)構(gòu)的目的，在非線性超樹的研究中根據(jù)圖論中邊細分的思想，定義了超圖對應(yīng)二部圖的點細分。最終，得到了判

3、斷可超樹度序列的幾個相關(guān)定理和一系列推論，并且通過探討超圖圈結(jié)構(gòu)的不同定義，得到了關(guān)于狹義超樹和廣義超樹之間關(guān)系的一些有意義的命題，從而進一步揭示了度序列與線性超樹的關(guān)系。 然后，在超樹中根據(jù)線性超樹懸掛邊與其孤立點之間的特殊對應(yīng)關(guān)系，提出了求線性超樹懸掛邊數(shù)目的一種有效、可行的算法，其算法復(fù)雜度僅為 。在廣義超樹中根據(jù)線性超圖和廣義超樹的性質(zhì)，得出了一類標號含圈廣義線性超樹的計數(shù)上下界以及相應(yīng)的多圈線性超圖的計數(shù)上下界。