图的确定一致性猜想

发布时间：2018-05-01 16:06

本文选题：连通图 + 正则图　；参考：《电子科技大学》2017年硕士论文

【摘要】：近30年以来图论有了非常快速的发展,许多工程和应用问题都可以适当的转换为图论问题,并运用图的理论及其算法对其进行深入的讨论和研究。在控制论领域,多智能体网络中的节点与邻节点间的信息互换通常用图的理论来建模。多智能体网络的一致性问题是近年来学者们研究的重点内容之一,正是通过对多智能体网络一致性问题的深入研究而提出了图的确定一致性猜想。本文主要讨论一些特殊的图是否满足确定一致性猜想。首先研究了一些非常特殊的图,如完全图、树等,确定其满足确定一致性猜想,然后讨论了直径与半径满足特定关系的图,研究直径与半径在什么关系时该图满足确定一致性猜想。对于其它满足确定一致性猜想的图的研究难度相对较大,先讨论了一些阶数较低的图,然后探讨图的一些运算对确定一致性猜想的影响。注意到所有的树都满足确定一致性猜想,我们以树图为基础构造了一类更广泛的图,并且证明了这类图都满足确定一致性猜想。本文对图的确定一致性猜想进行的研究和探讨,主要得到了以下结论:首先,证明了所有直径等于两倍半径的图都满足确定一致性猜想;从阶数较低的图出发,证明了五个顶点及以下的所有连通图都满足确定一致性猜想。通过分别证明奇数和偶数多个顶点的路的情况,证明了所有的路都满足确定一致性猜想。其次,证明了如果图G和H都满足确定一致性猜想,那么G?H也满足确定一致性猜想。证明了若H是图G的连通生成子图,且(7)(8)(7)(8)G(28)H,当H满足确定一致性猜想时,G也满足确定一致性猜想。最后,通过对于树半径的讨论,证明了树都满足确定一致性猜想。通过对nH图的发散式推广,构造了一系列特殊的图并证明这些图都满足确定一致性猜想。
[Abstract]:Over the past 30 years, graph theory has developed very rapidly. Many engineering and application problems can be converted into graph theory problems, and the graph theory and its algorithm are used to discuss and study graph theory. In the field of cybernetics, the information exchange between nodes and adjacent nodes in multi-agent networks is usually modeled by graph theory. In recent years, the consistency of multi-agent networks is one of the most important topics of scholars. It is through the in-depth study of the consistency of multi-agent networks that the conjecture of graph consistency is put forward. This paper mainly discusses whether some special graphs satisfy the conjecture of deterministic consistency. In this paper, we first study some very special graphs, such as complete graphs, trees, etc., and determine the conjecture of certain consistency. Then we discuss the graphs whose diameters and radii satisfy a particular relation. When the relation between diameter and radius is studied, the graph satisfies the conjecture of definite consistency. For other graphs satisfying certain conjecture it is relatively difficult to study. First some graphs with lower order are discussed and then the influence of some operations of graphs on determining conjecture is discussed. Note that all trees satisfy the conjecture of deterministic consistency. We construct a more extensive class of graphs based on tree graphs and prove that all of these graphs satisfy the conjecture of deterministic consistency. This paper studies and discusses the conjecture of certain consistency of graphs, and obtains the following conclusions: firstly, it is proved that all graphs with diameters equal to two times radius satisfy the conjecture of deterministic consistency. It is proved that all connected graphs with five vertices and below satisfy the conjecture of deterministic consistency. By proving the paths of odd and even vertices respectively, it is proved that all paths satisfy the conjecture of deterministic consistency. Secondly, it is proved that if the graph G and H satisfy the conjecture of deterministic consistency, then GG H also satisfies the conjecture of deterministic consistency. It is proved that if H is a connected generating subgraph of graph G, and G satisfies the conjecture of certain consistency when H satisfies the conjecture of certain consistency. Finally, by discussing the radius of the tree, it is proved that the tree satisfies the conjecture of deterministic consistency. By generalizing the divergence of NH graphs, a series of special graphs are constructed and proved to satisfy the conjecture of deterministic consistency.
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】