多智能体中的图论——图论中的定义（一）

目前人工智能分为：大数据智能，跨媒体智能，群体智能，混合增强智能，自主无人系统五类，若想要深入群体智能则图论的基础是非常必要的！一、引言1.1、专业词汇：distributed network：分布式网络 distributed multiagent network：分布式多智能体网络boids model：柏兹模型（类鸟型） topology：拓扑结构directed ...

autotian

15012人浏览 · 2020-03-21 11:57:32

autotian · 2020-03-21 11:57:32 发布

目前人工智能分为：大数据智能，跨媒体智能，群体智能，混合增强智能，自主无人系统五类，若想要深入群体智能则图论的基础是非常必要的！

1.2.5、图基交互模型（graph-based interaction models）

一、引言

1.1、专业词汇：

distributed network：分布式网络 distributed multiagent network：分布式多智能体网络

boids model：柏兹模型（类鸟型） topology：拓扑结构 directed undirected：有向、无向

separation：分隔 alignment：对准 cohesion：内聚

velocity：速率，速度 flocking：群集 formation：编队

robotic network：机器人网络 resolution：分辨率

1.2、图基交互模型

1.2.1、网络科学关注原因

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

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

1.2.2、Boids Model

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

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

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

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

根据以上原则，杂乱的方向的图形一段时间后变为右图

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

（1）网络系统的组成：

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

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

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

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

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

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

（1）局部通信

局部通信目前收到以下两点的约束

信息交换频道：传送和接受信息需要能量，因此只有在有限范围能够接受信息，在网络中可通过中间节点来扩大传递范围；

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

（2）局部感知

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

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

1.2.5、图基交互模型（graph-based interaction models）

交互几何图形将在多智能体网络系统的分析和综合中扮演重要角色,能够让我们集中研究拓扑结构内部连接所起到的作用

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

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

根据边可能的消失和再现分为三类：静态、动态和随机网络（Static, Dynamic, and Random Networks）

静态网络：边是静态的，即非时变；

动态，状态相关网络：边集可能是时变的，边可能由于网络机构状态的功能消失或再现；

随机网络：由特别的动态网络组成，边是概率发布而非确定性发布。

二、图论

2.1、专业词汇

vertex：顶点 subset：子集 subgraph：子图 adjacent vertex：邻接节点 Connected graph：连通图 connected component：连通分量 Isomorphic：同构 boundary：边界 closure：闭合 degree：度 matrix:度 Degree matrix：度矩阵 adjacency matrix：邻接矩阵 spectral：谱

2.2、图的相关概念

2.2.1、图、边、点的表示

一个有限的，无向的简单图（或简称为图）是建立在一个有限点集上的，即具有有限数量元素的集合。

将该集称为顶点集，用V表示，那么{ $v_{1},v_{2},...,v_{n}$ }的每个元素就是图的顶点。

现在考虑由 ${[V]}^{2}$ 表示的V的2个元素子集的集合。这个集合由以下形式的元素{ $v_{i},v_{j}$ }，其中 i,j=1,2,...,n ，且 $i\neq n$ .有限图定义为 G=(V,E) ,其中V是顶点的有限集合，E是 ${[V]}^{2}$ 边的集合。我们有时将图的顶点和边称为 V(G) 和 E(G) ，并简化边{ $v_{i},v_{j}$ }为 $v_{i}v_{j}$ 或。

图本质上是一个理论对象的集合，但是，它可以方便地以图形表示。图由“点”（如顶点 $v_{i}$ ）以及点之间的线构成。这种图形表示形式引导了许多关于图的定义，见解和观察。例如，当顶点vi和vj之间存在边时，我们称它们为邻接的(adjacent)，并用 $v_{i}\sim v_{j}$ 表示这种关系。在这种情况下，边 $v_{i}v_{j}$ 被称为与顶点 $v_{i}$ 和 $v_{j}$ 的入射（incident）。下图给予了一个无向图的例子， G=(V,E) ，{ $v_{1},v_{2},...,v_{5}$ }，{ $v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{3}v_{5},v_{2}v_{5},v_{4}v_{5}$ }

顶点 $v_{i}$ 的邻接点集合 $N(i)\subseteq V$ ，可理解为集合{ $v_{j}\in V | v_{i}v_{j}\in E$ }。如果 $v_{j}\subseteq N(i)$ 同时可得到 $v_{i}\subseteq N(j)$ ，则可知边是双向的，可知为一个无向图。邻接的概念可随着图的边"移动"。一系列不同的节点构成一个长度为m的路径（path）：

$v_{i_{0}},v_{i_{1}},...,v_{i_{m}}$

设定对于 k=0,1,2,...,m-1 顶点 $v_{i_{k}}$ 和 $v_{i_{k+1}}$ 是邻接的。则 $v_{i_{0}}$ 和 $v_{i_{m}}$ 被称为路径的终点； $v_{i_{1}},v_{i_{2}},...,v_{i_{m-1}}$ 被称为内部顶点。当路径的两个终点为同一个顶点，该路径称为循环。 没有循环的图称为森林。

如果对于图中的每一对顶点，均有一条使这两个点为终点的一条路径，则称图为连通的（connected）。如果不存在此情形则称为非连通（disconnected）。如在上图中即为连通的。将一个连通图称为一个连通分量（connected component），一个分量为图的一个子集。对于一个非连通图存在超过一个连通分量。具有一个分量的深林(forest)称为树（tree）。（连通分量：是联通的子图，其中子图中含有最大顶点数）

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

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

同构（isomorphic）：对于两个图 G=(V,E) 和 $G^{'}=(V^{'},E^{'})$ ，如果拥有相同的点集和边集称为同构，记为： $G\simeq G^{'}$

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

路径图（path graph）：与上诉彼此邻接的 $v_{i_{0}},v_{i_{1}},...,v_{i_{m}}$ 同构

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

下图中分别为完全图和路径图

2.2.2、子图及子图运算

（1）子图及生成子图（生成树及生成森林）

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

事实上对于 $G^{'}=(V^{'},E^{'})$ 是的子图，当 $V \subseteq V^{'}$ 和 $E\subseteq E^{'}$ 时，也称为 $G^{'}$ 的子图。如果对于一个子图如果 $V = V^{'}$ ，可以被定义为一个生成子图（spanning subgraph），对于图的生成树同是也是图的生成子图。

生成树（spanning tree）：包含连通图中所有的顶点；任意两顶点之间有且仅有一条通路；

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

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

（2）子图中的操作

边图：

闭合图：

2.2.3、图概念中的其它定义

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

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

（3）强连接（strongly connected）：有向图中任意两点 $v_{i}$ 和 $v_{j}$ 满足 $v_{i}$ 到 $v_{j}$ 以及 $v_{j}$ 到 $v_{i}$ 都连通（非边），相反则为弱连接（weakly connected）

上图中V = {v1,v2,v3,v4}，边集为{(v1,v3),(v1,v2),(v4,v3)}

2.3、图和矩阵

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

2.3.1、邻接矩阵和度

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