度序列與樹、超樹.pdf

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

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

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