图的最小填充的分解定理.pdfVIP

第 8卷 第 l期 1994 6月 虚 崩 数学 与 计算 数学 学 报 COM M ．ON APPL．M ATH．AND COMPUT Vo1．8 N0．1 jtlt．．1994 弓7厂一％ 图的最小填充的分解定理 塑 。苎望 ， (=)／ 、 —————～ 一 一，一，、 ／ (郑州大学数学摹·拜州·45∞驰) ’ - 摘耍 在计算数学镘域，稀疏矩炸的最小填充捧序 问题 由于其 藏耍的 z 理一些特殊结构·从而导出一些特殊罔的最小填充数’ } 俎 ． 号 囤， 板 绠元 ———～ 商 J ’1 弓l 言 一 ， 在许多数学分支如数值分析、敷学规划、敷理统计、工程计算、以及计算机辅助设计中 经常要处理一个稀疏的对称方阵的线性方程组 z?=b的术解阃题．在运J_fIGau亏s消去法或 cholesky分解法的过程中，为了保持矩阵的稀疏灶以减少计算量，在消去或分解过程中要求 确定矩阵的消元顺序使填充的非零元尽可能少．此u 便可考虑一个相应的筒 图的最小填充 问题1 ．设对应于矩阵A的筒 图为G=( E】，其中顶点集V：{ ． ． }对应于矩 阵A的n个行(列}，边禁E={ ，咭l ，≠0}对应于矩阵A的所有非零元，则 程组 0?=6 的消去或分解过程l相当于如下图G的消去运算． 给定一个茼 图G =( 研 JV J= ．顶点 ∈ 的邻集记为Ⅳ( }： {u∈Vlu≠ 口，(“， )∈E) 任一 射，：V一 {1，2，?，n)称为图G的一个顶点标号， =， ( ) = l 2． n)便是图0 的一个顶点顺序．在图Go= 中进行如下消去诞葬：(1l漕丧埙点 (及其关联边)j(2J增加边 使其邻集Ⅳ(u )中的顶点蹦_蚺楣邻．这样得到的囹记为G ．在 G 中再消去顶点u。，如此类推．其中第(2J步消击顶点 u 使其邻柴 r? l中顶点l婀l随相 邻所增加的边称为填允边，记这些边所成的集合为 】．对标母，及， 述消去运算，定义 为图0在标号，下的填充数；并称 F(G，)=∑I ( ) F(G)=n nF(C，n 为图G的最小填充数．使F(G)：F(G ，)的标号，称为最优标母．于是求使填允非零元 可能少的矩阵A昀消元顺序相当于求^对应图的最优标号．这个问题已被证明是NP一 完 全问题 因而人们的_丰要兴趣便转化为研究某些特殊图的最小填允数问题l1】并希望得到 本文 1993 6月4日收 甜 维普资讯 应 州 数 学 与计 算 数 学 学报 8卷 有普遍意义的方法．本文第2节讨论图的最小填充问题的基本性质；第3节给H 5最小填充的 分解定理；第4节应用分解定理得到一些特殊图的最小填充数结粜． 2．基本性质 在算法复杂性研究方丽，一般图的最小填充问题于1981年已被证明是NP一完仝问题 I 摄近原晋江等 把这方面的研究推进了一步，证明了当图G为偶图及平方图时该问题仍然 是NP 完仝问题 山此可见图的最小填充问题不大可能有统一的多项式ut问算法。 山最小填充数fIg定义易知对任意图G，F(G】 0．文献? 给 1了F(GJ：0的图G的充 要条件是G为弦圈(参见{1j引理2．2】．并山此把任一图的最小填充问题转化为弦图完嵛化问 题l』l即对任意图G 最小填充数F(G】就是使G成为弦图的最小添加边数： F(G)=min(iE(H—G)l_G 日，H是弦图) {参见? 定理2 3)．此外山最小填充数的定义易知对有若干个连通分支的图其最小填充数为 各分支最小填充数的和-山此，我们只考虑连通圈的最小填充数．对于 一 连通图文【l】给 dI了一个较紧的下界： 引理2．1 若G足 连通的，IV(G)I：n，则 ，{G)+IE(O)I≥ (2n一 一1) ‘ (参见l 1l定理2．5) 对于消去一点后的图的强小填充数有如下结粜： 引理2 2 设G是2一连通的，v∈ (G)，d(u)=2，Ⅳ(v】=扛 }J则 fG)：{F(G—v】， 若 )∈F(G1 【{：一 十xyj+1，若( ， 车 (G)． 0参见【5】定理l_1)． 引理2 3 若G H 则 ● ． F(G)+IE(C】i≤F{H)+】E(H) ． 其次，对任意给定图G：(V， )，】Vf=n．山定义易得最优标号的如下基水性质： 引理2．4 若，为G的最优标号 其中，-1{i)= 0=1，2，． n)．则山，诱导的图G，一l 的标号 ?其中 【?vi】=，一i+l ： ． +1， n) 为图G，一 的最优标号 引理2 5 若，为G的最优标号，则将山，诱导的图G —l的标号^替换为G。一i的另一 个最优标号 ，这样得到的标号， 仍为图G的最优标号． 严棒地说， 述标号， 的构造为： 厂 】={ ㈣ 一 引理2·G 设 =“ “：．一．uk} 为