几类特殊图的最优填充.pdfVIP

第25卷 第 1期 河 南 科 技 大 学 学 报 (自然 科 学 版 ) V0】．25 No．1 2OO4年 2月 JoumalofHenanUniversityofScienceandTechnology(NaturalScience) Feb． 20o4 文章编号 ：1672—6871(2004)01—0093—04 几类特殊图的最优填充 冯爱芬 (河南科技大学 数理系，河南 洛阳471003) 摘要：图的最优填充在稀疏矩阵计算中有重要的作用。利用图的分解定理和约化准则给出了扇形格子图 ． (m =1，2；1／,=1，2，3)和球面经纬图 、(m =1；n=3，4)及(m，1／,)一构形等的填充数表达式，从而为确 定这些图类的填充奠定了基础，并提出进一步研究的建议。 关键词：填充；最优化方法；图 中图分类号：O241．6 文献标识码：A 0 前言 对于一个对称方阵的线性方程组AX=b(其中系数矩阵A为稀疏的正定对称矩阵，即其中非零元 较少，大部分是零)，运用 Gauss消去法或Cholesky分解法求解该方程组时，为了减少存贮量，需要确定适 当的消元顺序，使填充的非零元较少，这称为矩阵的填充优化问题[】]。由于正定对称矩阵与一个图相 对应，由此导出了图的填充问题。一般图的填充问题被证 明为NP一完全的 J，因而对一般图的填充问 题不可能有好算法。于是人们把精力转向具有特殊结构的图。格子图是实际中应用最多的一类图，它 包括平面格子图、环面格子图、球面格子 图，这类图均为稀疏图，关于它们 的填充数还没有一般 的表达 式，已有的结果也针对平面格子图中阶数比较低的图。本文利用分解定理和约化准则给出扇形格子图 ． (m =1，2；／1,=1，2，3)和球面经纬图 cm．(m =1；／,／=3，4)及 (m，n)一构形等的填充数表达式。文 中未定义的术语和记号参见文献 [4]。 1 定义与引理 给定图G=(，E)，对任一子集 ScV，S的邻集记为 Ⅳ(S)={∈V＼SIyE-S使(，Y)∈E}。特别 地，顶点 ∈V的邻集记为N(v)=N({})。定义图G的一个标号为任意一个双射厂： {1，2，…，II}。 ． 在图 Go=G中进行如下的消去运算：(1)消去顶点 ，(及其关联的边)。(2)增加边 ，使邻集 Ⅳ(3／) 中的顶点两两相连，这样得到的图记为 G ，在图 G 中再消去 ，如此类推。 在运算(2)中增加的边称为 “填充边”，记这些边所成的集合为 ()。 定义 1 图G在标号厂之下的填充数为 F(G，厂)=∑IEf(v)I 图G的最小填充数为 F(G)： “ F(G，厂) j ’ 达到此最小值的标号厂，称为最优标号。 由最小填充数的定义易知，对任意图G，F(G)≥O。文献[5]给出了F(G)=0的充要条件是 G为 弦图(若 图中任意长度不小于4的圈都有弦称为弦图)，并 由此把任一图的最小填充问题转化为弦图完 备化问题。另外，对有若干个连通分支的图，其最小填充数为各分支最小填充数的和，所以可仅考虑连 通图的最小填充数-5J。图的最小填充问题没有统一的算法，但是若图具有一定的可分解结构，可以利用 作者简介：冯爱芬(1968一)，女，河南新安人，讲师，硕士 收稿 日期：2003一lO一09 。 94 。 河 南 科 技 大 学 学 报 (自然 科 学 版 ) 2004年 约化准则将图分解为结构相对简单的子图，然后再分别求其td,填充数及最优标号。问题的约化准则 一 般包括优势条件、降维原则及分解定理。 定义 2 图G的点割集SoV(G)称为完全点割集，如果导出子图G