图谱理论及其在多智能体系统中的应用

图谱是当前代数图论、组合矩阵论和代数组合论共同关注的一个重要研究课题，具有重要的理论意义和广泛的应用价值，受到了国际组合学界的高度重视。本课题研究图谱的界，图按照它们的谱进行分类和排序，以及图的代数不变量(图的谱)与图的不变量之间的联系，重点是确定图的拟拉普拉斯矩阵特征值（特别是谱半径）的界或极图，以及用图的拟拉普拉斯特征值确定图的某些不变量的界。在应用方面，基于图谱理论提出使得多智能体系统达到一致的脉冲控制协议的设计方案，探讨网络结构与多智能体系统脉冲一致性之间的关系。项目组成员已将图谱理论与多智能体系统的研究相结合，取得的系列结果发表在《Int. J. Systems Sci.》等国际重要学术期刊上。本课题的研究不仅在理论上丰富图谱理论，而且在应用层面上解决某些多智能体系统的脉冲一致性问题，从而促进图谱理论和控制理论的交叉研究。

图谱理论是代数图论的重要研究分支，具有重要的理论意义和广泛的应用价值。本项目主要研究图谱的界、图按照它们的谱进行分类和排序，并基于图谱理论研究多智能体系统的一致性问题，在国内外学术期刊上共发表论文30篇，其中SCI收录26篇，被SCI期刊引用40余次；培养硕士研究生6名，其中3名按期毕业并获硕士学位；4名项目组成员先后成功申请了国家自然科学基金资助项目，其中面上项目一项；举办了第四届全国数论、矩阵与图谱理论研讨会。本项目的研究不仅在理论上丰富了图谱理论，而且在应用层面上解决了某些多智能体系统的一致性问题，从而促进了图谱理论和控制理论的交叉研究，较好地完成了预定任务。代表性结果有：（1）分别给出了不含K2,3-minor图和边最多外平面偶图邻接谱半径的上界；（2）分别给出了n阶平面图和外平面图拟拉普拉斯谱半径的可达上界；（3）根据图的顶点数和边数给出拟拉普拉斯矩阵最小特征值的一个下界, 由此推得de Lima等人的一个猜想成立；（4）对匹配数和控制数给定的非二部连通图类, 分别确定了拟拉普拉斯矩阵最小特征值达到最小的图；（5）研究图的嫁接变换对距离谱半径的影响, 对悬挂点数给定的n阶简单连通图类刻画了距离谱半径达到最小的极图, 并对距离谱半径最大的极图提出一个猜想；（6）根据图的距离度、最大顶点度和团数给出了距离谱展一些下界，分别刻画了n阶连通图、二部图、树、独立数给定的图类中距离谱展最小的极图；（7）刻画了距离矩阵最小特征值在[-2.383, 0] 内的所有图；（8）利用伴随带号有向图的结构性质来研究符号模式矩阵的幂敛性，进一步刻画了本原非可幂矩阵基集, 还刻画了一些特殊矩阵, 发现了更多的“gaps”；（9）给出有向图的拟拉普拉斯矩阵的若干性质，基于拟拉普拉斯谱理论设计使得多智能体系统达到簇反一致的一种新的控制协议，利用拟拉普拉斯矩阵的性质给出系统达到簇反一致性的充分条件，并探讨了网络结构与系统一致性之间的关系；（10）针对一类网络化无源多智能体系统, 基于智能体的局部信息设计脉冲控制协议，并基于图谱理论和无源性原理分别给出该系统在网络拓扑固定、切换两种情形下达到输出一致的充分条件。