文档介绍：邻接矩阵及拉普拉斯矩阵
邻接矩阵及拉普拉斯矩阵
邻接矩阵及拉普拉斯矩阵
邻接矩阵及拉普拉斯矩阵
邻接矩阵
图的邻接矩阵能够很方便的表示图的很多信息,且具有描述简单、直观的特点。无向简单图的邻接矩阵定义如下:设图G ＝ (Ｖ,E ) ,有n ≥ １　个顶点,分别为：则G 的邻接矩阵Ａ是按如下定义的一个n阶方阵.
直观上，由邻接矩阵我们可以得到如下信息：
1．邻接矩阵是一个0，1的对称矩阵，对角线元素为0。
2．矩阵的各个行和(列和）是各个顶点的度。所有元素相加和为边数的二倍。
3．　An　的i，　j 位置元素为之间的长度等于n的通路的数目,而i,,i位置元素是的度;的i，i位置元素是含的三角形数目的二倍.
4．由3。设，,则说明与之间没有通路。由此我们可以得到一个判断图Ｇ的联通新的重要准则:对于矩阵,若S中所有元素都非零则Ｇ是连通图，否则图G是非连通图。
5．设Ｇ是连通图,将矩阵Ａ的所有是1的元素换成−１,并且把对角线元素换成相应顶点的度,,则所得到的矩阵的任何元素的代数余子式都相等，等于Ｇ的生成树的数目．
邻接矩阵及拉普拉斯矩阵
邻接矩阵及拉普拉斯矩阵
邻接矩阵及拉普拉斯矩阵
拉普拉斯矩阵
Ｌaｐlaｃian matrｉx的定义
拉普拉斯矩阵（Lａplaciａn ｍatrｉx)）,也称为基尔霍夫矩阵, 是表示图的一种矩阵。给定一个有n个顶点的图,其拉普拉斯矩阵被定义为:
ﻩ
其中为图的度矩阵,为图的邻接矩阵。
,如下：
 　  把此“图”转换为邻接矩阵的形式,记为：
    把的每一列元素加起来得到个数，然后把它们放在对角线上（其它地方都是零),组成一个的对角矩阵,记为度矩阵，如下图所示：
   