1.3 图的表示方法

计算机中的图变化多样。下面总结一些有关图的代数表示方法。邻接矩阵、度矩阵、关联矩阵比较常用，拉普拉斯矩阵涉及图谱论。因为早期的图神经网络都是以图信号分析或图扩散为基础的，所以在图的表示方法中，图谱论相关知识与其他表述方法进行了融合。

1.3.1 图的代数表示

邻接矩阵：如1.2.2节中所定义的，这里不再赘述。

度矩阵：对于简单图G={V,E}，它的度矩阵D是一个对角矩阵，D_ii=d（v_i）。

关联矩阵：对于具有n个节点和m条边的无向图，关联矩阵满足以下条件：

如果G={V,E}是有向图，那么有如下关系，即

拉普拉斯矩阵：对于一个有n个顶点的图G，它的拉普拉斯矩阵定义为

其中，D是图G的度矩阵并且是一个对角矩阵，A是图G的邻接矩阵。L中的元素可以定义为

通常，我们需要将拉普拉斯矩阵归一化，常用的方法有两种。

1）对称归一化拉普拉斯矩阵：

矩阵的元素如下：

2）随机游走归一化拉普拉斯矩阵：

L rw=D-1L=I-D-1A

矩阵的元素如下：

假设图的每个边的权重都是1，可以写出图1-11中图的邻接矩阵、度矩阵及拉普拉斯矩阵。

根据图1-11可知，图G的邻接矩阵A为

图G的度矩阵D为

根据式（1.6）可知，图G的拉普拉斯矩阵L为

通过对L的观察，我们可以看出拉普拉斯矩阵的性质。

●L是对称的。

●L是半正定矩阵（每个特征值λ_i≥0），换句话说，图G={V,E}的拉普拉斯矩阵的特征值是非负的。

●L的每一行、每一列的和都是0。

●L的最小特征值为0。给定一个特征向量v₀=（1,1,…,1）T，根据上一条性质（L的每一行、每一列的和都是0），L_vi=0。

●特征值为0的数目等于图中连通分量的数目。

前文说过拉普拉斯矩阵是半正定矩阵，所以，对于任意一个n维非0向量z，zTLz≥0。式子展开，

式（1.7）被称为拉普拉斯二次型。

对式（1.7）进行数学变形，则

其中，d_i是度矩阵D的对角元素，，w_ij表示v_i、v_j连接时它们之间的权重。显然，结果是大于或等于0的。L是正定矩阵。

1.3.2 图的遍历

图的遍历是指从图中的一个节点出发，按照某种搜索算法沿着图中的边对图中的所有节点进行不重复访问的过程。图的遍历主要有两种算法：深度优先搜索（Depth First Search，DFS）和广度优先搜索（Breadth First Search，BFS）。图的遍历是一种重要的图检索手段。

深度优先搜索是一个递归算法，其算法思想是：从图中任意节点v_i出发，访问它的任意一个邻居节点n₁；再从节点n₁出发，访问n₁的所有邻居节点中未被访问过的节点n₂。然后再从n₂出发，依次访问n₂的所有邻居节点中未被访问过的节点n₃，直到出现某节点不再有邻居节点未被访问过。接着，回退一步到前一次访问过的节点，看是否还有其他未被访问过的邻居节点，如果有，则访问该邻居节点，之后再从该邻居节点出发，执行与前面类似的操作，如果没有，再回退一步执行类似操作。重复上述过程，直到该图中所有节点都被访问过为止。以图1-12为例，我们可以得到如下深度优先搜索序列：v₁→v₂→v₄→v₅→v₃。

广度优先搜索是一个分层搜索过程，其算法思想是：从图中某一节点v_i出发，依次访问v_i的所有未被访问过的邻居节点n₁,n₂,…,n_n，如此一层层执行下去，直到图中所有的节点都被访问过为止。以图1-12为例，我们可以得到如下广度优先搜索序列：v₁→v₂→v₃→v₄→v₅。