The Path-Positive Property on the Products of Graphs

本文所讨论的积图是图的笛卡尔积，图的张量积，图的逻辑积和图的强直积四种积图．证明了：①如果Ｇ１和Ｇ２都是连通图，则积图中笛卡尔积，逻辑积和强直积都是道路正图．②图的张量积是道路正图的是图Ｇ１和Ｇ２是一个连通图，Ｇ１［或Ｇ２］有一个奇圈，且ｍａｘ｛λ１μ１，λｎμｍ｝≥２。

Improving Centralized Path Calculation Based on Graph Compression

Shortest-path calculation on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks(SDN),since SDN controllers need to centralizedly perform a shortest-path query for every flow,usually on large-scale network. Unfortunately,one of the challenges is that current algorithms will become incalculable as the network size increases. Therefore, inspired by the compression graph in the field of compute visualization,we propose an efficient shortest path algorithm by compressing the original big network graph into a small one, but the important graph properties used to calculate path is reserved. We implement a centralized version of our approach in SDN-enabled network,and the evaluations validate the improvement compared with the well-known algorithms.

3D multipath planning for UAV based on network graph

According to the characteristic and the requirement of multipath planning, a new multipath planning method is proposed based on network. This method includes two steps： the construction of network and multipath searching. The construction of network proceeds in three phases： the skeleton extraction of the configuration space, the judgment of the cross points in the skeleton and how to link the cross points to form a network. Multipath searching makes use of the network and iterative penalty method （IPM） to plan multi-paths, and adjusts the planar paths to satisfy the requirement of maneuverability of unmanned aerial vehicle （UAV）. In addition, a new height planning method is proposed to deal with the height planning of 3D route. The proposed algorithm can find multiple paths automatically according to distribution of terrain and threat areas with high efficiency. The height planning can make 3D route following the terrain. The simulation experiment illustrates the feasibility of the proposed method.

Individual tree extraction from terrestrial laser scanning data via graph pathing

Background:Individual tree extraction from terrestrial laser scanning(TLS)data is a prerequisite for tree-scale estimations of forest biophysical properties.This task currently is undertaken through laborious and time-consuming manual assistance and quality control.This study presents a new fully automatic approach to extract single trees from large-area TLS data.This data-driven method operates exclusively on a point cloud graph by path finding,which makes our method computationally efficient and universally applicable to data from various forest types.Results:We demonstrated the proposed method on two openly available datasets.First,we achieved state-of-the-art performance on locating single trees on a benchmark dataset by significantly improving the mean accuracy by over 10% especially for difficult forest plots.Second,we successfully extracted 270 trees from one hectare temperate forest.Quantitative validation resulted in a mean Intersection over Union(mIoU)of 0.82 for single crown segmentation,which further led to a relative root mean square error(RMSE%)of 21.2% and 23.5% for crown area and tree volume estimations,respectively.Conclusions:Our method allows automated access to individual tree level information from TLS point clouds.The proposed method is free from restricted assumptions of forest types.It is also computationally efficient with an average processing time of several seconds for one million points.It is expected and hoped that our method would contribute to TLS-enabled wide-area forest qualifications,ranging from stand volume and carbon stocks modelling to derivation of tree functional traits as part of the global ecosystem understanding.

Optimal parallel algorithm for shortest-paths problem on interval graphs

This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.

Longest Paths and Cycles in Connected Claw-Free Graphs

A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two distinct vertices x and y in V(G)-{v},G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G-C,and if H is connected but not 2-connected,then there exist nonadjacent vertices u and v in H such that |V(C)|≥(3(d(u)+)d(v))-2.

System Vulnerability Analysis Using Graph Pathfinding Strategies in Partitioned Networks

In this paper, a new method has been introduced to find the most vulnerable lines in the system dynamically in an interconnected power system to help with the security and load flow analysis in these networks. Using the localization of power networks, the power grid can be divided into several divisions of sub-networks in which, the connection of the elements is stronger than the elements outside of that division. By using our proposed method, the probable important lines in the network can be identified to do the placement of the protection apparatus and planning for the extra extensions in the system. In this paper, we have studied the pathfinding strategies in most vulnerable line detection in a partitioned network. The method has been tested on IEEE39-bus system which is partitioned using hierarchical spectral clustering to show the feasibility of the proposed method.

Length of the Longest Path and Diameter in Orientations of Graphs

We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether λhas the interval property. In this note, we answer this question in the affirmative. We also show that the diameter of directed graphs does not have the interval property.

基于CiteSpace的国内旅游形象研究进展与展望

旅游形象历来受到旅游目的地重视,也是目的地研究的重要领域。厘清旅游形象的研究热点与演化路径,有助于进一步推动目的地形象管理领域的理论创新。文章基于中国知网数据库收录的1994-2022年旅游形象研究文献作为数据,运用CiteSpace可视化软件对文献作者、研究机构和关键词进行计量分析。研究表明:旅游形象领域学者及机构共现较少,学术交流与合作亟待加强;研究热点主题有城市旅游、形象感知、品牌形象、品牌塑造、认知形象、内容分析和网络文本等;数字足迹、网络游记、地理标记图片、网络文本分析、文本挖掘等是今后一段时期旅游形象研究相关的热点主题。

正确性可验证的密文图数据最短路径外包计算方案

地理位置、社交网络等海量图数据应用广泛且包含大量隐私,通常需要安全的外包计算来提供多样化的查询服务。然而,如何设计正确性可验证的图数据外包计算协议仍是公开的难题。为此,提出了加密图数据上正确性可验证的精确最短路径外包计算方案。该方案利用加法同态加密构造密态图数据上的广度优先最短路径计算算法,支持加密图数据的精确最短距离查询外包计算;其次,基于双线性映射累加器构造最短路径外包计算结果的概率正确性验证机制。分析和证明表明,该方案能以概率可靠性实现正确性可验证的精确最短路径的外包计算,具备随机预言模型下的IND-CCA2安全。对比实验结果表明,所提方案相比其他相关方案在安全性、功能性方面有显著优势,性能上较已有可验证图数据外包计算方案在初始化及加密环节、查询环节、验证及解密环节的时间开销分别降低了0.15%~23.19%,12.91%~30.89%和1.13%~18.62%。

基于图搜索的陆空两栖平台3D路径规划算法

为了解决陆空两栖平台路径规划能效与寻径效率问题,提出了一种基于图搜索算法的全局路径规划算法。考虑了空中飞行能耗与地面行驶能耗模型的不同,结合起飞阈值、地面移动成本系数、空中移动成本系数等参数决定模态切换机制,在遇到难以越过的障碍时使用逃脱算法脱困,当允许地面通过时优先采用地面行驶的方式到达目标点以提升寻径效率与能效。为验证该算法,分别建立了针对陆空2种模式下的能耗模型,在现有交通规则约束下完成城市场景和虚拟迷宫测试。结果表明:本算法的搜索效率相较于对照组算法提升了30%以上,有效提升搜寻效率的同时降低了能量消耗。

基于证据图推理的文档级实体关系抽取

[研究目的]为缓解文档级实体关系抽取任务中存在的句子噪声问题,提高文档级实体关系抽取性能,提出一种基于证据图推理的文档级实体关系抽取方法,为文档级实体关系抽取和知识发现研究提供参考。[研究方法]通过启发式规则捕获实体对间关系推理所需证据句路径信息;引入图结构学习思想将证据句路径信息融入异构文档图;基于关系图卷积网络进行关系推理以提升文档图对证据句信息的聚合能力;采用前馈神经网络对实体关系进行预测,实现文档级实体关系高效抽取。[研究结论]所提出的模型在国际公开文档级评测数据集CDR和GDA上F1值分别达到71.3%和85.4%,较基准模型EIDER提高1.2%与1.1%。实验结果表明该方法能够有效选择实体关系推理所需证据路径,提升文档级实体关系抽取性能。

基于有向图规划的城乡物流配送路径优化研究

为了解决当前的城乡物流配送路径优化方法存在的路径利用率和需求点满意度低、配送成本高的问题,提出基于有向图规划的城乡物流配送路径优化方法。将城乡物流配送路径优化转化为配送路线合理安排问题,设计城乡物流配送路径问题表达式和约束条件,以此提出配送路径优化假设,建立城乡物流配送路径优化模型,并制定模型约束。采用有向图规划计算最短路径和最早配送时间,并获取该范围内的需求点,得到优化后的城乡物流配送需求点和路径。实验结果表明,研究方法的配送成本较低,路径利用率和需求点满意度较高。

路与星图的强乘积图的容错直径

设路P_(m)与星图S_(1,n-1)的强乘积图为G=P_(m)S_(1,n-1).首先,通过归纳假设和构造内点或边不交路的方法,结合星图的中心性,给出图G的点容错直径D_(w)(G)和边容错直径D′t(G).结果表明,对图G中发生的任意点或边故障,都有D_(w)(G)≤d(G)+2,D′t(G)≤d(G)+1.其次,通过顶点数和边数构造的不等关系,给出两个极大连通图的强乘积图的点容错直径的上界,以及两个非平凡连通图的强乘积图的边容错直径的上界.

结合注意力机制的属性异质网络嵌入方法

图(网络)是一种常用于抽象现实世界实体之间关系的数据结构,网络嵌入广泛应用于图数据的表征.目前大部分异质网络嵌入方法未考虑网络节点之间的多种边类型和边属性,无法完整刻画网络的结构和语义信息,导致原始网络特征信息丢失和下游任务效果差的问题.为解决该问题,基于注意力机制设计了一种多边属性异质网络嵌入方法,其将注意力机制应用于学习不同边类型下嵌入向量的重要系数,通过有偏序列采样、邻居向量聚合和模型参数更新3个阶段的嵌入学习,将网络节点表示成固定长度的稠密向量.实验表明,提出的嵌入方法能够更好地嵌入网络的特征信息,使之在下游的机器学习任务上有一定的效果提升.

一种基于转发图的域内路由保护算法

业界提出利用路由保护算法来解决网络中的故障问题,然而已有的路由保护算法存在4个方面的问题:1)无法应对网络中所有可能的单故障情形;2)需要额外辅助机制的协助;3)不支持增量部署;4)每个结点存储多个到达目的地址的备份下一跳.提出一种基于转发图的域内路由保护算法(an intradomain routing protection algorithm based on forwarding graph,RPBFG)来解决这4个问题.首先建立了以最大化故障保护率为目标、以转发图包含反向最短路径树为约束条件的路由保护模型;然后提出了利用遗传算法构造满足上述目标的转发图;最后根据构造的转发图计算出所有结点到达目的结点的备份下一跳.在11个真实拓扑结构中比较了RPBFG,NPC,U-turn,MARA-MA,MARA-SPE在故障保护率和路径拉伸度的性能.实验结果表明,RPBFG可以应对网络中所有可能的单故障;在平均路径拉伸度方面,RPBFG比NPC,U-turn,MARA-MA,MARA-SPE分别降低了0.11%,0.72%,37.79%,36.26%.

感-通-物多目标融合应急无人机路径规划方法

为了完成多无人机应急救援场景下救灾点的需求感知(感)、数据收集(通)和物资投放(物)任务,提出了在考虑无人机能耗约束下,感-通-物多目标融合的两阶段的应急无人机路径规划求解框架。第一阶段提出基于时序图卷积网络的救灾点人数预测模型,并量化救灾点物资和通信需求;第二阶段提出基于贪心和禁忌搜索的多无人机路径规划算法,通过交替优化救灾点划分和单无人机路径规划来求解原优化问题。仿真结果表明,该算法在总服务收益上优于传统的无预测多无人机路径规划算法。

路与广义Petersen图的直积图的Wiener指数

图G和H的直积图G×H是一个顶点集为V(G)×V(H)的图,两点(g_(1),h_(1))和(g_(2),h_(2))是相邻的当且仅当g_(1)g_(2)是图G中的一条边,h_(1)h_(2)是图H中的一条边.连通图G的Wiener指数,记作W(G),是图G中无序点对之间的距离之和.最后得到了路与广义Petersen图P(m,3)的直积图的Wiener指数.

图论在网络的可靠性分析中的应用—对基于1-critical-pathsubset网络的性能分析

本文对一种网络流模型的可靠性进行分析 .在这个模型中 ,我们考虑一对源节点和汇节点的图 ,它的弧是随机失效的 .当网络最大流大于正常工作流 ,我们就说系统是正常工作的 .考虑正常工作流的一种特殊情况 ,这里 ,所有的弧都具有相同的容量 .在这种特殊的情况中 ,潜在的系统是 1- critical的 ,也就是说 ,所有的弧的最小截大小为 2 .此时 ,问题转化为在有向图中 ,求所有的失效弧都在同一条路径上的概率 。