直线簇上区间图的最小独立控制集

本文研究了在三种情况下直线上的区间图的最小独立控制集的计算问题:1．相交于一点的直线簇,2．除一条直线外,其余的直线都平行的直线簇,3．一条直线和直线上t个赋权的点,使得其最小独立控制集所覆盖的点的权和最大．本文给出了这三个问题的多项式时间算法,问题1可以在O(n)时间内求解,借助动态规划方法问题2和问题 3分别可以在O(n log n),O(n t)时间内求解．     

点接手镯图的L(1,1,1)-标号

图的L(1,1,1)-标号定义为顶点集V(G)到非负整数集的映射f,且当d(u,v)=1,2,3时,均有|f(u)-f(v)|≥1.不妨设0为最小标号,则称图G的所有L(1,1,1)-标号中的最大跨度f(v)的最小数为图的L(1,1,1)-标号数,记为λ(G).基本给出了点接手镯图的L(1,1,1)-标号数的确切值.     

探针区间图和STS-探针区间图的刻划

该文首先引入了探针区间序来刻划探针区间图;接着给出STS-探针区间图的探针区间完备的一种构造方法,并借此得到二部图G是相对于给定顶点划分的STS-探针区间图的一个充要条件;同时也说明了STS-探针区间图其实就是其他文献中被独立研究的凸二部图.最后基于前面给出的STS-探针区间图的刻划结果提供了两种简单的O(V E)时间的STS-探针区间图的判别算法.     

竖梯的局部替换图的L(d,1,1)-标号

图的L(d,1,1)-标号定义为顶点集V(G)到非负整数集的映射f,且当d(u,v)=1时,均有|f(u)-f(v)|≥d,当d(u,v)=2,3时,均有|f(u)-f(v)|≥1.不妨设0为最小标号,则称图G的所有L(d,1,1)-标号中的最大跨度max{f(v):v∈V(G)}的最小数为图的L(d,1,1)-标号数,记为λ_d(G).基本给出了竖梯的局部替换图的L(d,1,1)-标号数的确切值或界.     

高校应用数学学报第19卷(2004年)B辑(英文版)第2期目次和提要

二分(mg,mf) -图中的具有特殊性质的(g,f) -因子卞秋菊　刘桂真(山东大学数学系)设G是一个二分图,g和f是定义在顶点集V( G)上的两个整数值函数且g( x)≤f( x) .文中给出了二分( mg,mf) -图中含有特殊性质的( g,f) -因子的与连通度和边连通度有关的充分条件.得到了一些新结果并推广了Katerinis等人19 96年和作者2 0 0 3年的结果.单圈混合图的最大特征值范益政(南京师范大学数学系)在所有的具有n个顶点的单圈混合图中确定了如下的图:它们分别极大化和极小化图的最大特征值;同时也刻画了最大特征值等于n或者属于区间( n,n+1]的图.有界树宽图…     

无爪图上团横贯数的界

设 G=(V,E) 为简单图,图 G 的每个至少有两个顶点的极大完全子图称为 G 的一个团. 一个顶点子集 S\subseteq V 称为图 G 的团横贯集, 如果 S 与 G 的所有团都相交,即对于 G 的任意的团 C 有 S\cap{V(C)}\neq\emptyset. 图 G 的团横贯数是图 G 的最小团横贯集所含顶点的数目,记为~${\large\tau}_{C}(G)$. 证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和 Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半.     

平面图 4-割问题的 O(|V|~2)算法

给定一个简单图 G=(V,E).V 是顶点集,E■V×V 是边集.所谓 k-割乃是E 的一个子集 E_1,它使图 G_1=(V,E—E_1)恰包含 k 个分支.寻找一个图的最小 k-割问题,无论在理论上和实践中都有重要的意义.Hochbaum 和 shmoys 在文献[1]中给出了平面图最小3-割的 O(|V|~2)算法.本文将给出一个平面图最小4-割的O(|V|~2)算法.本文用到的概念及符号记法均与文献[1]一致.     

图的极大Tutte集的几个有效算法

图G=(V,E)的Tutte集定义为X■V(G)满足ω_o(G-X)一|X|=def(G).若不存在Tutte集Y■X,则称X为图G的极大Tutte集.通过找极大extreme集和D-图的极大独立集给出一般图G的找极大Tutte集的两个有效算法,并给出结论:X■V(G)是二部图G的极大Tutte集当且仅当X为二部图G的最小覆盖,从而得到找二部图G的极大Tutte集的一个有效算法.     

Halin图的线性k-点荫度

图G的线性点荫度vla(G)是指V(G)的最小划分数,使得每个点划分集的导出子图为线性森林.G的线性k-点荫度vla_k(G)是指V(G)的最小划分数,使得每个点划分集的导出子图的每个连通分支为长度至多为k的路.1998年,吴建良证明了Halin图的线性点荫度为2.本文在此基础上,证明了对Halin图G,有vla_k(G)=2,其中■     

构建最小k 重控制集的概率算法

点集D ⊆ V (G) 称为图G 的k 重控制集, 如果D 满足V (G) - D 中任意结点在D 中至少有k 个邻居. 在无线网络中, 最小k 重控制集(MkDS) 用以构建健壮的虚拟骨干网. 构建虚拟骨干网是无线网络中最基本也是最重要的问题. 在本文中, 我们提出一种快速的分布式概率算法来构建k重控制集. 我们构建的k 重控制集的期望大小不超过最优解的O(k²) 倍. 算法的运行时间复杂度为O((Δ logΔ+log log n)n),其中Δ = max{|D(p)|}, D(p) 是以p 为中心半径为1 的圆盘中的结点, 最大值的比较范围是给定集合中所有的p 点.     

关于几类图的L(2,1)标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y) ｜≥ 1 .图G的L( 2 ,1 ) 标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立     

六点七边图的λ-填充与λ-覆盖

λKv为λ重v点完全图,G为有限简单图.λKv的一个G-设计(G-填充设计,G-覆盖设计),记为(v,G,λ)-GD((v,G,λ)-PD,(v,G,λ)-CD),是指一个序偶(X,B),其中X为Kv的顶点集,B为Kv中同构于G的子图的集合,称为区组集,使得Kv中每条边恰好(至多,至少)出现在B的λ个区组中.一个填充(覆盖)设计称为最大(最小)的,如果没有其它的填充(覆盖)设计有更多(更少)的区组.本文中,我们构作了三个六点七边图的最大填充与最小覆盖.     

图的谱半径与拟悬挂点数

设G(n,k)为含有k个拟悬挂点的n阶图所构成的集合.本文刻画了在G(n,k)中无符号Laplace谱半径达到最大的图,同时给出了当k=0,1,2,3时,在G(n,k)中无符号Laplace谱半径达到最小的图.     

树的补图的区间图完全化问题

一个图G的区间图完全化问题包含两类子问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G),其中侧廓问题是寻求G的一个边数最小的区间超图;路宽问题是寻求G的一个团数最小的区间超图.这两类子问题分别在数值代数、VLSI-设计和算法图论等学科领域中有重要的应用.对一般图来说,两类子问题都是NP-完全问题;但是对一些特殊图类来说,它们在多项式时间内可解.本文给出了树T的补图的具体侧廓和路宽值.     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

T-染色和G_n~d图的T-边柞(Edge Span)

给定一个包含0的有限正整数集T,一个简单图G的一个T-染色是定义在G的顶点集V(G)上的一个非负函数f,满足对任意的uv∈E(G)有|f(u)-f(v)| T.一个T-染色f的边柞(edgespan)定义为最大的|f(x)-f(y)|,xy∈E(G),一个图G的边柞(edgespan)是G的所有T-染色中最小的边柞(edgespan).这篇文章研究了当T={0,1,2,…,k-1}时,Gdn图的T-边柞(edgespan),找到了当n≡1(modd)时Gdn图的T-边柞(edgespan)的确切值,和其他情况下的上下界.     

树的线图的图扩充问题

图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题.     

最小极差 s-子图的算法

一、前言在网络优化问题中,以往研究的问题一般是给定网络 G 和限制条件 s,求满足 s 的 G的子图(如树形图,有向路,匹配等),使该子图的权达到最大(或最小)。但有些网络优化问题不要求子图的权达到最大(或最小),而要求子图中各弧的权较为“均匀”,即要求子图中最大弧权与最小弧权之差达到最小。这就提出了最小极差 s-子图的问题。     

极大非正则图的边数（英文）

设G是一个连通图,最大度和最小度分别为△(G)和δ(G).图G的非正则指标t(G)是指G的度序列中不同值的个数.如果t(G)=△(G)一δ(G)+1,则称图G为极大非正则图.本文给出了极大非正则图和不含三角的极大非正则图边数的上界,同时给出极大非正则图边数的一个紧的下界.     

极大全控点临界图

图G的点集S如果满足:VG-S(或VG)中每个点相邻于S中的某个点(或而不是它本身),则称点集S是一个控制集(或全控制集).图G的所有控制集(或全控制集)中最小基数的控制集(或全控制集)中的点数,称为控制数(或全控数),记为γ(G)(或γt(G)).在这篇文章中我们特征化γt-临界图且满足γt(G)=n-Δ(G)的图特征,这回答了Goddard等人提出的一个问题.