令 表示一个图，其中 是一个有限的非空的节点集， 是边集。图 的一条边记为 ，表示这条边是从节点 开始到节点 结束的，这同时也意着节点 可以直接接收到节点 的信息。在这种情况下，节点 称为节点 的父亲节点，而节点 称为节点 的孩子节点。所有节点 的邻居节点组成的集合记为 。当且仅当 的同时也意着 ，则图 是无向图，否则，图 是有向图。一条有向路径是一组边的序列，形如 。一条无向路径也是类似定义的。在无向图 中，如果从节点 到节点 有路径，则称 和 是连通的。如果对于图中任意两个顶点都是连通的，则称 是连通图。在有向图中，如果对任意两个节点 、 ，都有从 到 的路径和从 到 的路径，则称 是强连通图。

2.2  矩阵知识

为了方便描述图中边和节点的关系，我们引入了邻接矩阵的概念。图 的带权重的邻接矩阵 定义如下：如果 ，则 ，否则， 。由于不存在节点自身到自身的封闭路径，所以 。无向图对应的邻接矩阵是对称的。入度矩阵定义为 ，若图 是对称的，则有每个节点的出度等于入度，这时称 为度矩阵。如果一个图对应的邻接矩阵的出度和入度相等，则称该图为平衡图。

另一种描述节点与边之间的关系的矩阵是图 的拉普拉斯矩阵 ，定义为：若 ，则有 ，否则 。即 。在无向图中，拉普拉斯矩阵是对称半正定的，但是有向图并不具备此性质。 

拉普拉斯矩阵具有三大特性，这些特性是研究有限时间一致性协议收敛的重要因素。

性质一：0是矩阵 的特征值，并且 为对应的特征向量，其中 ； 

性质二：如果图 是强连通图，则0为矩阵 的单一特征值；  

性质三：如果图 是连通且对称的，则矩阵 对称且正半定，所有的特征值都为实数且非负，可以写成以下形式： 。