基于无向图转有向图的同构判别

无向同构图指的是在两个图中寻找顶点之间的映射关系,通过映射使原本形式各异的两图中的各条边保持对应的关系.为了有效提高寻找无向同构图的时间效率、简化操作,首先研究了无向图同构的矩阵存储方式,并针对性地提出了把无向图转换为有向图的同构算法.与矩阵存储算法相比,该判定算法的时间更为简短.最后给出了实现该算法的相关程序以及用该算法对无向图进行判定的过程和结果.     

无向图同构的充要条件以及判定

通过对两个图邻接矩阵的特征值以及特征向量分析,利用对角化过程中的正交特征向量矩阵的特殊性质,得到了一种新的无向图同构的充要条件,并且由此条件得到同构图之间存在的关系,从而使得判定图的同构更加方便,尤其是在需要找出变换矩阵、判定同谱图时非常有效.     

简单无向图的同构判定问题的研究

图的同构判定问题是图论学科的基本问题之一,但是要判定两个图是否同构却是一件非常不简单的事情。本文旨在研究简单无向图的同构判定问题;并提出了一种新的简单无向图同构的必要条件。     

有限非交换群的交换图的一些性质

设G是一个有限非交换群,ΓG是G的一个交换图,这个交换图ΓG的顶点集为群G的所有元素,ΓG的两个不同顶点x和y是相连的当且仅当xy=yx.该文研究了交换图的一些性质,具体介绍了几个交换图同构的例子.     

关于广义路代数

通过将箭图的每个顶点放置一个k-代数,路代数的概念被推广到了广义路代数。首先研究了广义路代数的遗传性质。其次讨论了同构问题,证明了当两个正规广义路代数中的箭图都有限且无定向圈时,它们作为代数是同构的当且仅当它们中的箭图及对应顶点上的单代数是同构的。     

无向无权图同构判别算法简

首先,分析判别同构图的一种常用实现方法:基于邻接矩阵存储,并讨论其存在的时间复杂度为O(N!).接着,针对两图中结点数、边数、每个结点的度均相同的特殊图形提出无向无权图同构判别的另一算法:采用结点之间距离及关联边进行判别.最后通过实例进行算法测试和比较,证明了该算法是完全行之有效的.     

基于路径信息比较的图同构新算法

为了在多项式时间内解决图同构问题,首先证明了2个同构图相等长度的路径信息必相同是图同构判定更为严格的必要条件.然后,根据此条件,提出了一种基于路径信息比较的图同构PIC算法.该算法依次比较各长度的路径信息,对邻接矩阵进行调整,从而实现了2个图的快速同构判定.为了减少路径信息的计算时间,引入Hash函数对PIC算法进行改进,从而得到了HPIC算法.实验结果表明,所提的2种算法均能够正确判定1×104对不同类型、不同大小的随机图是否同构,并且图同构判定的时间复杂度明显降低.HPIC算法的运行速度快于PIC算法;这2种算法在时间性能方面均优于CS算法,略劣于Nauty算法;但对于规则2维网孔图,Nauty算法失效,所提的2种算法则仍能快速进行图同构判定.     

一种对称无向图的同构判定算法

文章在电路模拟法的基础上提出了一种对称无向图的同构判定算法.电路模拟法对随机图的同构判定问题非常有效,但是对于处理对称度较高的图,判定效率明显降低甚至失效.该文提出的算法针对对称无向图的特性,在电路模拟法的基础上结合Dijkstra算法,综合得到顶点属性和最短距离序列来搜索顶点之间的映射关系,能够有效判定这类图的同构问...     

交换环的二部本质图

交换环R的本质图EG(R)是一个无向简单图,它以Z(R)\{0}为顶点集,两个不同的顶点x、y之间有一条边相连当且仅当ann(xy)是R的一个本质理想.给出了模n剩余类环Zn的零因子图与本质图相等的充分必要条件.在此基础上,证明了交换环的二部本质图必是完全二部图,并对相应的环进行了同构分类.     

支持增量图数据的超图查询算法研究

当前大部分图查询算法都是针对静态图数据,不适用于现实应用中不断更新的图数据。针对这一问题,提出支持增量图数据的超图查询算法。该算法将数据图分解成直至单个顶点的子图,然后从单个顶点的子图开始求它到查询图的子图同构,直到求出数据图到查询图的子图同构结果,算法在数据图增加时只需将新加入的数据图进行分解即可,不必重新计算。通过分析证明,所提算法时间和空间复杂度不随数据图的增加而呈线性增长,节省了大量时间和空间代价。     

一个求外平面图最小反馈点集的多项式时间算法

如果从一个图中去掉某些顶点后得到的导出子图是无圈图，则所去的那些顶点组成的集合就是原图的反馈点集。本文讨论外平面图的反馈点集并给出了一个求外平面图最小反馈点集的多项式时间算法。     

任意无向加权图K点连通扩充的逐次改善算法

为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K 点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明.最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果.为解决任意无向加权图最小扩充问题给出了一种新途径.     

图的同构判定算法:关联度序列法及其应用

提出了图的同构判定新算法,即关联度序列法和黄金分割关联度序列法,后者的计算时间复杂性远远低于2N（N为图的顶点数）,已接近于多项式时间复杂性,该算法可应用于很多能用图来描述的式识别等实际问题。     

赋权图上最短路径的一种简便算法

在不考虑负回路的前提下,给出了在含有负权的赋权图上求任意两点间最短路径的一种简便算法,此算法既适用于有向图又适用于无向图,并且可据此算法找到最短路径。     

3度非对称的点传递图的性质

设X为3度连通的简单无向图,X称为具有非平凡点稳定子群的非对称的点传递图,若X的全自同构群A在X的顶点集合上作用是传递的,而且X的任意顶点在A中的稳定子群在该点的邻域上的作用是非传递的、非平凡的.本文考察了这种图,我们给出了这类图的一些性质.     

图的坚韧度与图的Laplacian特征值的关系

利用简单无向图中的特殊顶点集与图的Laplacian谱的关系,得到了有关图的坚韧度与Laplacian 谱的一个有趣的关系式.     

Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs

Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights l(e) satisfying the triangle inequality. The vertex set V is partitioned into clusters V1, V2, …, Vk. The clustered traveling salesman problem (CTSP) seeks to compute the shortest Hamiltonian tour that visits all the verti- ces, in which the vertices of each cluster are visited consecutively. A two-level genetic algorithm (TLGA) was developed for the problem, which favors neither intra-cluster paths nor inter-cluster paths, thus realized inte- grated evolutionary optimization for both levels of the CTSP. Results show that the algorithm is more effec- tive than known algorithms. A large-scale traveling salesman problem (TSP) can be converted into a CTSP by clustering so that it can then be solved by the algorithm. Test results demonstrate that the clustering TLGA for large TSPs is more effective and efficient than the classical genetic algorithm.     

一类完全多部图的Hamiton性刻画

Gutin证明了在强的半完全二部图中若含有一个由两个圈构成的圈因子,则图是Hamilton图。把此定理推广到无向图中就可得到这样一个结果,即含有一个由两个圈构成的圈因子的完全二部图是Hamilton图。在此基础上,对含有由两个圈构成的圈因子的完全n（n≥3）部图进行了讨论,得出了类似于二部图的结果。     

求解图最大团的并行算法

本文给出了一个求解图中最大团的异步并行算法。在算法中采用了最优先搜索和分枝限界法等人工智能搜索技术,避免了无意义的搜索。其特点是易于在共享内存多处理机的并行计算机上实现,其执行时间曲线表明,对图中任意2点之间边存在概率小于1/3的无向图,具有较高效率的求解过程。还给出了在一定条件限制下,求解 NP—完全问题的方法。