路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

114—三次图的构造

在[1]中,只讨论了不含三角形时abc为111和222两种情况的abc—三次图,本文的目的是解决114—三次图的存在问题,并且给出一个图是114—三次图的充要条件,它类似于[1]中的定理4,但不必给予“无三角形”的限制。我们用G表示一个连通的无自环的非K_4的三次图,H表示G的一个最大二部分子图,H中的一条路如果满足(ⅰ)非平凡(ⅱ)它的端点在H中为3度(ⅲ)所有其它顶点在H中为2度,则称这样的一条路为H的一条初等路。如果G的最大二部分子图日中每个3度顶点是长度分别为a、b、c的三条初等路的公共端点,则称G为abc—三次图,若S是G的顶点集V(G)的一个子集,则K=[S,]表示G的棱集E(G)的一个子集,它的端点一个在S中,另一个在中,且称K为G的棱截。截指标c(K,H)定义为:     

Cartesian积的局部边-路替换图的L(2,1)-标号

设d为正整数,图G的一个L（d,1）-标号就是从非负整数集到V（G）的一个函数,且使得2个相邻顶点的标号相差至少是d,2个距离为2的顶点的标号相差至少为1. 图G的L（d,1）-标号的跨度就是所有L（d,1）-标号的最大值和最小值之差. 图G的L（d,1）-标号数是G的所有L（d,1）-标号下跨度的最小值. 在已有研究图G的边-路替换图的L（d,1）-标号基础上,研究了Cartesian积的局部边-路替换图的L（2,1）-标号.     

Cartesian积与邻点可区别着色之间的关系（英文）

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,Sf(x)或S(x)表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S(u)≠S(v),则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ′a(G).图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点x,使用Cg(x)或C(x)来表示顶点x的颜色(在g下)以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C(u)≠C(v),则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″a(G).主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

Cartesian积与邻点可区别着色之间的关系

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,S_f（x）或S（x）表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S（u）≠S（v）,则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ'_a（G）.图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点 x,使用C_g（x）或C（x）来表示顶点x的颜色（在g下）以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C（u）≠C（v）,则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″_a（G）.主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

图的非自中心数（英文）

许克祥等人在文献[1]中定义了新的基于离心率的图不变量,称之为图的非自中心数(简称NSC数),记为N(G).图的非自中心数定义为N(G)=∑_({v_i,v_j}V(G)|e_i-e_j|,这里ei表示顶点vi的离心率,在文献[1]中,同其他结果一起,作者确定了一些图的N(G)数的上界和下界并且刻画了达到上下界的极图.但是作者给出的极图的刻画是不完全的.基于他们得到的研究结果,在本文中我们给出了达到上下界的所有极图的完全刻画.另外,我们还给出了阶为n直径为d的树T的N(T)数的下界并且确定双圈图和含有奇数个顶点的三圈图的NSC数的上界.     

s-点连通图的路可扩性(英文)

设G是一个简单图.如果G的每一个有s个点的导出子图都连通,但存在一个s-1个点的导出子图不连通,则称G是s-点连通的,其中s≥3.一条路称为可扩的,如果存在路P′满足V(P′)V(P)且|V(P′)|=|V(P)|+1.一个图称为完全路可扩的,如果它的直径至多为2且它的每一条少于|V(G)|个顶点的路都是可扩的.本文证明了s-点连通图,如果它的顶点数n与s满足n≥2s-1,则它是完全路可扩的.     

Harary图的外连通度(英文)

一个顶点集是一个Rg-点割,如果它将一个连通图分割成一些连通分支使得每个连通分支至少含有g个顶点.图G的g-外连通度(记作κg(G))是Rg-点割的最小基数.图G的通常的点连通度和上连通度分别相应的为κ0(G)和κ1(G).本文将分别证出第一类和第二类Harary图的κg和刻画它们的Rg-点原子部分.     

Brooks定理的附注

<正> 图的顶点的染色是图论中的重要问题之一。本文从讨论图的色数的上界问题,从而得出Brooks定理的又一证明。1.基本概念如果用颜色去染一个图G的顶点,使得任意有棱相连的两个顶点均有不同的颜色。这样     

k路覆盖图的新充分条件（英文）

设G是一个n阶简单连通图。如果其顶点集V (G)能被k条或更少的点不交的路覆盖,则图G是k-路覆盖的。分别用距离谱半径、距离无符号拉普拉斯谱半径、Wiener指数和Harary指数得到了图G是k-路覆盖的新的充分条件。     

自适应memetic算法求解集合覆盖问题

集合覆盖问题是一个经典的NP困难的组合优化问题,有着广泛的应用背景.首先,采用动态罚函数法将集合覆盖问题等价转化为无约束的0-1规划问题.然后,基于集合覆盖问题的结构特征,设计了初始种群构造方法、局部搜索方法、交叉算子、动态变异算子和路径重连策略,提出了一个高效求解该0-1规划问题的自适应memetic算法.该算法有效平衡了集中搜索和多样化搜索.通过45个标准例子测试该算法,并将其结果与现有遗传算法进行了比较,表明该算法能够在可接受的时间内找到高质量的解,能够有效求解大规模集合覆盖问题.     

基于变长编码求解一维下料问题的演化算法

针对一维下料问题的特点,将线性规划方法与演化算法相结合,提出了一种基于变长编码求解一维下料问题的演化算法,该算法设计了一种新颖的遗传算子,实现简单,求解快速,实验表明,运用该法求解下料问题,材料利用率高,平均达到97．5％以上,具有很好的实用价值。     

二维Stokes问题的谱-τ逼近

文[2]在假定二维Stokes问题的谱逼近问题之解存在的条件下,给出了解的收敛估计.本文首先给出这个谱-τ逼近问题解的存在唯一性证明,然后对[2]的误差估计加以改进.     

一种网格参数化的优化算法

网格参数化是数字几何处理(Digital Geometry Processing)中的一个基本问题.作者利用Floater的具有保形权或均值权的凸线性组合参数化引入一种新的参数化的扭曲度量--点密度,以及网格上的最短切割路径来优化原来的参数化.切割路径由网格上的一内点和网格上的一边界点连接而成,内点位于参数区域上最密集区域,也是扭曲最严重的区域.具有最短切割路径的网格模型,被重新参数化成为一个具有较小扭曲的参数化.最后给出实例说明了此方法是可行和有效的,并且是优于原来的参数化的.     

基本解方法求解一个三维线弹性力学反问题

将用于求解椭圆型偏微分方程边值问题的基本解方法应用于求解一个三维线弹性反问题,即Navier方程组的Cauchy问题.基本解方法离散方程所得的线性方程组是高度病态的,常见的求解方法如最小二乘法等无法得到合理的解.文中应用Tikhonov正则化和截断奇异值分解这两种正则化方法求解线性方程组,所需正则化参数则根据L-曲线确定,克服了问题的病态性.数值算例表明,本文方法能有效地求解三维线弹性力学反问题,而且这两种正则化方法所得到的结果精度相当.     

单位圆到任意多边形区域的Schwarz Christoffel变换数值解法

Schwarz Christoffel变换技术在处理某些工程问题时具有重要作用.从黎曼存在定理出发,建立了单位圆到任意多边形区域的映射函数Schwarz Christoffel变换模型,采用Levenberg-Marquardt算法求解含约束条件的非线性映射函数Schwarz Christoffel变换模型参数系统.针对映射函数中出现的奇异积分问题,对映射函数进行2次参数变换,将其化为高斯雅克比型积分,以积分路径中的奇异点为界,缩短积分路径,对子路径采用修正高斯积分方法进行计算.通过指数变换、连乘变换和累加变换,使任意初值问题均可进行迭代计算并满足初值的约束条件.提出以边长绝对误差和顶点绝对误差为迭代计算的收敛条件,并保证了映射函数的精度.给出了11顶点多边形区域映射函数的求解算例,4种方案的计算结果表明,Schwarz Christoffel变换数值解法操作简单、精度高、收敛快.     

基于遗传算法的静态环境全局路径规划

静态环境中移动机器人全局路径规划一直是路径规划中的一个重要问题.作者提出了基于遗传算法的静态环境下机器人全局路径规划方法.该方法首先提出机器人工作空间中环境信息的神经网络模型,并利用该模型建立机器人免碰撞路径与神经网络输出的关系,然后将需规划的路径的二维编码简化成一维编码,并把免碰撞要求和最短路径要求融合成一个适应度函数.通过对算法进行实验仿真表明,提出的全局路径规划方法是正确和有效的.     

遗传程序设计中分布式染色体的一个应用

对一类遗传程序设计问题，提出了简单等长的分布式染色体，取代复杂变长的树结构染色体，使演化算子操作更方便，个体复杂度得到有效控制．用该染色体形式解决割草问题，分析了分布式染色体带来的一些性质，并给出了很好的计算结果．     

预处理的校正梯度路径信赖域算法

信赖域算法是最优化中广泛使用的一种方法．在迭代的每一步都要解信赖域子问题,在众多解子问题的方法中,校正梯度路径算法利用系统的特征值和特征向量在整个雏数空间求出子问题的解,虽然这个方法较吸引人,但现有的校正梯度路径算法不太可行,因为在每一步迭代中它要求整个特征系统的计算或者矩阵的重复分解．提出了一种预处理的校正梯度信赖域算法．该算法在一步迭代中仪通过对对称矩阵进行一次Bunch-Parlett分解就在全空间中求出子问题的解,再用单位下三角矩阵因子去标度问题的变量,预处理的校正梯度路径由此形成,算法在通常使用的条件下有好的收敛性,对各种模型的优化问题的计算结果也显示出算法的高效性．     

基于中国邮递员问题的可信平台模块测试序列生成优化研究

现今国内外已经有不少对可信平台模块进行测试的研究成果,但是对测试效率分析不足.本文基于自动机理论和中国邮递员问题,提出了可信平台模块改进的有限状态机模型与相应的优化测试方案,通过寻找一条遍历有限状态机模型中每一条转移至少一次的最短路径的方法,从而生成费用优化的测试序列.测试结果表明,测试方案能够简化有限状态机状态的测试.