共轭单圈图的广义Randic指标

化学分子图的拓扑指标理论是组合化学的一个重要研究分支,Randic指标与烷烃分子的很多物理和化学性质都显示了很强的相关性,如沸点、表面积以及水溶解度等等。Randic指标具有很低的退化度,能很好的描述分子结构和结构活性之间的关系。每一个顶点都是饱和的单圈图称为共轭单圈图。图G的广义Randic指标定义为R_a(G)=(d_ud_v)~a,其中α为任意实数,d_u为顶点u的度。本文使用反证法,通过分类讨论,研究了α∈[-1.3867,-1]时,共轭单圈图的广义Randic指标的最小值问题,给出了最小值及其相应的结构。给出的分子结构具有最小的广义Randic指标值,以及由此衍生而来的某类分子结构,可以帮助建立分子图数据库,对合成一些分子或药物具有非常重要的理论价值和应用背景。     

煤炭运输公路网络可靠性仿真分析

针对突发事件对煤炭运输公路网络中节点或边的破坏，引起煤炭运输公路网络堵塞的问题，基于复杂网络理论，建立原始法和对偶法构建的网络模型，并用Matlab软件对其可靠性进行仿真分析。首先，对比分析了两种网络的基本特征，然后提出网络效率相对变化量对网络中的关键路段进行识别。基于此，建立网络可靠性评价模型，并提出网络效率、最大连通子图相对大小和网络离散度三个可靠性评价指标，对在随机毁坏和蓄意毁坏两种毁坏模式下的网络可靠性进行仿真分析。实验结果表明：在蓄意毁坏模式下，当10%的节点失效时，三种可靠性指标值分别为10%、20%、20，而随机毁坏模式下的指标值仍维持在较高的水平，因此，煤炭运输网络对随机毁坏具有鲁棒性，对蓄意毁坏具有脆弱性，应加强对网络中重要节点的保护工作。     

搜索图的全部可能回路的新算法

51．引言如何找出一种简便算法来判断一个图中的所有回路是网络图论学者所关心的重要问题之一，也是计算机网络和操作系统理论所研究的重要课题．对于无向图而言，传统的做法是先找出图的基本回路，然后形成其全部线性组合，再从中删去不是回路的组合．这种算法比较繁琐．本文提出的算法是以图中某一顶点为参考点，找出与该点相关联的边组成的二元组合、三元组合、等等，其中每一个闭组合就是一条回路，从而生成通过参考点的所有回路．输出后再删除该参考点及其关联边，生成退化图．对该退化图，重新进行上述搜索，直至退化图成为空留或度数…     

基于图论和启发式搜索的装配序列规划算法

将装配序列规划中成熟的割集法和人工智能中启发式搜索方法相结合，提出一个高效的装配序列生成算法。此算法在启发函数的指导下，直接产生所需的最佳装配规划，避免了单独采用割集法产生装配AND／OR图而导致的组合爆炸的问题。同时省去了在选择装配规划时，对整个装配AND／OR图进行再次搜索。此算法与其它算法相比具有效率高、智能性强的特点。最后给出了一个实例。     

基于图理论的频率子图挖掘算法在生物分子网络中的研究

基于大规模生物分子网络的信息挖掘是近年来生物信息学研究领域的一个重要研究课题,频率子图在生物分子网络中代表具有特定功能的稳定结构,基于频率子图的挖掘是生物信息学的一个重要研究方向,对分子网络中的频率子图挖掘算法进行研究,主要对三种经典频率子图挖掘算法（AGM、FSG、gSpan）进行详细的研究和比较,并对生物分子网络中频率子图挖掘存在的问题及解决这些问题的方法进行研究,其目的是为研究更高效的频率子图挖掘算法提供参考和借鉴。     

用于图分类的组合维核方法

对图等内含结构信息的数据进行学习,是机器学习领域的一个重要问题.核方法是解决此类问题的一种有效技术.文中针对分子图分类问题,基于Swamidass等人的工作,提出用于图分类的组合维核方法.该方法首先构建融合一维信息的二维核来刻画分子化学特征,然后基于分子力学的相关知识,利用几何信息构建三维核来刻画分子物理性质.在此基础上对不同维度的核进行集成,通过求解二次约束二次规划问题来获得最优核组合.实验结果表明,文中方法比现有技术具有更好的性能.     

标记法求解网络和图的最短距离算法

采用深度优先搜索法,文章首次提出了在搜索过程中采用标记距离的算法,有效地求解复杂网络和图的最短距离问题。通过对网络最短距离问题运算效率的分析,表明该算法具有理想的运算效率。文章给出了一个具有现实应用价值和更具潜在应用价值的智能问题算法。     

一种基于与或图的语义Web服务自动组合方法研究

单个Web服务提供的功能有限,服务组合成为Web服务应用的一个重要研究方向。提出了一种基于与或图的语义服务自动组合方法。该方法为Web服务引入语义,能将服务搜索空间受限于服务组合与或图中,并能从服务组合与或图中选出最佳组合图,从而达到优化服务组合的目的。仿真实验证明,该方法提高了Web服务组合的成功率和效率。     

基于与或图的Web服务组合的研究

现在Web服务技术的应用变得更为普及。单个Web服务只提供有限的功能,难以满足实际应用的需要。Web服务组合已经成为Web服务应用中一个非常重要的研究方面。本文提出了一种基于与或图的Web服务组合方法,该方法通过对已经访问过的服务进行标记,以服务代价作为在与或图中进行搜索的依据,缩小了搜索空间,能够快速找到一种代价很小的服务组合方法。仿真实验表明,该方法提高了Web服务组合的效率和成功率。     

数据集成系统中的服务组合方法

利用服务本体语义相似度来表示计算服务之间的关联度,并以关联度为权值基于图论的方法构建服务组合图,然后通过服务组合图转化为组合优化树的方法将服务组合问题转化为树的深度搜索问题,针对该搜索问题提出了一个有效的优化搜索方法,实现了服务动态组合.仿真实验结果表明,与已有方法相比,该方法可以自动地根据服务请求实现服务的动态组合,同时保证了服务组合的效率和质量.     

EvoGeneSys,a new evolutionary approach to graph generation

Graphs are widely used to represent complex and structured information of interest in various fields of science and engineering. When using graph representations, problems of special interest often imply searching. For example, searching for the prototypes representing a dataset of graphs or for the graph that optimizes a set of parameters. In any case, it is necessary that the problem solution be expressed in terms of graphs. Therefore, defining effective methods for automatically generating single graphs, or sets of graphs, representing problem solutions, is a key issue. A new evolutionary computation-based approach specifically devised for generating graphs is presented. The method is based on a special data structure, called multilist, which allows the encoding of any type of graph, directed or undirected, with or without attributes. Graph encoding by multilists makes it possible to define effective crossover and mutation operators, overcoming the problems normally encountered when implementing genetic operators on graphs. Further advantages of the proposed approach are that it does not require any problem specific knowledge and it is able to search for graphs whose number of nodes is not known a priori. Three sets of experiments were performed to test the proposed approach and the solutions found were compared with those obtained by other approaches proposed in the literature.     

Marking Optimization of Weighted Marked Graphs

Cyclic manufacturing systems can be modeled by marked graphs, which are an elementary class of Petri nets. To model systems with bulk services and arrivals and to reduce the size of the model, weighted marked graphs can be used. An important step when designing these systems is the definition of the number of manufacturing resources to be used in order to reach a given productivity. In terms of timed Petri nets, this is known as the marking optimization problem and consists of reaching a given average cycle time while minimizing a linear combination of markings. In this paper, a necessary and sufficient condition to obtain a feasible solution of the marking optimization problem of weighted marked graphs with deterministic times is established. A fast heuristic solution, based on an iterative process and using simulation, is given. An example and an application to manufacturing systems are presented.     

Putting Consistent Theories Together in Institutions

The problem of putting consistent theories together in institutions is discussed.A general necessary condition for consistency of the resulting theory is carried out,and some sufficient conditions are given for diagrams of theories in which shapes are tree bundles or directed graphs.Moreover,some transformations from complicated cases to simple ones are established.     

无向哈密顿图的一个充分必要条件及计算公式

哈密顿图的判定问题是一个NP完全问题,是图论理论中尚未解决的主要问题之一。1968年,Grinberg证明了一个必要条件,提高了判定非哈密顿可平面图的效率,由此产生了很多3-正则3-连通非哈密顿可平面图的研究成果。根据无向哈密顿图的特征,提出了基本圈的分解、合并、单条公共边连通,原子圈等概念。任何一个简单连通无向图G是哈密顿图,当且仅当,哈密顿圈要么其本身就是一个包含所有顶点的原子圈;要么总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通。根据这个充分必要条件,推导出了一个必要条件计算公式。它不仅能处理平面图,也能处理非平面图;甚至能处理某些Grinberg条件不能处理的平面图。此外,对一些实际案例的测试结果验证了充分必要条件和计算公式的有效性。     

大图上跳数受限的可达查询算法研究与优化

判断有向图上两个顶点之间是否存在一条路径是一个经典问题,而对于一些路由规划和图分析等实际应用,要求查找是否存在跳数受限的可达路径,这是一个变种的图可达查询问题.对于大图上跳数受限的查询算法,不仅仅要对大图查询的时间效率和空间效率进行权衡,而且还要利用跳数受限的特性进行优化.普通的可达查询算法存在小度数顶点索引项占用空间过多的问题,造成空间浪费严重.为此我们提出了一种面向跳数受限的2-hop部分索引方法,采用改进的索引方法并结合局部搜索,实现跳数受限的有效可达性查询.实验结果表明,在Orkut社交网络数据集上与已有算法相比,该算法索引空间节省了32％,同时查询时间略微增加,使得我们算法可以计算更大规模图的跳数受限可达问题.     

一类图的色唯一性

如果两个图的色多项式相等,称这两个图色等价。如果与一个图色等价的所有图都与这个图同构,称这个图色唯一。类似的,如果两个图的伴随多项式相等,称这两个图伴随等价。如果与一个图伴随等价的所有图都与这个图同构,称这个图伴随唯一。众所周知,两个图色等价当且仅当它们的补图伴随等价;一个图色唯一当且仅当它的补图伴随唯一。给出了一类图伴随唯一的一个充分必要条件,因而给出了它的补图色唯一的一个充分必要条件。     

A Conjecture on Wiener Indices in Combinatorial Chemistry

Drugs and other chemical compounds are often modeled as polygonal shapes, where each vertex represents an atom of the molecule, and covalent bonds between atoms are represented by edges between the corresponding vertices. This polygonal shape derived from a chemical compound is often called its molecular graph, and can be a path, a tree, or in general a graph. An indicator defined over this molecular graph, the Wiener index, has been shown to be strongly correlated to various chemical properties of the compound. The Wiener index conjecture for trees states that for any integer n (except for a finite set), one can find a tree with Wiener index n. This conjecture has been open for quite some time, and many authors have presented incremental progress on this problem. In this paper we present further progress towards proving this conjecture—through the design of efficient algorithms, we show that enumerating all possible trees to verify this conjecture (as done by all the previous approaches) is not necessary, but instead searching in a small special family of trees suffices, thus achieving the first polynomial (in n) time algorithm to verify the conjecture up to integer n. More precisely, we (i) present an infinite family of trees and prove various properties of these trees, (ii) show that a large number of integers, up to at least 10⁸ (compared with the previous best 10⁴) are representable as Wiener indices of trees in this succinct family, (iii) provide several efficient algorithms for computing trees with given Wiener indices, and (iv) implement our algorithms and experimentally show that their performance is asymptotically much better than their theoretical worst-case upper bound.     

Vertex-Edge Degree Based Indices of Honey Comb Derived Network

Chemical graph theory is a branch of mathematics which combines graph theory and chemistry. Chemical reaction network theory is a territory of applied mathematics that endeavors to display the conduct of genuine compound frameworks. It pulled the research community due to its applications in theoretical and organic chemistry since 1960. Additionally, it also increases the interest the mathematicians due to the interesting mathematical structures and problems are involved. The structure of an interconnection network can be represented by a graph. In the network, vertices represent the processor nodes and edges represent the links between the processor nodes. Graph invariants play a vital feature in graph theory and distinguish the structural properties of graphs and networks. In this paper, we determined the newly introduced topological indices namely, first -degree Zagreb index, first -degree Zagreb index, second -degree Zagreb index, -degree Randic index, -degree atom-bond connectivity index, -degree geometric-arithmetic index, -degree harmonic index and -degree sum-connectivity index for honey comb derived network. In the analysis of the quantitative structure property relationships (QSPRs) and the quantitative structureactivity relationships (QSARs), graph invariants are important tools to approximate and predicate the properties of the biological and chemical compounds. Also, we give the numerical and graphical representation of our outcomes.