Hamilton临界图C_(m,n)的派生图类C′_(m,n)的简单性质

Hamilton临界图Cm,n是一个重要图类,当其中的某些参数、边的关联方式或边的数量等发生变化时,将产生一个新的有趣图类C′m,n(称为Cm,n的派生图类),通过对图类C′m,n的Hamilton性的讨论,得出了图类C′m,n存在Hamilton圈的充要条件.

BSCC(4,k)的Hamilton圈分解

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络。2010年师海忠提出了如下猜想:冒泡排序连通圈网络BSCC(n)(n≥4)可分解为边不交的Hamilton圈和完美对集的并。记BSCC(n)为BSCC(n,0),对BSCC(n,0)的每个顶点用一个三角形代替,得到新网络BSCC(n,1),对BSCC(n,1)的每个顶点用三角形代替得到BSCC(n,2),类似迭代k次得新网络BSCC(n,k)。师海忠进一步提出猜想2:BSCC(n,k)可分解为边不交的一个Hamilton圈和一个完美对集的并。证明了BSCC(4,k)可分解成边不交的一个Hamilton圈和一个完美对集的并。

基于最优加权图匹配的服务功能链部署方法

服务功能链技术通过对虚拟网络功能的编排来支持灵活的网络服务请求。针对资源有限网络中的服务功能链部署问题,提出了一种基于最优加权图匹配的服务功能链部署方法,把服务功能链组合为功能拓扑图,利用邻接矩阵特征向量分解算法获取功能拓扑与物理拓扑的加权图匹配方式,并通过爬山算法对匹配结果进一步优化。仿真结果表明,所提方法在降低服务功能链部署所需带宽的同时,优化了节点负载和链路带宽的均衡度,可以支持更多的服务请求,且复杂度低,具有较高的时效性。

赋权图中的路和圈(英文)

本文研究了赋权图中的最长路和最长圈,将关于非赋权图中最长路和最长圈的一些结果推广到赋权图上.

关于旅行推销员问题的一个算法

通过圈上结点下标自足方法 ,给出了一个关于旅行推销员问题的算法 .尽管该算法实质上无法改变问题的 NP-完全性的难度 ,但较分支定界法的执行速度快 。

λ阶短哈密顿回路的最小权法

提出短哈密顿回路的概念,分析由延长而形成最短哈密顿回路的特点,得出求权图G(n,m)λ阶短哈密顿回路的最小权法.该最小权法不但可精确求得最短和其它阶的短哈密顿回路,而且可用于权图G(n,m)的判别,得出求λ阶短路径的最小权法.

赋权图中最重的最长v-路与赋权周长

对 2 -连通非Hamilton赋权图G ,本文证明 :若P(u ,v)是G中最重的最长路 ,则G的赋权周长cw(G)≥dw(u) +dw(v) ;假设G满足文中描述的额外条件C1 、C2 ,则max{dw(x) ,dw(y) |d(x ,y) =2 }≥m/ 2时 ,对每个顶点v ,G含最重最长υ -路P(u ,v)使dw(u)≥m/ 2 ,而dw(x) +dw( y) +dw(z)≥m(当d(x ,y ,z) =2 )时 ,cw(G)≥ 2m/ 3.改进了非赋权图的周长及赋权图的赋权周长的若干已有结果 .

λ阶短哈密顿回路的匹配法

无向权图G(n,m)的任始结点哈密顿回路可分成两条匹配半路径,根据给定λ值,用最小权路径延长法,对所有相关半路径进行匹配,便可完全确定从最短到λ阶短哈密顿回路的匹配法和相应的匹配算法.λ阶短哈密顿回路的匹配法可用于判别权图G(n,m)是否为哈密顿图.

赋权图过指定点的圈

设G是满足条件D1和D2的2-连通非Hamilton赋权图,证明了如下新结果:若G满足dw(x)+dw(y)≥m(xy E(G),x≠y),则通过图G的每个顶点存在权重大于或等于m的圈.该结果推广了非赋权图的已有结果.

限制度的IC平面图中轻弦4-圈的权和

删去完全图k 4任意一条边所得的图称为弦4-圈.利用权转移方法讨论限制度的IC-平面图中轻弦4-圈的权和,证明每个最小度至少为5且最小边度至少为11的IC-平面图含有一个轻弦4-圈v 1v 2v 3v 4v 1,并证明具有该类限制度的IC-平面图中轻弦4-圈权和的上界小于等于37.

赋权图中的重路与重圈

给出了2 通非Hamilton赋权图中关于重路与重圈的2个新结果,推广了非赋权图的相关结果。

赋权图中的圈

对2-连通赋权图G,本文证明了如下新结果:若G满足对任意独立集S={u,v,w},存在x≠y∈S,使得dw(x)+dw(y)≥m,则图G或者包含Hamilton圈或者含权重≥m的圈,它推广了非赋权图及赋权图的相关已有结果。

面的并区域与三正则图的Ham ilton圈

Sachs. Kozyrev和 Grinbery指出了平面图具有 Hamilton圈的一个必要条件是 ∑ni=3 ( i-2 )i=∑ni=3 ( i-2 ) ′i=n-2 ,其中 i 和 ′i 分别为 Hamilton圈内 ,外度为 i的面数 ,在这个必要条件的基础上 ,给出了三正则平面图

关于冒泡排序连通圈网络猜想的一个注记

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络,它是3正则的.2010年师海忠提出了如下猜想:冒泡排序连通圈BSCC(n)(n≥4)可分解为边不交的一个Hamilton圈和一个完美对集的并.在本文中证明了当nn==5,4时猜想成立,另外,给出了BSCC(6)的一个圈分解.

有关完全图的算法及实现技术

讨论了求解极大完全子图算法的形式化．

基于图的航空图像与GIS模型匹配算法

地理信息系统(GIS)采用语义描述,图像中缺少颜色及灰度信息,只能基于其结构特征进行匹配。受目前图像处理技术限制,从图像中提取的特征信息量少、精度受限、且往往含有噪声。针对上述问题,提出一种基于图的航空图像与GIS模型匹配算法。基于UWG-SA方法分别对GIS与实时图像特征自动构建图,根据设定的相容函数,采用分级指派方法计算图的全局相容度,并给出主方向方法去除误匹配,求解变换参数。实验结果表明,该算法匹配概率为98.5%,平均匹配误差为8.54 m,平均耗时为0.075 s,可满足飞行器导航需求。

无向图在计算机绘图中的应用

本文把笔式绘图仪绘图过程时间最少的调度问题转换为在加权无向图中求解最优H-回路,并且利用最小生成树、欧拉回路、非二部图赋权匹配的算法给出了一种近似调度算法,旨在减少绘图仪移动空走时间和换笔时间,从而提高绘图效率。本算法经RP-MF160等绘图仪应用,效率提高约15%。

一些极值图问题的谱条件综述

这篇综述分为两个方面.首先,我们总结了图论中的Turan型问题的谱极值结论的最新进展.更准确地说,关于各种图的邻接谱半径和无符号拉普拉斯谱半径,我们总结了它们的谱版本的Turán型函数.例如,完全图、色数至少为3的一般图、完全二部图、奇圈、偶圈、色临界图和相交三角形图.第二个目标是总结一些最近的关于图性质的谱条件.通过一种统一的方法,基于邻接谱半径和无符号拉普拉斯谱半径,我们给出了一些充分条件,使得该图成为哈密顿图、k-哈密顿图、k-边哈密顿图、可迹图、k-路径可覆盖图、k-连通图、k-边连通图、哈密顿连通图、完美匹配图和β-亏量图.