共查询到19条相似文献,搜索用时 171 毫秒
1.
侯爱民 《计算机工程与应用》2009,45(30):57-61
图同构的判定性问题是图论理论中的一个难问题,至今没有得到彻底解决。Ulam曾经提出过一个判定图同构的猜想,也称为图的重构猜想。提出了一个新的判定图同构的充分必要条件,即在子图同构的前提下,根据新增顶点及相应关联边的关系,判断母图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术,采用数学归纳法证明了这个充分必要条件的成立。 相似文献
2.
3.
侯爱民 《计算机工程与应用》2011,47(16):52-57
图同构的判定性问题是图论理论中的一个难题,至今没有得到彻底解决。受Ulam猜想的启发,提出了一个新的判定图同构的充分必要条件:在子图同构的前提下,根据新增顶点及相应关联边的关系,利用子图同构函数,判断父图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术,采用反证法证明了这个充分必要条件的成立。设计并实现了图同构的一个判定算法,通过实例验证了算法的正确性和有效性。 相似文献
4.
简单连通图若边数等于顶点数加1,且图中所含的两个圈至少有两个公共顶点,则称该图为相交双圈图。主要给出了相交双圈图中第五到第十大代数连通度的图类。 相似文献
5.
(一)问题 2000年第24期擂台赛的问题是有向图的连通性判断。 对一个有向图,忽略所有有向边的方向性而得到对应的一个无向图,如果该无向图是连通的,即其中任意两点有通路相连,则称原有向图是弱连通的:如果在原有向图中任意两点间至少有一点至另一点的通路,则称该图是单向连通的:而如果原图任两点之间一定既有甲至乙,也有乙至甲的通路,即有双向通路,则称该图是强连通的。 例如,图1是一个非弱连通非单向连通与非强连通图:图 相似文献
6.
新疆大学数学物理研究所承担的国家自然科学基金项目:图论及其在化学和网络优化中的应用,已在国际上的ISIP、MR、SCI等文献上发表了20篇论文。它的一系列成果有:首次引入K-图共振图概念,并建立了判定K-圈共振图的充分必要条件;建立了广义分子键序模型;首次基于广义六角系统的性质定义了广义六隅体及其结构,定义了超环及超六隅体旋转变换图等新概念,并证明了该变换图的有向树结构;首次建立了辨识Kekulean六角系统的典型P—V路消去法,建立了生成该系统所有1=因子的有效算法;首次给出了临界K-边连通图… 相似文献
7.
图连通性的判定对于路径规划中任意两点间路径相通性判断以及连通块的划分都具有重要意义。从节点的边连通关系着手分析图的结构层次,通过构建图的分层递阶商空间链,分析不同层次商空间链中各节点分布情况,得出新的图连通性判定方法。与以往各判定方法相比,该方法具有易实现、效率高的优点,不仅能有效地判定图是否连通,还能确定图的连通分支数以及哪些节点位于同一连通分支中。 相似文献
8.
9.
姜新文 《计算技术与自动化》2004,23(2):52-54
给出了哈密顿图判定问题的一个算法。思想是先将简单无向图转换成多级图,然后证明简单无向图中哈密顿回路存在性与多级图中简单路径(定义见正文)存在性的等价性,最后通过多级图中简单路径存在性的判定实现简单无向图H性质判定。 相似文献
10.
11.
We consider the problem of coloring a planar graph with the
minimum number of colors so that each color class avoids one or
more forbidden graphs as subgraphs. We perform a detailed study of
the computational complexity of this problem. We present a complete picture for the case with a single forbidden
connected (induced or noninduced) subgraph. The 2-coloring
problem is NP-hard if the forbidden subgraph is a tree with at
least two edges, and it is polynomially solvable in all other
cases. The 3-coloring problem is NP-hard if the forbidden
subgraph is a path with at least one edge, and it is polynomially solvable in all other
cases. We also derive results for several forbidden sets of
cycles. In particular, we prove that it is NP-complete to decide if a planar
graph can be 2-colored so that no cycle of length at most 5 is
monochromatic. 相似文献
12.
本文基于{0,1}线性不定方程组和顶边关联矩阵.提出了一个基于无向Hamiltonian图的充要判定定理。并证明了满足该定理的不定方程组解向量对应给定圄的Hamiltonian回路中边的集合,本文还推导出两个可以基于矩阵秩的Hamiltonian回路存在的必要判据。 相似文献
13.
We analyse a polyhedron which contains the convex hull of all Hamiltonian cycles of a given undirected connected cubic graph. Our constructed polyhedron is defined by polynomially-many linear constraints in polynomially-many continuous (relaxed) variables. Clearly, the emptiness of the constructed polyhedron implies that the graph is non-Hamiltonian. However, whenever a constructed polyhedron is non-empty, the result is inconclusive. Hence, the following natural question arises: if we assume that a non-empty polyhedron implies Hamiltonicity, how frequently is this diagnosis incorrect? We prove that, in the case of bridge graphs, the constructed polyhedron is always empty. We also demonstrate that some non-bridge non-Hamiltonian cubic graphs induce empty polyhedra as well. We compare our approach to the famous Dantzig–Fulkerson–Johnson relaxation of a TSP, and give empirical evidence which suggests that the latter is infeasible if and only if our constructed polyhedron is also empty. By considering special edge cut sets which are present in most cubic graphs, we describe a heuristic approach, built on our constructed polyhedron, for which incorrect diagnoses of non-Hamiltonian graphs as Hamiltonian appear to be very rare. In particular, for cubic graphs containing up to 18 vertices, only four out of 45,982 undirected connected cubic graphs were so misdiagnosed. By constrast, we demonstrate that an equivalent heuristic, when built on the Dantzig–Fulkerson–Johnson relaxation of a TSP, is mostly unsuccessful in identifying additional non-Hamiltonian graphs. These empirical results suggest that polynomial algorithms based on our constructed polyhedron may be able to correctly identify Hamiltonicity of a cubic graph in all but rare cases. 相似文献
14.
通过定义k元组合的方式给出了一个逐步搜索图(有向或元向)的全部Hamiltonan回路的新算法和判定图的哈密顿特性的充要条件。使用该算法可准确地求出Hamiltonan图的全部Hamiltonan回路,不必生成基本回路。 相似文献
15.
We consider the two problems of finding the maximum number of node disjoint triangles and edge disjoint triangles in an undirected graph. We show that the first (respectively second) problem is polynomially solvable if the maximum degree of the input graph is at most 3 (respectively 4), whereas it is APX-hard for general graphs and NP-hard for planar graphs if the maximum degree is 4 (respectively 5) or more. 相似文献
16.
In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. We assume that all the unknown graphs are undirected and connected. The searcher is not aware of the existence of an edge until he/she visits one of its endpoints. The searcher's task is to visit all the nodes and go back to the starting node by traveling a tour as short as possible. One of the simplest strategies is the nearest neighbor algorithm (NN), which always chooses the unvisited node nearest to the searcher's current position. The weighted NN (WNN) is an extension of NN, which chooses the next node to visit by using the weighted distance. It is known that WNN with weight 3 is 16-competitive for planar graphs. In this paper we prove that NN achieves the competitive ratio of 1.5 for cycles. In addition, we show that the analysis for the competitive ratio of NN is tight by providing an instance for which the bound of 1.5 is attained, and NN is the best for cycles among WNN with all possible weights. Furthermore, we prove that no online algorithm to explore cycles is better than 1.25-competitive. 相似文献
17.
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G
have non-negative weights assigned to them. In this problem a {-1,0,1} incidence vector is associated with each cycle and
the vector space over
generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for
its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. This
paper presents an
algorithm, which is the first polynomial-time algorithm for computing a minimum cycle basis in G. We then improve it to
an
algorithm. The problem of computing a minimum cycle basis in an undirected graph has been well studied. In this problem
a {0,1} incidence vector is associated with each cycle and the vector space over
generated by these vectors is the cycle space of the graph. There are directed graphs in which the minimum cycle basis has
lower weight than any cycle basis of the underlying undirected graph. Hence algorithms for computing a minimum cycle basis
in an undirected graph cannot be used as black boxes to solve the problem in directed graphs. 相似文献
18.
本文分析基于量子绝热近似的不同顶点的最大割问题求解.该算法将无向图的顶点等效为量子比特,各个顶点间的边等效为两个量子比特之间的耦合,边的权重值等效为量子比特间的耦合强度.采用Python语言编写算法程序,模拟了6–13个顶点的完全无向图的最大割问题求解情况.实验结果表明,当完全无向图顶点个数取为8,12,13,同时耦合强度为1.0时,所求解最大割问题哈密顿量的期望值不收敛.进一步调整模拟计算中量子比特间耦合强度数值,观察期望值变化.实验发现,对于顶点数为12的完全无向图,耦合强度取0.95时,其期望值获得收敛.对于顶点数为8和13的完全无向图情形,当耦合强度取0.75时,所计算得到的期望值随演化时间变化收敛.由此推测超过13个顶点的完全无向图在用量子绝热算法求解最大割问题时,可将量子比特耦合强度归一化到0.75左右,使期望值有效收敛. 相似文献
19.
《Advances in Engineering Software》2001,32(5):339-351
Linear time algorithms are presented which generate the Voronoi tessellation from a Delaunay tessellation and vice versa when the tessellations of convex polygons and triangles are stored as edge-adjacent undirected graphs. These two geometric algorithms lead naturally to two further linear and quadratic graph algorithms for determining the minimal simple cycles or regions in both triangular and regular-3 undirected planar graphs. 相似文献