邻接矩阵及拉普拉斯矩阵

邻接矩阵及拉普拉斯矩阵邻接矩阵及拉普拉斯矩阵 邻接矩阵邻接矩阵 图的邻接矩阵能够很方便的表示图的很多信息 且具有描述简单 直观的特点 无向 简单图的邻接矩阵定义如下 设图 G V E 有 n 1 个顶点 分别为 则 G 的邻接矩阵 A 是按如下定义的一个 n 阶方阵 12 n v vv 1v aa 0 ij ij n nij A v E 否则 直观上 由邻接矩阵我们可以得到如下信息 1 邻接矩阵是一个 0 1 的对称矩阵 对角线元素为 0 2 矩阵的各个行和 列和 是各个顶点的度 所有元素相加和为边数的二倍 3 An 的 i j 位置元素为之间的长度等于 n 的通路的数目 而 i j 位置的元素为 vi j 与v 到自身的回路的数目 特别的的 i i 位置元素是的度 的 i i 位置元素是含的vi 2 Avi 3 Avi 三角形数目的二倍 4 由 3 设 则中位置元素为顶点与之间长度小于或 1 1 l k l k SAl l S i j S l i ji vvj 等于 l 的通路的个数 若 则说明与之间没有通路 由此我们可以得到一个 n 1 S0 i j i vvj 判断图 G 的联通新的重要准则 对于矩阵 若 S 中所有元素都非零则 G 是连 1 l k l k SA 通图 否则图 G 是非连通图 5 设G 是连通图 将矩阵 A的所有是 1 的元素换成 1 并且把对角线元素换成相 ii a 应顶点的度 则所得到的矩阵的任何元素的代数余子式都相等 等于G i vi 1 2 n 的生成树的数目 拉普拉斯矩阵拉普拉斯矩阵 Laplacian matrix 的定义的定义 拉普拉斯矩阵 Laplacian matrix 也称为基尔霍夫矩阵 是表示图的一种矩阵 给定 一个有 n 个顶点的图 其拉普拉斯矩阵被定义为 V E G LDW 其中为图的度矩阵 为图的邻接矩阵 举个例子 给定一个简单的图 如下 把此 图 转换为邻接矩阵邻接矩阵的形式 记为 把的每一列元素加起来得到个数 然后把它们放在对角线上 其它地方都是零 组成一个的对角矩阵 记为度矩阵度矩阵 如下图所示 根据拉普拉斯矩阵的定义 可得拉普拉斯矩阵 为 拉普拉斯矩阵的性质拉普拉斯矩阵的性质 介绍拉普拉斯矩阵的性质之前 首先定义两个概念 如下 对于邻接矩阵 定义图中 A 子图与 B 子图之间所有边的权值之和如下 A B ij i A j B Ww 其中 定义为节点 i 到节点 j 的权值 如果两个节点不是相连的 权值为零 ij w 与某结点邻接的所有边的权值和定义为该顶点的度 d 多个 d 形成一个度矩阵 对角阵 1 n iij j dw 拉普拉斯矩阵 具有如下性质 是对称半正定矩阵 即 的最小特征值是 0 相应的特征向量是 1 证明 L 10 1 1 100 1LD W 有 n 个非负实特征值 12n 0 且对于任何一个属于实向量 有以下式子成立 n fR 2 1 1 2 N ijij i j f Lfwff 其中 证明 LDW 1 n iij j dw A B ij i A j B Ww 2 1 1 2 22 1 11 1 11 2 22 nn iiij