传输子网选择:度数有界最大支撑子图逼近

研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d。这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图。就输入图的边是否带权,分别设计了多项式时间近似算法。当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图。算法输出的度数有界支撑子图可以用作无线网状网络的传输子网。

几乎三角剖分图中的2-连通支撑子图

证明了每一个无可分离三角形的几乎三角剖分图均存在一个２－连通支撑子图，其最大度至多３．并且，这一结果是最佳可能的。

有向网络中强连通支撑子图扩容问题

针对有向网络中的强连通支撑子图弧扩容问题,提出了 GSCSCE模型.首先研究不受限制的两种特殊情况:最少弧强连通支撑子图扩容问题(MNSCSCE)和最小费用强连通支撑子图扩容问题(MCSCSCE),并把它们的模型转化为赋权形式的强连通支撑子图问题,分别给出了 2-近似算法,时间复杂性均为O(mn).最后讨论受限制问题的特殊情况:最少弧受限强连通支撑子图扩容问题(NCSCSS),用支撑树形图的简单变换给出了一个2-近似算法,时间复杂性为O(mn).

关于图的(g,f)-因子分解

设G是一个图，g和f是定义在图G的顶点集V（G）上的两个非负整数值函数且g＜f．图G的一个（g，f）-因子是G的一个支撑子图F，使对所有的x∈V（G）有g（x）≤dF（x）≤f（x）．若G本身是一个（g，f）-因子，则称G是一个（g，f）-图．若G的边能分解成一些边不交的（g，f）-因子，则称G是（g，f）-因子可分解的．本文给出图G是(g，f)-因子可分解的一个充分条件．

图中具有某种性质的子图

设ｇ 和ｆ 是定义在图 Ｇ的顶点集合 Ｖ（ Ｇ）上的整数值函数且对每个ｘ ∈ Ｖ（ Ｇ）都有０≤ｇ（ｘ）≤ｆ（ｘ）且ｇ（ｘ）和ｆ（ｘ）为偶数．本文证明了：若 Ｇ是一个（ｍ ｇ＋ ｋ－ １，ｍｆ－ ｋ＋ １）图，１≤ｋ≤ｍ ， Ｈ 是 Ｇ中一个给定的有ｋ 条边的子图，则 Ｇ存在一个子图 Ｒ使得 Ｒ有一个（ｇ，ｆ）因子分解与 Ｈ

(4d+1)-正则图中的2d-因子

设d是一个正整数 ,G是一个 (4d +1 ) -正则图 .证明了若图G不含d +4条割边 ,则G有2d 因子 .进而说明上述结果是最好的 .

与任意图(m,r)-正交的(g,f)-因子分解

设g和f是定义在图G的顶点集合V(G)上的两个整数值函数.本文证明了如下结果:设r是一个正整数,G是一个(mg+1,mf-(m-1)r)图,1≤r≤m-1,若对每个x∈V(G)均有g(x)≥2r-1,H是G的有mr条边的子图,则G有(g,f)因子分解与H(m,r)正交.

与任意图(m,r)-正交的(g,f)-因子分解

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g(x)和f(x)是定义在V(G)上的两个整数值函数,且对每个x∈V(G),有52r-1≤g(x)≤f(x),则图G的一个支撑子图F称为G的一个(g,f)-因子,如果对每个x∈V(G),有g(x)≤dF(x)≤f(x).图G的(g,f)-因子分解是指E(G)能划分成边不交的(g,f)-因子,设F={F1,F2,…,Fm}和H分别是图G的因子分解和子图,若对所有1≤i≤m有|E(H)∩E(Fi)|=r,则称F和H(m,r)-正交.本文证明:若G是一个(mg+m-1,mf-m+1)-图,H是G中任一有mr条边的子图,则G有一个(g,f)-因子分解与H(m,r)-正交.

完全偶图的[1,2]因子计数

讨论了完全偶图存在 [1,2 ]因子的充分必要条件 ,并给出了 [1,2

2-连通图的单圈子图

证明了如下结果:(1)一个2-连通图G的Θ-图是2(ρ-1)连通的;(2)如果一个2-连通图G有两个单圈支撑子图,且这两个单圈支撑子图分别含m和n个悬挂点(m<n),则图G至少有2(ρ-1)个含k个悬挂点的单圈支撑子图,这里m≤k≤n,ρ=|E(G)|-|V(G)|+1.

关于图（g，f）－因子的一个注记

设Ｇ是一个图，ｇ，ｆ是定义在图Ｇ的顶点集上的两个非负整数值函数，且ｇ≤ｆ．图Ｇ的一个（ｇ，ｆ）－因子是Ｇ的一个支撑子图Ｆ，使对任意的ｘ∈Ｖ（Ｆ）有ｇ（ｘ）≤ｄＦ（ｘ）≤ｆ（ｘ）．本文给出了一个图是（ｇ，ｆ）－可因子化的充分条件．

完全偶图的PCS-因子计数

图G的一个PCS-因子是G的一个支撑子图,其中每一个连通分支是路,圈或顶点数大于等于4的星.本文研究完全偶图Km,n的PCS-因子计数,给出了Km,n存在由k个分支构成的PCS-因子的充要条件,以及Km,n的PCS-因子的计数公式.

图的连通支撑分解

设G是一个简单连通图,若{G_1,G_2,…,G_R}是图G的一组支撑子图,且满足:(1)G_i是连通图,i=1,2,…,R;(2) 对任何1≤i≠j≤R,有E(G_i)∩E(G_j)=φ;(3)∪E(G_i) from i=1 to R=E(G);(4) R是满足上述条件的最大正整数,则称{G_1,G_2,…,G_R}为图G的一个连通支撑分解,并记R(G)=R,称它为图G的分解度。本文证明:R(K_n)=[n/2]和R(K_(m,n))=[nm/(n+m-1)],并且给出求子图的算法。

图的(g,t)-因子分解

§1.定义和记号 本文中所考虑的图是可以有重边际没有环的图,G是一个图,g,f是定义在V(G)上的整数值函数,对∈V(G),满足g(x)≤f(x),H是G的一个支撑子图且满足g(x)≤d_H(x)≤f(x),∈V(G),则称H是G的一个(g,f)一因子。

关于k-消去图的若干新结果

设G是一个图．k是自然数．图G的一个k-正则支撑子图称为G的一个k-因子．若对于G的每条边e．G—e都存在一个k-因子，则称G是一个k-消去图．该文得到了一个图是k-消去图的若干充分条件，推广了文［2—4］中有关结论．

树的奇因子

树的奇因子马润年１高安喜２（１空军电讯工程学院数学教研室，西安７１００７７；２陕西财经学院管理系，西安７１００６１；第一作者，男，３２岁，讲师）设Ｔ为一树，用Ｖ（Ｔ）和Ｅ（Ｔ）分别表示Ｔ的顶点集和边集，任给ｘ∈Ｖ（Ｔ），用ｄＴ（ｘ）表示ｘ在Ｔ中的顶点...

关于k-覆盖图的一些新结果

本文给出了一个图G是k-覆盖图的若干充分条件．

二分图为k-消去图的 2个条件(英文)

图G的一个k 正则支撑子图称为G的k 因子 .若对G的任一边e ,图G总存在一个k 因子不含e ,则称G是k 消去图 .若图G存在一个划分 (X ,Y)使得G的每条边的端点分别在X和Y中 ,则称G =(X ,Y)为二分图 .证明了二分图G =(X ,Y)且X =Y是k 消去图的充分必要条件是kS≤r1+2r2 +… +k(rk+… +rΔ) -ε(S)对所有S X成立 .并由此给出二分图是k 消去图的一个邻集充分条件 .

k-消去图的邻集和最小度

研究了为保证一个图G是k-消去图,G所具有的独立集邻集的基数和最小度。

关于消去图的一个充分条件

设G是一个图,用V(G)和E(G)表示顶点集和边集,并设g和f是定义在V(G)上的两个非负整数值函数,且g<f。图G的一个(g,f)-因子是G的一个支撑子图F,使对任意的x∈V(G)有g(x)≤dF(x)≤f(x)。如果去掉图G的任何三条边都有一个(g,f)-因子,则称图G是一个(g,f)-3-消去图,本文给出了一个图是(g,f)-3-消去图的一个充分条件。