一些圖的填充和樹(shù)寬.pdf

1、最優(yōu)標(biāo)號(hào)與最優(yōu)嵌入問(wèn)題是組合最優(yōu)化學(xué)科非?；钴S的一個(gè)研究課題.,它具有很強(qiáng)的應(yīng)用性,并且包含一系列內(nèi)容相當(dāng)豐富的理論問(wèn)題.該文的研究與其中的兩個(gè)問(wèn)題有關(guān).由以下兩部分組成:(1)一些圖的填充問(wèn)題,(2)一些圖的樹(shù)寬問(wèn)題.1一些圖的填充問(wèn)題填充問(wèn)題具有強(qiáng)烈的實(shí)際背景.在實(shí)際中經(jīng)常要處理一個(gè)稀疏的對(duì)稱正定方陣的線性方程組Ax=b的求解問(wèn)題,其中A為稀疏的,即其中非零元較少,大部分是零.在運(yùn)用Gauss消去法或Cholesky分解法求解時(shí),消

2、去過(guò)程中有的零元會(huì)變?yōu)榉橇阍?這稱為矩陣的填充.如果消元順序不當(dāng),填充的非零元越來(lái)越多,增加了存貯量,便會(huì)影響運(yùn)算速度,降低工作效率.所以在消元過(guò)程中,需要確定適當(dāng)?shù)南樞?使填充的非零元較少.這稱為矩陣的填充優(yōu)化問(wèn)題.由于正定對(duì)稱矩陣與一個(gè)圖相對(duì)應(yīng),由此導(dǎo)出了圖的填充問(wèn)題.2.一些圖的樹(shù)寬問(wèn)題.樹(shù)寬問(wèn)題是Robertson和Seymour在建立圖的minor理論時(shí)提出的兩個(gè)概念之一[6-7].劉振宏和王常藩從算法復(fù)雜性的估計(jì)中提出了

3、另一參數(shù)"核密度"[8].楊?lèi)?ài)民和林詒勛在文[9]又證明核密度就是樹(shù)寬,它們相應(yīng)于矩陣的消去過(guò)程的波前寬度.這個(gè)問(wèn)題同樣是圍繞著計(jì)算復(fù)雜性、算法理論、特殊圖結(jié)果、運(yùn)算性質(zhì)等方面進(jìn)行.S.Arnborg, D.Corneil和A.Proskurowski于1987年證明了樹(shù)寬問(wèn)題的NP-完全性[15],文[9]中推得確定弦圖的樹(shù)寬是多項(xiàng)式可解的.關(guān)于特殊圖的結(jié)果,圖論工作者已經(jīng)涉足此領(lǐng)域,但與其它標(biāo)號(hào)問(wèn)題相比,結(jié)果還不多.對(duì)于一些已知結(jié)構(gòu)