图索引技术研究综述

随着信息技术和网络技术的发展,图作为一种通用的数据结构被用于不同学科建模各种实体以及实体之间的关系,,图中各实体间隐藏了很多有价值的信息,为了挖掘图中隐藏的这些信息,图的相关研究成为了各领域的研究热点,但在大多数图研究中最关键的问题是如何有效地进行图查询。在图数据库中存在着两种图数据集：单图和图集。针对单图或图集进行图查询是相当费时的,为了加快图查询速度,图索引成为各种图查询算法的研究重点,而图索引的焦点在于利用图索引的结构模式来最小化搜索空间的大小。本文将图查询归为两种：子图查询和超图查询。在每种查询中,依据图索引建立时选择的图结构特性进行了细分,主要集中于图索引的构建思想,并对典型的索引方法进行了详细的叙述。针对不同的图索引分析了各自的优缺点,并比较了各种索引方法的特点,最后,总结并探讨了图索引的发展趋势。     

超级太阳图的felicitous性质

许多环行网络可以被转换成图论中的超级太阳图,使得超级太阳图中的环上每一个节点代表一个服务器,与环所连接的节点代表客户.作者对超级太阳图的felicitous性质进行了研究,利用具有集有序felicitous性质的树构造超了级太阳图,并确定了这类图的felicitous标号.此外,对唯一圈图中的特殊图(超级太阳图)的felicitous性质进行了研究,利用具有felicitous性质的树构造超级太阳图,并确定了这类图的felicitous标号.     

分数Hamilton图的充分必要条件

分数Hamilton图是比Hamilton图更广泛的图类.作者借用线性规划的知识给出了判定分数Hamilton 图的新的充分必要条件,并利用新的充分必要条件对特殊图类的分数Hamilton图进行了研究.     

不含三圈的双圈图的谱半径

Nikiforov等人最近将图谱研究与极值图论相结合,提出了谱Turán型问题:给定一个图F,设G是一个不含子图与F同构的n阶图,那么图G的谱半径至多是多少?双圈图是边数等于顶点数加1的简单连通图。近期,部分学者对双圈图的谱半径进行了研究,确定了双圈图谱半径的第1~10大值和相应的极图。受此启发,研究了不含三圈的双圈图,确定不含三圈的双圈图的谱半径的上界,并刻画了相应的极图。     

临界极小2连通图的构造

连通极值图类的构造,是图论研究中的一个重要课题,本文对唯一剩下没有被构造出的2(边)连通极值图类——临界极小2连通图类进行了研究,得出了一个特征定理,构造出这个图类。同时,本文研究了临界与极小之间的关系,在构造出临界极小2连通图类的基础上,用新的方法构造出临界2连通图类和极小2连通图类。     

求图上广探树的时间复杂度

本文研究如何找连通图的广探树问题,对边权相同的赋权连通图和边权不同的赋权连通图,分别进行了研究.在对图进行广度优先遍历的过程中找到了一棵广度优先树,并总结出:对于边权相同的图而言,至多在O(n)阶多项式步骤下可以找到图的一棵广探树;对于边权不同的图而言,至多在O(n)2阶多项式步骤下可以找到图的一棵广探树.     

平环图着色的性质

利用色多项式的零点问题的性质研究了平面图的着色问题,主要研究平环中具有n个区域以及剖分后得到的图进行着色性质,也就是使得相邻两个区域着不同色.首先,研究了带有n个区域平环图Gn的最小涂色数目,并且该图进行广义三角剖分,研究了广义三角剖分后图的涂色数目的性质;其次,讨论了两个这样图组合在一起,就是两个具有一条公共边Gt和Gs组成区域图的性质,讨论这些图及其广义三角剖分后图的涂色性质.进而证明这些图在剖分前后的着色的性质是不变的.     

广义Bartlett图的分类研究

针对贝叶斯推断问题研究了广义Bartlett图的一类新模型。运用无向图的可分解覆盖算法,对长度大于等于4的圈和完全二分图G=K_(m,m)(m大于等于3)进行研究。研究结果表明,长度大于等于4的圈属于广义Bartlett图,完全二分图G=K_(m,m)(m大于等于3)不属于广义Bartlett图。通过引入广义Bartlett图的概念和可分解覆盖算法,避免了在不可分解图上进行贝叶斯推断时模型选择的困难。     

2类图的零度的极图的刻画

应用图谱理论的基本方法对两类图的零度的极图进行了研究,刻画了达到上界的极图,推广了前人的有关结论.     

正则q 树根图的双概率可靠性探究

首先研究得到了双变量色多项式的一般性的减边公式.接着对根图顶点进行了期望值研究,得出其减边公式,并由此得到一些特殊根图的期望值计算公式.最后讨论了正则q-树根图和正则q-树整子根图的期望值计算公式.     

极大基尔霍夫指数的块图

图的基尔霍夫指数是指图中所有无序点对之间的电阻距离之和,是化学分子图的最重要的拓扑指数之一.本研究首先给出图的基尔霍夫指数的相关运算,接着利用移接变形对图的基尔霍夫指数进行研究,给出块图的基尔霍夫指数上界,并刻画了块数小于4时对应的极图.     

具有完美匹配的仙人掌图的极小广义和连通指数

限制-0.585≤α0,对具有完美匹配的仙人掌图的广义和连通指数进行了研究.通过分析,利用图的变换,将符合条件的仙人掌图缩小范围,然后通过数学归纳法进行证明,最终得到具有完美匹配的仙人掌图的广义和连通指数的极小值并刻画了极图.     

几类图的符号星k控制数

通过对图G的边集分析的方法,对图的符号星k控制数进行研究,确定了几类图的符号星k控制数     

图的分数f-因子的一些性质证明

对图的分数f-因子的一些性质进行了研究.设G为一个图,给出G的子图,证明了图G有分数f-因子含有子图的每条边或不含子图的任一条边的充要条件.     

耦合诱导Turing斑图的形成

通过数值模拟的方法研究了耦合的CDIMA反应模型。结果显示:处于不能形成图林斑图区域的系统与另一个处于图林斑图区域的系统进行耦合,两系统都能形成图林斑图。     

关于简单图是Hamilton图的若干判定定理

寻找一个图是Hamilton图的充要条件一直是图论中不断探索的重要课题,本文对Hamilton问题进行了较深入的研究和讨论,给出了简单图是Hamilton图的若于判定定理及其证明。     

几类图的强符号控制数

本文对几类特殊图的强符号控制函数及强符号控制数进行了研究,给出了完全图、完全二部图、路及圈的强符号控制数。     

几类图的强符号控制数

本文对几类特殊图的强符号控制函数及强符号控制数进行了研究,给出了完全图、完全二部图、路及圈的强符号控制数.     

关于Uni=1miC24的优美性

优美图是图论中的重要课题,至今对非连通图优美性的研究并不多,特别对n个图的并图优美性的研究就更少,笔者给出一类非连通图Uni=1miC24,证明了当mi≥2(i=1,2,…,n)时,这类图是优美图,也是交错图,并在此基础上进行了推广,从而给出构造一类任意n个图的并图是优美图和交错图的一种方法.     

循环赋权图的谱分析

近年来,对循环图的研究已有很多出色成果,但对循环赋权图的研究却很少,对于多重循环赋权图和广义循环赋权图的研究则更少。本文对上述循环赋权图的谱结构进行分析,建立了谱定理和极限分布定理。所得结果在晶体能谱,同系物能谱,均匀连续介质有限元等方面有一定实用价值。