On (g, f)-Uniform Graphs

A graph G is called a (g, f)-uniform graph if for each edge of G, there is a(g, f)-factor containing it and another (g, f)-factor excluding it. In this paper a necessary andsufficient condition for a graph to be a (g, f)-uniform graph is given and some applications of thiscondition are discussed. In particular, some simple sufficient conditions for a graph to be an [a,b]-uniform graph are obtained for a b.

齿轮图及其一致膨胀图的PI指数

齿轮图就是在轮图的轮圈上每相邻两点之间均添加一个顶点后得到的图,由于齿轮图有很好的对称性,所以将其边进行分类,计算出齿轮图的PI指数。齿轮图的一致膨胀图就是将它的每个顶点都替换成阶相等的完全图,通过与齿轮图类比,计算其一致膨胀图的PI指数,为研究一些特殊图形的PI指数问题提供了线索。

基于UniformLBP特征的镜头检测算法

首次将Uniform LBP特征引入镜头检测中,提出一种有效的镜头检测算法。算法的主要思想是:以Uniform LBP特征作为描述视觉信息的主要特征,利用图模型计算图像序列的特征差异信号,采用主动处理策略构造特征向量和选择训练数据,通过SVM分类器识别视频镜头。提出的算法以Trec Vid05实验数据为测试平台,通过与Trec Vid05的测试结果比较可以证明该算法不但对切变镜头检测有很好的实验结果,而且能更为有效地检测渐变镜头。

基于对齐性和均匀性约束的图神经网络会话推荐方法

会话推荐(session-based recommendation,SBR)旨在匿名状态下通过用户的短期历史行为序列来预测下一个待点击的项目。为解决现有基于图神经网络(graph neural networks,GNNs)的会话推荐方法忽略会话中不同位置相同项目之间差异的问题,在图卷积获得项目表示后,进一步考虑该项目与相邻项目之间的相关性,生成邻域相关的项目表示。此外,鉴于对齐性和均匀性在对比学习中的起到的重要作用,还提出了一种适用于会话推荐的对齐性和均匀性损失方法,以约束生成的会话表示和项目表示。在3个公开数据集上的实验表明,文中提出的模型TAU-GNN的推荐性能优于对比的主流会话推荐模型。

基于泰森图大规模MMTSP问题的高效求解

针对大规模MMTSP问题任务划分不均匀与计算效率低的问题,本文提出了基于泰森图的高效基本计算框架。首先基于离散点上下凸包算法快速构造泰森图;然后基于高端点去除法快速完成MMTSP问题的任务划分;最后结合模拟退火算法求解单旅行商问题,完成大规模MMTSP问题的高效求解。为进一步提升计算效率,对该框架中的部分环节基于GPU的众核算力,提出了GPU并行加速计算时任务的划分设计,结合软件层面提出了软硬件协同加速计算框架。试验证明,本文算法在加速优化与任务划分均衡性上具备较大优势,其计算结果与计算效率均优于其他两类算法,软硬件协同加速优化后,可进一步提高约10倍的效率。

一种非均匀图滤波器组的设计方法

针对图频率分布不均匀的情况,提出一种非均匀图滤波器组的设计方法。根据图频率的分布特性,设计了具备良好频率选择特性及顶点域局部特性的非均匀分析滤波器。先用低阶非多项式滤波器近似高阶多项式滤波器,再在给定分析滤波器和子带信号的前提下,将重构问题归结成一个最小二乘问题。由于直接求解优化问题会涉及矩阵求逆,为了解决在大规模图的情况下计算复杂度高的问题,采用一种预处理梯度法对优化问题进行迭代求解,且能分布式实现。仿真结果表明,通过该方法设计的非均匀图滤波器组能实现完全重构,且其分析滤波器具备良好频率选择特性及顶点域局部特性。与其他迭代方法相比,该方法具有较快的收敛速度和较低的计算成本。

基于NUMA延迟发送的时变图弱连通分量求解

时变图连通分量已经被广泛应用到不同场景,如交通路网建设、推荐系统的信息推送等.然而当前多数连通分量求解方法忽视了NUMA体系结构对计算效率产生的影响,即过高的远程内存访问延迟导致低下的算法执行效率.本文针对时变图的弱连通分量求解问题,提出一种基于NUMA延迟发送的时变图弱连通分量求解方法,它通过合理的数据内存布局,合理控制NUMA节点间的信息交换次数,最大限度减少远程内存访问数量,显著提高了算法执行效率.实验结果表明,该方法的性能明显优于当前流行的图处理系统Ligra和Polymer提供的方法.

消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g<f条件下

邻域并与[a,b]-k-对等图

设G是一个n阶图,1≤a<b及b≥k≥0是整数,本文证明了若n≥2(a+b)(a+bb-1)+2k,图G的最小度δ(G)≥a+k,且NG(x)∪NG(y)≥ana++2bk,则G是[a,b]-k-对等图,推广了已有的结果。

有约束条件的r-正则图的k-对等性质

即是k-覆盖又是k-消去的图称为k-对等图.本文研究了有约束条件的r-正则图和k-对等图之间的关系,给出了有约束条件的r-正则图是k-对等图的关于顶点数和边连通度的充分条件.

有1-因子的图和(g,f)-对等图

既是(g,f)-覆盖又是(g,f)-消去的图称为(g,f)-对等图.给出了有1-因子F的图是(g,f)-对等图、f-对等图的关于F的分支的若干充分条件,证明了如下定理:设G是一个图,F为G的1-因子,w(F)≥2且w(F)≡0(mod 2);g和f是定义在V(G)上的整数值函数并且对每个x∈V(G)都有g(x)≤f(x).若对F的每个分支C=xy,G-{x,y}是(g,f)-对等图,则G也是(g,f)-对等图.并指出定理中的条件在一定意义上是最好可能的.

关于(g,f)-对等图

提出对等图的概念，给出一个图是对等图的充要条件．

[a,b]-对等图的范-型条件

既是[a,b]-覆盖又是[a,b]-消去的图称为[a,b]-对等图.设1≤a<b为整数,G是阶为n的图,其中n相对于a,b充分大.若δ(G)≥a+1且对G中每一对满足d(x,y)=2的顶点x,y,都有max{degG(x),degG(y)}>an+1a+b,则G为[a,b]-对等图.给出了一个图是[a,b]-对等图的关于范-型条件及邻域并的若干充分条件,并指出定理中的条件在一定意义上是最好可能的.

函数一致连续证明方法研究

针对函数一致连续证明问题,给出了证明方法的流程图,该流程图对函数一致连续性证明给出了一个清晰的思路,通过例题解释流程图使用方法。事实表明该流程图对函数一致连续证明是有效的。

钢铁企业均衡用氧评价模型研究

分析了氧气使用的均衡程度,定义了用氧均衡度和用氧均衡状况图的概念,建立了企业氧气系统均衡用氧评价模型。理论分析和实例计算表明,用氧均衡状况图和用氧均衡度全面地反映了用氧均衡情况。利用均衡用氧评价模型及其软件可以快速地计算用氧均衡度指标,方便地画出用氧均衡状况图,为氧气发生系统和氧气用户的决策者提供满足氧气生产和使用要求的分析方法和计算方法。

基于XML的实时数据一致性描述与查询处理

实时数据查询技术在工业企业信息平台中具有广泛的用途,XML数据标准能够实现各子系统数据的统一描述。该文用成熟的关系数据库查询机制处理符合DTD的XML文档,提出了一整套数据模型、转换规则、算法描述,可以将XML文档转换为关系元组,从而达到用XML实现基于关系数据库的实时数据一致性描述和查询处理的目的。

电阻抗层析成像系统“软场”非线性特性——基于统计的方法

基于图方法与均匀设计方法,分析了电阻抗层析成像系统中的非线性特性．定义了非线性度,研究了圆域内两子区域的参数变化,采用正态图及半正态图方法分析了5因子2水平的情形,采用8因子6水平进行均匀设计,“最坏”情形的非线性度为-93．265％,并采用基于灵敏度矩阵的双共轭梯度法进行图像重建．结果表明,由于灵敏度矩阵法将各区域的电导率变化与测量电压变化存在的非线性关系线性化,忽略了EIT系统中由于“软场”性质引起的耦合效应,导致图像质量降低及迭代次数不确定;由于不同子区域间的耦合效应,尽管控制迭代次数可实现部分补偿,但基于灵敏度定理的迭代重建算法仍有其局限性,难于重建精确图像．

r-正则图的边连通度和k-对等性质

既是k-覆盖又是k-消去的图称为k-对等图.给出了边连通度为λ的r-正则图是k-对等图的若干充分条件,得到了如下结论:设r,k,λ均为正整数,G是边连通度为λ的r-正则图,λ≥2且|V(G)|为偶数.若r/λ≤k≤r-r/λ,则G是k-对等图.设r为奇数,k为偶数,G是边连通度为λ(G)=λ≥2的r-正则图,λ*=2[λ/2]+1.若2≤k≤r-r/λ*,则G为k-对等图.

(g,f)-k-对等图的若干充分条件

若对图G的任何k条边,G有一个(g,f)-因子含它并且有另一个(g,f)-因子不含它,则称图G是(g,f)-k-对等图。本文证明了以下结论:设0<r≤1,k≥1,若对每个x∈V(G)有g(x)≤rdG(x)-k≤f(x)-k,则图G是(g,f)-k-对等图。

结构-属性平衡图节点相似度测量算法

节点相似度是图聚类算法的重要基础,在基于结构-属性图聚类现有方法中,由于传统图模型的限制,需要多次矩阵相乘来调整属性边的权值,算法执行效率低。为解决这一问题,提出了结构-属性平衡图的概念,并采用随机游走模型策略统一度量结构-属性平衡图GB中顶点间的相似度。与现有方法相比,该方法不但能测量直接相连的顶点之间的相似度,还可测量不直接相连而存在不同长度的路径的顶点之间的相似度,且没有增加原相似度矩阵的规模,节省了大量存储空间,提高了算法执行效率。