论文部分内容阅读
近30年以来图论有了非常快速的发展,许多工程和应用问题都可以适当的转换为图论问题,并运用图的理论及其算法对其进行深入的讨论和研究。在控制论领域,多智能体网络中的节点与邻节点间的信息互换通常用图的理论来建模。多智能体网络的一致性问题是近年来学者们研究的重点内容之一,正是通过对多智能体网络一致性问题的深入研究而提出了图的确定一致性猜想。本文主要讨论一些特殊的图是否满足确定一致性猜想。 首先研究了一些非常特殊的图,如完全图、树等,确定其满足确定一致性猜想,然后讨论了直径与半径满足特定关系的图,研究直径与半径在什么关系时该图满足确定一致性猜想。对于其它满足确定一致性猜想的图的研究难度相对较大,先讨论了一些阶数较低的图,然后探讨图的一些运算对确定一致性猜想的影响。注意到所有的树都满足确定一致性猜想,我们以树图为基础构造了一类更广泛的图,并且证明了这类图都满足确定一致性猜想。 本文对图的确定一致性猜想进行的研究和探讨,主要得到了以下结论: 首先,证明了所有直径等于两倍半径的图都满足确定一致性猜想;从阶数较低的图出发,证明了五个顶点及以下的所有连通图都满足确定一致性猜想。通过分别证明奇数和偶数多个顶点的路的情况,证明了所有的路都满足确定一致性猜想。 其次,证明了如果图G和H都满足确定一致性猜想,那么G×H也满足确定一致性猜想。证明了若H是图G的连通生成子图,且D(G)=D(H),当H满足确定一致性猜想时,G也满足确定一致性猜想。 最后,通过对于树半径的讨论,证明了树都满足确定一致性猜想。通过对Hn图的发散式推广,构造了一系列特殊的图并证明这些图都满足确定一致性猜想。