两类特殊图的最小填充数

在计算机教学领域,稀疏矩阵的最小填充问题由于其重要的实际意义而受重视.本文从图论的观点提出一种处理方法,即利用图的分解约化定理给出了铅笔图和蜘蛛图的填充数表达式,从而为确定这引起图类的填充奠定了基础,并提出进一步研究的建议.     

图的填充

给出了分解定理的一个新的证明方法,同时给出了填充数上界的一个新的表达形式.     

一类特殊图的最优填充

本文运用图的最优填充的分解定理和局部最优充定理，研究图Ｇ＊Ｔ的最小填充数和最优消去顺序，其中Ｇ为几乎完全图，Ｔ为树。     

几类特殊图的最优填充

图的最优填充在稀疏矩阵计算中有重要的作用。利用图的分解定理和约化准则给出了扇形格子图Fm,n(m=1,2;n=1,2,3)和球面经纬图Gm,n(m=1;n=3,4)及(m,n)-构形等的填充数表达式,从而为确定这些图类的填充奠定了基础,并提出进一步研究的建议。     

几类图的最优填充数

运用图的最优填充分解定理和局部最优填充定理,将一些特殊图类G1×G2,S(G),R(G)和双圈图分解为一些可求得最小填充数的图,得到如下结果:(1)F(Pm×Pn)≤(m-2)(n-2),其中m≥2,n≥2;(2)若G是有m条边的n阶2-连通图,则F(S(G))=m F(G);(3)设图G为双圈图,两个诱导圈的圈长分别为p和q,t为这两个圈公共部分的路上的顶点个数(不包括两个端点),则F(G)=p q-t-6.     

几类7点7边图的图设计与最优填充

设λKv是λ重ν点完全图,G是无孤立点的有限简单图。将G－设计（G－填充）记作（ν,G,λ）－GD（（ν,G,λ）－PD）是指一个序偶（X,B）,其中X是完全图Kν的顶点集,B是Kν中间构于G的子图（区组）的集合,使得Kν中每条边恰好（至多）出现在B的λ个区组中。讨论了3类7点7边图Gi(i=1,2,3)的图设计及最优填充问题,并给出了（ν,Gi,1)-GD及（ν,Gi,1)-OPD(i=1,2,3)存在的谱。     

几种特殊图的填充数

应用图的最优填充分解定理和局部最优填充定理,得到了书本图Bm、方型网图F(m;n)(m=1,2,3)和蛛网图W(m,n)(m=1;n=3)的填充数表达式分别为:F(Bm)=m,F(F(1;n))=n,F(F(2;n))=4n-3,F(F(3;n))=({]3,n=1,9,n=2,14,n=3.)F(W(1,n))=n-3,F(W(m,3))=3(m-1).     

两个图的联的最小填充数

本文研究了两个图G和H的联图G∨H的最小填充数，并得到了F（G∨H）关于F（G）和F（H)表达式。     

几类4-正则平面图的最小折数纵横扩张

主要讨论了4类4-正则图的最小折数纵横扩张,对任意阶这样的的4-正则图都给出了它的一个最小折数纵横扩张,并给出了最小折数与阶数之间的关系.     

两类特殊图的最优填充

运用图的最优填充分解定理,将强乘积图 P3×Pn,P2×Pn与乘积图P2×P2n进行分解,得到了它们的最优填充数.     

与网络问题有关的一些极图

本文研究与网络题有关的一些极图,得出的主要结果有:五个关于没有三角形的极大图的定理,以及它们的三个推论。     

几类特殊的M2-等可覆盖图

若图G的每个极小H-覆盖都是它的最小H-覆盖,则称图G为H-等可覆盖的．得出了M2-等可覆盖图的必要条件,并刻画了以下几类特殊M2-等可覆盖图的特征：匹配、路、圈、完全图、完全二部图、轮图和扇图．     

最小度与[a,b]-k-对等图

设G=(V(G),E(G))是一个n阶图,1≤an+(a+b)-2■bn-2k+1,则G是[a,b]-k-对等图。推广了已有的结果。     

几种特殊图的均匀边染色

研究立方Halin图以及一些倍图的均匀边染色,利用换色法、构造法和归纳法得出：立方Halin图和路的倍图都是均匀的,星的倍图都有均匀4-边染色．     

一些特殊图的树宽

通过树宽的分解定理,得到有关Dn,4演化的蜘蛛图,花蕊图的树宽表达式,以及三合图和四合图的树宽表达式．     

某些不含5-圈的图的线性2-荫度

线性森林是所有分支都为路的图,图G的线性荫度la(G)也就是把图的边集分解为互不相交的线性森林的最少数量k.本文对将要讨论的不含5-圈的平面图做一些限制,这些图不含3-面与3-面相邻、4-面与4-面共用一条边的情况.设G为不含5-圈的如上述所示的平面图,则la2(G)≤(Δ(G)+1/2)+5.