研究一致性问题需要的数学工具主要有矩阵论和图论,现代控制理论部分主要涉及到李亚普诺夫判定法。本文涉及的图论及矩阵论知识主要来源于文献[23],我们使用图论及矩阵论对网络拓扑图进行结构分析,李亚普诺夫判定法则用来分析系统的收敛性。
2.1 图论
图是图形结构的简称,图是一种复杂的非线性数据结构。图的二元组定义为:G=(V,E)。其中V(G)表示为图的非空顶点集合,边集E(G)为图的顶点的二元关系集合。图分为有向图、无向图和带权图。对于实际的多智能体系统,假设智能体个数为N,则系统的图的顶点数为N,V(G)中含有N个元素,即可设V(G)= 其中 , , 分别表示系统的N个智能体,假如 到 存在信息流,则 属于边集E(G),加入对于任意的属于E(G)的 都有 也属于E(G),则可称G为无向图,否则G为有向图。
图中与某一顶点有关联的边的数目称为该顶点的度,该顶点入边的数目称为入度,相应的,出边的数目称为出度。加入图G的任意两个顶点之间都存在一个路径,则称图G是联通的。如果一个有向图中任意两个顶点X和Y,都存在X到Y的有向路径及Y到X的有向路径,那么我们可以称此有向图为强连通图,具有强连通性。所以连通的无向图必定是强连通图。文献综述
2.2 矩阵论
本文涉及的矩阵论知识主要为分析图提供帮助,因此此部分与图论紧密结合。
邻接矩阵A:邻接矩阵是表示图中顶点之间连接关系的矩阵。加入图G有N个顶点,则邻接矩阵A为N*N阶矩阵,如果E(G)中存在( ),则A[i,j]=1,否则A[i,j]=0。定义A中对角线上元素为0。所以对于无向图的邻接矩阵A 必定是对称矩阵。
度矩阵D:度矩阵可以分为出度矩阵 和入度矩阵 。我们用如下的两个表达式定义这两个矩阵: , ,
, 。
拉普拉斯矩阵L:在图论研究中,拉普拉斯矩阵是一种重要的矩阵。利用图的度对角矩阵减去图的邻接矩阵即可得到图的拉普拉斯矩阵:
关于拉普拉斯矩阵,有如下定理:
定理1:若无向图G是联通的,则图G的拉普拉斯矩阵L阶数为N-1,即rank(L)=N-1。
在此,我们要引入一个定理:Gersgorin定理。在复平面上L的根都位于以 为圆心, 为半径的封闭圆内,其中 为度矩阵对角线元素中的最大值。