多智能体/多机器人网络中的图论法
一、引言
1、网络科学至今受到广泛关注的原因：
（1）大量的学科（尤其生物及质料科学）需要对元素间相互作用在多层级体系中所扮演的角色有更深层次的理解；
（2）科技的发展促进了综合网络工程体系的能力
2、Boids model（boids模子）
boids model由Reynolds联合计算机图形提出，这个模子尝试去探求社会中鸟群、兽群在集群中分列方式。并提出了以下告急的协议：
（1）分隔原则（separation）：群体内所有个体有克制相邻碰撞的趋势
（2）对准原则（alignment）：群体内个体与其相邻个体速率保持一致的趋势
（3）内聚原则（cohesion）：群体内所有个体有趋向邻近个体的趋势
根据以上原则，可得下图厘革
https://i-blog.csdnimg.cn/blog_migrate/5e718f09e1f91e8f9ec26440e8f2a3fb.png
3、网络体系的组成及挑战
（1）网络体系的组成：
动态单位（dynamic units）：彼此之间可以或许传递和发送信息
信号互换网络（signal exchange network）：可以或许通过有线大概无线协议实现信息互换
（2）网络体系所遇到的挑战
体系理论不得不混合信息网络数学
面对跨学科联合，如网络多少学
4、通过局部交互的信息互换
（1）局部通讯（locality communication）
信息互换频道（communication channels），传送和接受信息需要能量，因此只有在有限范围可以或许接受信息
可靠的带宽（available bandwidth），如果许多机构同时流传大量的数据，交互频道将会饱和并且会导致通讯体系急速的恶化。因此，为了满足带宽要求信息互换应保持过分节俭的
（2）局部感知
https://i-blog.csdnimg.cn/blog_migrate/c28ed20b1489a32700be7bb495e80737.png
a、视觉传感器（vision-based sensor）：可以或许有很长的有效范围，但为锲型多少地区
b、 范围传感器（range sensor）：如声呐、激光雷达（sonars，laser scanners）等，不同传感器有着不同的分辨率和有效范围，为环形全方向
c、触觉传感器（tactile sensor）：可以或许提供马上的周边信息
d、单射线范围传感器（single ray range sensor）
5、图基交互模子
交互的多少图形究竟大将在多智能体网络体系的分析和综合扮演告急角色，可以或许让我们聚集在拓扑布局内部连接所起到的作用（topology）
一个具有全方向范围传感器机构网络其相应的机构和交互边体如今下图中
https://i-blog.csdnimg.cn/blog_migrate/b371ccbec38259ab1d0916d00975fb28.png
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={https://i-blog.csdnimg.cn/blog_migrate/224e5f822929154fecff16e02300f116.gif}
若 V用两个子集表现则定义为https://i-blog.csdnimg.cn/blog_migrate/c8f9cd9a1969b6365ca95a142117dacb.gif，这个集合情势为{https://i-blog.csdnimg.cn/blog_migrate/cc022594e0f6526044b893f9cd8e40f3.gif},其中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={https://i-blog.csdnimg.cn/blog_migrate/1196b65a06e9049f0e9e0db9ca2ec3f4.gif},E=(https://i-blog.csdnimg.cn/blog_migrate/deb6d920952ab0225f8c3c9fccd775cd.gifhttps://i-blog.csdnimg.cn/blog_migrate/7f01d62c5fe26762b56769368a8ec7d7.gif,https://i-blog.csdnimg.cn/blog_migrate/7f01d62c5fe26762b56769368a8ec7d7.gifhttps://i-blog.csdnimg.cn/blog_migrate/61da69b88628fb241c59ed7aac34fd1a.gif,https://i-blog.csdnimg.cn/blog_migrate/61da69b88628fb241c59ed7aac34fd1a.gifhttps://i-blog.csdnimg.cn/blog_migrate/8768a80b57dcfbcf6044c128c79c5d93.gif,https://i-blog.csdnimg.cn/blog_migrate/0d1494febf5cd57e27340ed3d42ba3a3.gifhttps://i-blog.csdnimg.cn/blog_migrate/f0e3cc1f0fa597449063dd967a2cf403.gif,https://i-blog.csdnimg.cn/blog_migrate/8768a80b57dcfbcf6044c128c79c5d93.gifhttps://i-blog.csdnimg.cn/blog_migrate/f0e3cc1f0fa597449063dd967a2cf403.gif)
https://i-blog.csdnimg.cn/blog_migrate/44dabe0bbebaa7f0a92a9cd749605e11.png
https://i-blog.csdnimg.cn/blog_migrate/dae13d4f9a2b061a3f7af98edac07fb6.gif在V中的邻接顶点集合为N(i)，可理解为点集{https://i-blog.csdnimg.cn/blog_migrate/38bbdbce0d2e9b58d39743c551e49e1e.gif∈V|vivj∈E}，也就是https://i-blog.csdnimg.cn/blog_migrate/38bbdbce0d2e9b58d39743c551e49e1e.gif中所有点均与https://i-blog.csdnimg.cn/blog_migrate/dae13d4f9a2b061a3f7af98edac07fb6.gif是邻近的。对于无向图，如果https://i-blog.csdnimg.cn/blog_migrate/38bbdbce0d2e9b58d39743c551e49e1e.gif∈N(i)那么https://i-blog.csdnimg.cn/blog_migrate/dae13d4f9a2b061a3f7af98edac07fb6.gif∈N(j)。
对于序列 https://i-blog.csdnimg.cn/blog_migrate/9870cf9baa3643b1d2ea9ea6308e9d26.gif,https://i-blog.csdnimg.cn/blog_migrate/d6759ea8853847ff0871f4a2f467d56b.gif,https://i-blog.csdnimg.cn/blog_migrate/59466c949943c98a4854e3baabd5a29a.gif,...,https://i-blog.csdnimg.cn/blog_migrate/aad82bdbdd4aa8ca29f279197cf1ba84.gif 在上述序列中https://i-blog.csdnimg.cn/blog_migrate/3a25085e8c2e4a0952eef1a047b5d881.gif和https://i-blog.csdnimg.cn/blog_migrate/2b4ed62661e319c792650af25465d945.gif是邻接的。https://i-blog.csdnimg.cn/blog_migrate/9870cf9baa3643b1d2ea9ea6308e9d26.gif和https://i-blog.csdnimg.cn/blog_migrate/aad82bdbdd4aa8ca29f279197cf1ba84.gif称为路径的止境(end vertices)，vi1...vim-1称为内部顶点（inner vertices）。如果两个止境首尾连在一起称为一个环（cycle）。对于一个图形，没有形成环，叫做一个丛林(forest)。
连通图（connected）：对于V(G)中的每一对点，都有一条路使他们成为止境（end vertices），称图G为连通图（connected）。相反，称为非连通图（disconnected）。（连通图相对于无向图而言）
连通分量（connected component）：一个连通图含有一个连通分量，一个非连通图有凌驾一个分量。只有一个分量的深林叫做一棵树（tree）。（连通分量：是子图，子图是连通的，子图中含有的最大顶点数）
Unlabeld（无标签）：为了更清晰的表述图中的逻辑布局，删除各顶点的明白身份信息；
Labeld（标签）：将无标签图重新给予身份，下面分别为无标签和标签图：
https://i-blog.csdnimg.cn/blog_migrate/37cf519cb4ee723aad02170288435a58.pnghttps://i-blog.csdnimg.cn/blog_migrate/6b65d6a0bc34eb48521c61a3c038c94c.png
同构（isomorphic）：对于两个图G=(V,E)和G’=(V’,E’)，如果拥有相似的点集和边集称为同构，记为：https://i-blog.csdnimg.cn/blog_migrate/2ec32f6eb73dbff7b7603e22d862ecda.png
完全图（complete graph）：每一个顶点是邻接任何一个其他顶点
路径图（path graph）：与上诉彼此邻接的 https://i-blog.csdnimg.cn/blog_migrate/9870cf9baa3643b1d2ea9ea6308e9d26.gif,https://i-blog.csdnimg.cn/blog_migrate/d6759ea8853847ff0871f4a2f467d56b.gif,https://i-blog.csdnimg.cn/blog_migrate/59466c949943c98a4854e3baabd5a29a.gif,...,https://i-blog.csdnimg.cn/blog_migrate/aad82bdbdd4aa8ca29f279197cf1ba84.gif同构
环形图（cycle graph）：与路径图不同形成闭环
以下为完全图及路径图：
https://i-blog.csdnimg.cn/blog_migrate/6c27dcdb4b43e5743fa2ed896ff06a06.png
（2）子图及生成子图
子图：G = (V,E)和其一个子集S⊆V，产生的子图（subgraph）记为https://i-blog.csdnimg.cn/blog_migrate/dea298cc19f138b6202e52d8a9d1ae1b.gif =(S,https://i-blog.csdnimg.cn/blog_migrate/02df4c02a934a98cf8ab34ca5f85bb13.gif)，其中https://i-blog.csdnimg.cn/blog_migrate/02df4c02a934a98cf8ab34ca5f85bb13.gif={{https://i-blog.csdnimg.cn/blog_migrate/dae13d4f9a2b061a3f7af98edac07fb6.gif,https://i-blog.csdnimg.cn/blog_migrate/38bbdbce0d2e9b58d39743c551e49e1e.gif} ∈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 棵），因此与整个非连通图相对应的，是由多棵生成树组成的生成丛林。
https://i-blog.csdnimg.cn/blog_migrate/e2e3c815432a2abd41d5b745ee3d5426.png
图a中包含有子图b；c为b的边界图（boundary），即为与子图b存在边的点和其够成的边；图d为子图b的闭合图（closure），即为子图b与其边界图的联合。
2、有向图和赋权图
（1）赋权图（weighted graphs）：图G中的每一条边都相应地赋有一个数值https://i-blog.csdnimg.cn/blog_migrate/ab1a21e1a8cc6525531ae961f2e8c573.gif，则称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.
https://i-blog.csdnimg.cn/blog_migrate/b27ccdc0a28cf924260c0612562b705d.png
上图中V = {https://i-blog.csdnimg.cn/blog_migrate/deb6d920952ab0225f8c3c9fccd775cd.gif,https://i-blog.csdnimg.cn/blog_migrate/7f01d62c5fe26762b56769368a8ec7d7.gif,https://i-blog.csdnimg.cn/blog_migrate/61da69b88628fb241c59ed7aac34fd1a.gif,https://i-blog.csdnimg.cn/blog_migrate/8768a80b57dcfbcf6044c128c79c5d93.gif}，边集为{(https://i-blog.csdnimg.cn/blog_migrate/deb6d920952ab0225f8c3c9fccd775cd.gif,https://i-blog.csdnimg.cn/blog_migrate/61da69b88628fb241c59ed7aac34fd1a.gif),(https://i-blog.csdnimg.cn/blog_migrate/deb6d920952ab0225f8c3c9fccd775cd.gif,https://i-blog.csdnimg.cn/blog_migrate/7f01d62c5fe26762b56769368a8ec7d7.gif),(https://i-blog.csdnimg.cn/blog_migrate/8768a80b57dcfbcf6044c128c79c5d93.gif,https://i-blog.csdnimg.cn/blog_migrate/61da69b88628fb241c59ed7aac34fd1a.gif)}
3、图和矩阵
上诉中，确立了图形用顶点和边的表述情势，下面将会创建图形和矩阵的表述情势。
（1）邻接矩阵和度
对于一个无向图G，其内涵顶点https://i-blog.csdnimg.cn/blog_migrate/dae13d4f9a2b061a3f7af98edac07fb6.gif的度(degree)，表现为d(vi)，其值为邻接点集N(i)的基数，即为https://i-blog.csdnimg.cn/blog_migrate/dae13d4f9a2b061a3f7af98edac07fb6.gif在G中邻接顶点数的个数。下图中
d(https://i-blog.csdnimg.cn/blog_migrate/deb6d920952ab0225f8c3c9fccd775cd.gif)=1, d(https://i-blog.csdnimg.cn/blog_migrate/7f01d62c5fe26762b56769368a8ec7d7.gif)=3, d(https://i-blog.csdnimg.cn/blog_migrate/61da69b88628fb241c59ed7aac34fd1a.gif)=3, d(https://i-blog.csdnimg.cn/blog_migrate/8768a80b57dcfbcf6044c128c79c5d93.gif)=2, d(https://i-blog.csdnimg.cn/blog_migrate/f0e3cc1f0fa597449063dd967a2cf403.gif)=3
https://i-blog.csdnimg.cn/blog_migrate/41c34ee19e8cf094c3f7fabab9322e77.png
一个图形的度序列是其顶点度的集合，G的度矩阵(degree matrix)，∆(G)是一个对角矩阵，在对角线上包含了G中的顶点度， 即：
https://i-blog.csdnimg.cn/blog_migrate/000b3199a0be5eb7c163255754607e21.png
邻接矩阵A(G)(adjacency matrix)是对称的n×n矩阵,邻接矩阵的值为：
https://i-blog.csdnimg.cn/blog_migrate/90bc1b714f061a34ee5ea6e4fb7a54ed.png
上图中的度矩阵和邻接矩阵为：
https://i-blog.csdnimg.cn/blog_migrate/8cf64b4191835b3d8aa9a3c236754634.png
（2）关联矩阵（incident matrix）
关联矩阵（incident matrix） D(D)：假设在具有n个顶点和m条边的有向矩阵https://i-blog.csdnimg.cn/blog_migrate/956d12c3c9db1504ea3361fd05a4e257.gif中的恣意一条边都赋予标签，则D(https://i-blog.csdnimg.cn/blog_migrate/956d12c3c9db1504ea3361fd05a4e257.gif)为一个n×m矩阵被定义为：https://i-blog.csdnimg.cn/blog_migrate/8f653f626e9452c623672ebfd517ec69.png
即对于dij当箭头的头部指向vi时dij为1，箭头的头部指向j时为-1.
下图关联矩阵为：
https://i-blog.csdnimg.cn/blog_migrate/ab8148e559deeed39acc0fc48a508800.pnghttps://i-blog.csdnimg.cn/blog_migrate/53311f4d6bc7f2e6c476347d86481673.png
上诉的关联矩阵可以看到，每一列的和均为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的拉普拉斯矩阵：（度矩阵-邻接矩阵）
https://i-blog.csdnimg.cn/blog_migrate/84b77f0c9aa8fdb2833453b71b35ce48.png
对于有向图，图G的拉普拉斯矩阵为：
https://i-blog.csdnimg.cn/blog_migrate/e272f494f1d3ddd4380906d57646a197.png
其中D(GO)为GO所对应的关联矩阵，这个定义揭露了图拉普拉斯矩阵实为一个对称且正半定矩阵。
上诉对于有向图和无向图的定义是等效的，并且在无向图计算公式的定义中不需要方向。我们将风俗采用D(G)即关联矩阵的方法来计算有向图。抛开方向，偶然采取上诉两个定义中的一个对于图的拉普拉斯矩阵是有用的。
赋权图拉普拉斯矩阵：
https://i-blog.csdnimg.cn/blog_migrate/efb5a517c46f9fbbb971e01efe297829.png
W为一个mXm的对角矩阵，w(ei),i = 1,...,m，位于对角线上。
（2）边拉普拉斯
边拉普拉斯（edge laplacian）：对于一个恣意方向的图G，边拉普拉斯定义为
https://i-blog.csdnimg.cn/blog_migrate/8f653f626e9452c623672ebfd517ec69.png
两个Le(G)关键线性代数特性如下：Le(G)非零特性值与L(G)非零特性值雷同（转置矩阵特性值与原矩阵特性值雷同）；Le(G)与L(G)非零特性值等于D(G)中非零奇异值的平方。
具有p个连通分量Gi的图G，其关联矩阵为：
https://i-blog.csdnimg.cn/blog_migrate/7d6452c267514cfc5ae06f4facea9d67.png
图G的边拉普拉斯矩阵具有块对角线矩阵的情势：
https://i-blog.csdnimg.cn/blog_migrate/8e0a24a3dd739fa74de88cd18c97e4b5.png
[*]有向图拉普拉斯（在两个矩阵计算中不包含由于出度导致的度淘汰）
定义有向赋权图的邻接矩阵为：（即对于wij，箭头指向i为正）
https://i-blog.csdnimg.cn/blog_migrate/ab7622d035e06f14a6275d911be875be.png
对于对角度矩阵，定义为：
https://i-blog.csdnimg.cn/blog_migrate/e6b01e8244c364b9e3f0a385baa2fa41.png
din(v)是顶点v的赋权内度（in-degree）:（在i出各箭头边权值相加，箭头指向i为正）
https://i-blog.csdnimg.cn/blog_migrate/2a9a1657bf4f7ecf0d7e012d371bb57f.png
记度矩阵为：（即为A(D)与1列向量的对角阵，这是由于A(D)每一行相加即为dii的权值和）
https://i-blog.csdnimg.cn/blog_migrate/f3c3046dde6cfcf7cc593ac9576bf74f.png
对应的权值拉普拉斯（内度 in-degree）定义为：
https://i-blog.csdnimg.cn/blog_migrate/ff658b5a1b5704cc99a286183511f28d.png
对于所有的有向图，均有（即全部为1的向量是L(D)矩阵中0特性值所对应的特性向量）（N是指矩阵的0空间，即Av=0，由于特性值及其特性向量的计算公式固有v为0特性值所对应的特性向量）
https://i-blog.csdnimg.cn/blog_migrate/f3c3046dde6cfcf7cc593ac9576bf74f.png
在多智能体网络中我们选择入度（In-degree）而非出度（out-degree），这是由于入度体现机构被其他影响，而出度体现影响其他机构。
（3）代数和谱图论
究竟上，对于度、邻接、关联、拉普拉斯矩阵特性值的研究属于图论中的子学科，名为谱图论（spectral graph theory）
图拉普拉斯L(G)是对称且半正定的（特性值均为非负），因此其特性值可写为：
https://i-blog.csdnimg.cn/blog_migrate/2111d3bf81a8635dcdfcf88489ea3162.png
其中 https://i-blog.csdnimg.cn/blog_migrate/42bcc51db687bd798d7679f8e521dfbb.png
理论：图G是连通图的充要条件为 https://i-blog.csdnimg.cn/blog_migrate/4dee4815797070905a7fdf38585be787.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]