一些圖的填充和樹寬.pdf

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

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

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