一种最大化传感网络覆盖率的移动辅助部署算法

研究了使用移动传感器提高传感网络覆盖率的问题,提出了一个基于二部图匹配的移动传感器部署算法．设目标区域可以划分成多个小区域或网格,首先把初始网络描述成一个二部图G,G的顶点集合由移动节点集合和需要覆盖的网格集合组成．如果某个移动节点可以覆盖某个网格,则它们之间存在一条边．衡量移动的花费可以使用移动的距离、消耗的能量或者跳跃的次数等．对构造的二部图G求它的最小花费的最大匹配基,则该匹配基对应着一个最优的移动方案,按此方案部署的网络覆盖率最大且总的移动花费最小．     

导出子图中不含K4-e的无爪立方图的完美匹配个数

设G是一个简单图,具有顶点集合V（G）和边集合E（G）。若图G的任意导出子图都不与K1,3同构,则称G是一个无爪图。一个立方图是一个所有顶点都是三度点的图。本文给出了一类特殊图--不含K4-e的无爪立方图的完美匹配计数。 更多还原     

表象式语义网络研究

为解决形象思维及表象信息相关问题,结合语义网络以及表象式方法各自的优点,提出一种表象式语义网络知识表示方法.在语义网络中加入表象信息可以实现形象思维相关的推理.对表象式语义网络的构成要素及网络的组织进行了讨论,基于蚁群和最大最小蚁群算法提出了一种求解表象式语义网络的算法,给出了算法的实现步骤.实验结果表明,用表象式语义网络表示知识是可行的,利用该算法可以在表象式语义网络上进行推理,并能找到较为理想的解.     

几类特殊图的（2,1）-全标号

研究了与频道分配有关的1种（p,1）-全标号染色问题.（p,1）-全标号是从V（G）∪E（G）到集合{0,1,…,k}的1个映射,满足：①G的任2个相邻的顶点得到不同的整数;②G的任2个相邻的边得到不同的整数;③任1个点和与它相关联的边得到的整数至少相差p.通过在2个简单图之间叠加一系列匹配构造了几类有趣图,并根据所构造图的特征,利用穷染法得到了这些图的（2,1）-全标号数.     

一类序列树的构造

图G的标号指f是V（G）到整数集合的一个映射,然后边xy∈E（G）由f（x）,f（y）导出标号,仿照优美图中平衡标号的概念,定义图的序列平衡标号的概念,利用一类具有序列平衡标号的树构造更多顶点的序列树。     

P部图的Kirchhoff指标下界

连通图G的两个顶点i和j之间的电阻距离rij定义为通过用单位电阻来代替G中的每条边而构造出的电网络N中的节点i和j之间的有效电阻的阻值．图G的Kirchhoff指标Kf（G）定义为G中所有点对之间的电阻距离之和．得到了n阶p部图G=G（N1,N2,…,Np）（｜Ni｜=ni,i=1,2,…,p）的Kirchhoff指标下界,指出当G为完全p部图时达到下界;并进一步得到,在所有的n阶p部图中,图兰图的Kirchhoff指标最小．     

矩阵论中的图论匹配法

G.Birkhoff用代数的方法证明了如果一个矩阵是双随机矩阵,则它能表示成置换矩阵的凸线性组合.设G是具有两分类(X,Y)的二部图,则G中含有饱和X中的所有顶点的匹配M的充分必要条件为:对(A)S(∈)X,有dG(S)≥|S|.文章借助上述二部图的匹配思想,给出这一结论的图论证明.     

一类单圈图的度距离

图G=(V,E)表示顶点集为V、边集为E的所有的简单连通图的集合,研究了棒棒糖图L(n,k)的度距离,L(n,k)是将一条长为n-k的路的一个端点连接到圈Ck的一个顶点v上得到的一类特殊的单圈图。     

二部图最大权匹配的符号ADD算法

利用代数决策图ADD数据结构,在KM算法基础上,提出了一种二部图最大权匹配的符号ADD算法。该算法引入优先函数概念,将传统的匹配选择转化成布尔运算,"并行"地搜索匹配集合。实验结果表明:与传统算法相比,该算法可以改善问题的状态空间复杂度。     

基于语义连通图的场景图生成算法

提出了基于语义连通图的场景图生成算法. 将关系检测过程分为关系建议和关系推理两步; 以目标检测算法得到的候选对象为节点集合,构建一个全连接图; 使用物体的类别信息和相对空间关系计算物体之间存在关系的概率; 通过设置阈值来删除图中的无效连接,得到稀疏的语义连通图; 使用图神经网络聚合物体节点的特征进行聚合,融合上下文信息. 根据语义连通图的连接关系,结合更新后的主语和宾语特征以及两个物体联合区域的特征,构建关系特征,预测图中的每条边对应的关系类别.     

Integer Programming Model for Maximum Clique in Graph

The maximum clique or maximum independent set of graph is a classical problem in graph theory. Combined with Boolean algebra and integer programming, two integer programming models for maximum clique problem,which improve the old results were designed in this paper. Then, the programming model for maximum independent set is a corollary of the main results. These two models can be easily applied to computer algorithm and software, and suitable for graphs of any scale. Finally the models are presented as Lingo algorithms, verified and compared by several examples.     

关于乘积图的导出匹配划分数

图G的导出匹配划分数是图论中研究的热点问题.针对乘积图的导出匹配划分数进行了研究,给出了乘积图的导出匹配划分数的一个下界和一个上界,对一些特殊图类的乘积图,还给出了其导出匹配划分数的精确结果,可为相关研究参考.     

基于知识增强的图卷积神经网络的文本分类

针对文本分类问题,提出新的基于知识增强的图卷积神经网络（KEGCN）分类模型. KEGCN模型在整个文本集上构建了一个包含单词节点、文档节点、外部实体节点的文本图,不同类型节点之间使用不同的相似性计算方法;在文本图构建完成后将其输入到2层图卷积网络中学习节点的表示并进行分类. KEGCN模型引入外部知识进行构图,捕获长距离不连续的全局语义信息,是第1个将知识信息引入图卷积网络进行分类任务的工作. 在4个大规模真实数据集20NG、OHSUMED、R52、R8上进行文本分类实验,结果表明,KEGCN模型的分类准确率优于所有的基线模型. 将知识信息融入图卷积神经网络有利于学习到更精准的文本表示,提高文本分类的准确率.     

并行最小割算法及其在金融社交网络中的应用

有效实施金融监管已成为金融健康发展的必要保证. 若能够在金融社交网络中,找到一部分承载网络中所有信息流动的关键节点,便能实现整个金融社交网络的有效监管. 金融社交网络图规模通常较大,须开发大规模图处理并行算法. 本文提出基于分布式图处理平台Pregel的并行最小割算法. 实验基于Apache Spark平台开展,所用数据均来自BoardEx数据库. 实验结果表明,在大规模社交网络图的处理中,该算法具有良好性能. 利用该并行算法得到金融社交网络图的最小割,便可有效实施金融监管.     

图的边重构性的一个注记

如果图Ｇ的每个边重构图都与图Ｇ同构,则称图Ｇ是边可重构的,图的边重构猜想是指所有的至少有４条边的有限无向简单图都是边可重构的,它是至今尚未解决的著名的图论问题之一,文章主要通过定义特殊函数的方法来研究图的边重构性问题,并给出仅以图的最大顶点次数和最小顶点次数作为参数的简单充分条件。     

一类单圈图的度基尔霍夫指数

设G是简单连通图,顶点集为V（G）.图G的度基尔霍夫指数定义为图G中所有顶点对的度与顶点之间的电阻距离乘积的和.棒棒糖图Ln,k是路Pn-k的一个端点连接到圈Ck的一个顶点得到的一类特殊的单圈图.给出首先给出Ln,k的度基尔霍夫指数计算公式,然后刻画了相应的极图.