多智能体/多机器人网络中的图论法

一、引言

1、网络科学至今受到广泛关注的原因：

（1）大量的学科（尤其生物及材料科学）需要对元素间相互作用在多层级系统中所扮演的角色有更深层次的理解；

（2）科技的发展促进了综合网络工程系统的能力

2、Boids model（boids模型）

boids model由Reynolds结合计算机图形提出，这个模型尝试去寻找社会中鸟群、兽群在集群中排列方式。并提出了以下重要的协议：

（1）分隔原则（separation）：群体内所有个体有避免相邻碰撞的趋势

（2）对准原则（alignment）：群体内个体与其相邻个体速度保持一致的趋势

（3）内聚原则（cohesion）：群体内所有个体有趋向邻近个体的趋势

根据以上原则，可得下图变化

3、网络系统的组成及挑战

（1）网络系统的组成：

动态单元（dynamic units）：彼此之间能够传递和发送信息

信号交换网络（signal exchange network）：能够通过有线或者无线协议实现信息交换

（2）网络系统所遇到的挑战

系统理论不得不混合信息网络数学

面临跨学科结合，如网络几何学

4、通过局部交互的信息交换

（1）局部通信（locality communication）

信息交换频道（communication channels），传送和接受信息需要能量，因此只有在有限范围能够接受信息

可靠的带宽（available bandwidth），如果许多机构同时传播大量的数据，交互频道将会饱和并且会导致通信系统急速的恶化。因此，为了满足带宽要求信息交换应保持过分节俭的

（2）局部感知

a、视觉传感器（vision-based sensor）：能够有很长的有效范围，但为锲型几何区域

b、范围传感器（range sensor）：如声呐、激光雷达（sonars，laser scanners）等，不同传感器有着不同的分辨率和有效范围，为环形全方向

c、触觉传感器（tactile sensor）：能够提供即刻的周边信息

d、单射线范围传感器（single ray range sensor）

5、图基交互模型

交互的几何图形事实上将在多智能体网络系统的分析和综合扮演重要角色，能够让我们聚集在拓扑结构内部连接所起到的作用（topology）

一个具有全方向范围传感器机构网络其相应的机构和交互边显示在下图中

edge（边）：能使信息在边连接的顶点之间传递，分为有向和无向（directed or undirected）,其中有向是带箭头的单向，而无向是指无箭头的双向

静态、动态和随机网络（Static, Dynamic, and Random Networks）

根据边可能的消失和再现分为三类：

静态网络（static network）：边是静态的，即非时变

动态，状态相关网络（Dynamic, State-dependent Networks）：边集可能是时变的，边可能由于网络机构状态的功能消失或再现

随机网络（random network）：有特别的动态网络组成，边是概率发布而非确定性发布

二、图论

1、图与顶点集和边集

（1）图（graphs）及其中的定义

图是由含有有限数量元素的有限点集建立，将该点集设为顶点集（vertex set），并标记为V；

V中的每一个元素都为图中的一个顶点（vertex），表述为V={ ${{v_{1},v_{}2,...,v_{}n}}$ }

若 V用两个子集表示则定义为 $[V]^{}2$ ，这个集合形式为{ $v_{}i,v_{}j$ },其中i,j=1,,2,3,...。

有限图G形式上定义为G=(V,E)，其中V定义为有限顶点的集合，E定义为边的集合，顶点和边集为V(G)和E(G)，并简化edge{vi,vj}为vivj或ij。

若在顶点vi和vj之间存在一条边(edge)，称顶点是邻接的(adjacent)，并记关系为vi~vj。这种情况下，边vivj称为vi和vj之间的关联(incident)

下图为一个无向图，G=(V,E)，其中V={ ${{v_{1},v_{}2,...,v_{}5}}$ },E=( $v_{}1$ $v_{}2$ , $v_{}2$ $v_{}3$ , $v_{}3$ $v_{}4$ , $v_{2}$ $v_{}5$ , $v_{}4$ $v_{}5$ )

$v_{}i$ 在V中的邻接顶点集合为N(i)，可理解为点集{ $v_{}j$ ∈V|vivj∈E}，也就是 $v_{}j$ 中所有点均与 $v_{}i$ 是邻近的。对于无向图，如果 $v_{}j$ ∈N(i)那么 $v_{}i$ ∈N(j)。

对于序列 $v_{i0}$ , $v_{i1}$ , $v_{i2}$ ,..., $v_{im}$ 在上述序列中 $v_{ik}$ 和 $v_{ik+1}$ 是邻接的。 $v_{i0}$ 和 $v_{im}$ 称为路径的终点(end vertices)，vi1...vim-1称为内部顶点（inner vertices）。如果两个终点首尾连在一起称为一个环（cycle）。对于一个图形，没有形成环，叫做一个森林(forest)。

连通图（connected）：对于V(G)中的每一对点，都有一条路使他们成为终点（end vertices），称图G为连通图（connected）。相反，称为非连通图（disconnected）。（连通图相对于无向图而言）

连通分量（connected component）：一个连通图含有一个连通分量，一个非连通图有超过一个分量。只有一个分量的深林叫做一棵树（tree）。（连通分量：是子图，子图是连通的，子图中含有的最大顶点数）

Unlabeld（无标签）：为了更清楚的表述图中的逻辑结构，删除各顶点的明确身份信息；

Labeld（标签）：将无标签图重新给予身份，下面分别为无标签和标签图：

同构（isomorphic）：对于两个图G=(V,E)和G’=(V’,E’)，如果拥有相似的点集和边集称为同构，记为：

完全图（complete graph）：每一个顶点是邻接任何一个其他顶点

路径图（path graph）：与上诉彼此邻接的 $v_{i0}$ , $v_{i1}$ , $v_{i2}$ ,..., $v_{im}$ 同构

环形图（cycle graph）：与路径图不同形成闭环

以下为完全图及路径图：

（2）子图及生成子图

子图：G = (V,E)和其一个子集S⊆V，产生的子图（subgraph）记为 $G_{}S$ =(S, $E_{}S$ )，其中 $E_{}S$ ={{ $v_{}i$ , $v_{}j$ } ∈E|vi,vj∈S}。也就是子图S中的点和边均为G中存在的，如下图中所对应的a、b图。

事实上对于G’=(V’,E’)是G的子图，当V⊆V’and E⊆E’时，也称G为G’的子图。如果对于一个子图V=V’，可以被定义为一个生成子图（spanning subgraph），对于图G的生成树同时也是图G的生成子图。

生成树（spanning tree）：包含连通图中所有的顶点；其中有一顶点可到达任意一顶点；

生成森林（forest）：生成树是对应连通图来说，而生成森林是对应非连通图来说的。非连通图可分解为多个连通分量，而每个连通分量又各自对应多个生成树（至少是 1 棵），因此与整个非连通图相对应的，是由多棵生成树组成的生成森林。

图a中包含有子图b；c为b的边界图（boundary），即为与子图b存在边的点和其够成的边；图d为子图b的闭合图（closure），即为子图b与其边界图的结合。

2、有向图和赋权图

（1）赋权图（weighted graphs）：图G中的每一条边都相应地赋有一个数值 $w_{_{ij}}$ ，则称G为赋权图，记为G = (V,E,w)。

（2）有向图（digraphs）：当给图中的边赋予方向，即变为有向图，记为D(V,E)。其中(vi,vj)表示i为箭头的尾部，j为箭头的头部，即为指向j的箭头方向。

强连接（strongly connected）：有向图中任意两点vi和vj满足vi到vj以及vj到vi都连通（非边），相反则为弱连接（weakly connected）

相似地，D = (V,E),其子图D’ = (V’, E’), is such that V’⊆ V and E’⊆ E.

上图中V = { $v_{}1$ , $v_{}2$ , $v_{}3$ , $v_{}4$ }，边集为{( $v_{}1$ , $v_{}3$ ),( $v_{}1$ , $v_{}2$ ),( $v_{}4$ , $v_{}3$ )}

3、图和矩阵

上诉中，确立了图形用顶点和边的表述形式，下面将会建立图形和矩阵的表述形式。

（1）邻接矩阵和度

对于一个无向图G，其内在顶点 $v_{}i$ 的度(degree)，表示为d(vi)，其值为邻接点集N(i)的基数，即为 $v_{}i$ 在G中邻接顶点数的个数。下图中

d( $v_{}1$ )=1, d( $v_{}2$ )=3, d( $v_{}3$ )=3, d( $v_{}4$ )=2, d( $v_{}5$ )=3

一个图形的度序列是其顶点度的集合，G的度矩阵(degree matrix)，∆(G)是一个对角矩阵，在对角线上包含了G中的顶点度，即：

邻接矩阵A(G)(adjacency matrix)是对称的n×n矩阵,邻接矩阵的值为：

上图中的度矩阵和邻接矩阵为：

（2）关联矩阵（incident matrix）

关联矩阵（incident matrix） D(D)：假设在具有n个顶点和m条边的有向矩阵 $G_{}0$ 中的任意一条边都赋予标签，则D( $G_{}0$ )为一个n×m矩阵被定义为：

即对于dij当箭头的头部指向vi时dij为1，箭头的头部指向j时为-1.

下图关联矩阵为：

上诉的关联矩阵可以看到，每一列的和均为0，这位关联矩阵的共同属性，这是由于每一列为一条有向边，而有向边又对应着头和尾巴（1和-1）。

定义弱连接有向图的循环空间(cycle space)为关联矩阵的零空间(null space)，即为D(D)z = 0中z列向量的集合。

定义：假定在关联矩阵D(D)中，一个符号路径向量(signed path vector)是向量z在D中所对应的一条路径（非边），z中第i个指数为+1表示第i条边(edge)是积极遍历（traversed positively）（符合路径遍历方向），-1为消极遍历，0为未在该条路径中使用。

公理：有向图中，一个符号向量Z所对应的通路（path），有着不同的起点和终点，向量y=D(G)z中，第i个元素，其值为1则为起点，值为-1则为终点，0为其他。

定理：一个弱连接连通有向图D，其关联矩阵D(D)的零空间(null space)是由D的循环（cycle）所对应的符号向量路径所决定的。

4、图的拉普拉斯表述

（1）图拉普拉斯矩阵

图G的另一个矩阵描述为图拉普拉斯矩阵（graph laplacian），L(G)。

图拉普拉斯矩阵最直接的定义是对于无向图G的拉普拉斯矩阵：（度矩阵-邻接矩阵）

对于有向图，图G的拉普拉斯矩阵为：

其中D(GO)为GO所对应的关联矩阵，这个定义揭露了图拉普拉斯矩阵实为一个对称且正半定矩阵。

上诉对于有向图和无向图的定义是等效的，并且在无向图计算公式的定义中不需要方向。我们将习惯采用D(G)即关联矩阵的方法来计算有向图。抛开方向，有时采取上诉两个定义中的一个对于图的拉普拉斯矩阵是有用的。

赋权图拉普拉斯矩阵：

W为一个mXm的对角矩阵，w(ei),i = 1,...,m，位于对角线上。

（2）边拉普拉斯

边拉普拉斯（edge laplacian）：对于一个任意方向的图G，边拉普拉斯定义为

两个Le(G)关键线性代数特征如下：Le(G)非零特征值与L(G)非零特征值相同（转置矩阵特征值与原矩阵特征值相同）；Le(G)与L(G)非零特征值等于D(G)中非零奇异值的平方。

具有p个连通分量Gi的图G，其关联矩阵为：

图G的边拉普拉斯矩阵具有块对角线矩阵的形式：

有向图拉普拉斯（在两个矩阵计算中不包含由于出度导致的度减少）

定义有向赋权图的邻接矩阵为：（即对于wij，箭头指向i为正）

对于对角度矩阵，定义为：

din(v)是顶点v的赋权内度（in-degree）:（在i出各箭头边权值相加，箭头指向i为正）

记度矩阵为：（即为A(D)与1列向量的对角阵，这是由于A(D)每一行相加即为dii的权值和）

对应的权值拉普拉斯（内度 in-degree）定义为：

对于所有的有向图，均有（即全部为1的向量是L(D)矩阵中0特征值所对应的特征向量）（N是指矩阵的0空间，即Av=0，由于特征值及其特征向量的计算公式固有v为0特征值所对应的特征向量）

在多智能体网络中我们选择入度（In-degree）而非出度（out-degree），这是由于入度显示机构被其他影响，而出度显示影响其他机构。

（3）代数和谱图论

事实上，对于度、邻接、关联、拉普拉斯矩阵特征值的研究属于图论中的子学科，名为谱图论（spectral graph theory）

图拉普拉斯L(G)是对称且半正定的（特征值均为非负），因此其特征值可写为：

其中

理论：图G是连通图的充要条件为