度序列與樹、超樹.pdf

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

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

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