当前课程知识点：线性代数(2) > 第八讲：图与网络 > 8.2 图和矩阵 > 8.2 图和矩阵
为了使用刚才那个框架呢
讨论欧姆定律的向量形式呢
我们首先来看一下图和矩阵
一般的定义
那么我们来看一下
一个图是由一些顶点
和连接顶点的边组成
比如下面这个图
这个图有四个顶点
那么顶点和边
我们用不同的数字指标表示
顶点我们加了一个圈
数字我们没有加圈
如果若干条边构成的连通子图
就为路
比如说从这个第一点走若干步
走2 3 再走4到2
那么这就构成一条路
那么长度为1的路呢
就是我们的边
那么在这个图里面呢
我们讨论的图
不允许一个顶点到自己的边
我们把这张图可以记成
G=（V，E）V就表示顶点
E就表示边
那么一般来说呢
在现在这个图里面
顶点就是① ② ③ ④
而边就是1 2 3 4 5 6
所以一个图呢
两个要素 顶点和边
那么如果是带方向呢
就叫定向图
每点我规定一个方向
那么整个图就是带方向的图
叫定向图
给定一个电路图呢
我们可以把顶点和边抽象出来
这样
我们就可以得到一个定向图
比如说左边这个电路图呢
我们可以抽象出五个顶点
而剩下的呢
凡是有一个电子器件在的
那么我们就形成一条边
在这个顶点和这个顶点之间呢
这是第五个顶点
这是第一个顶点
这是第三个顶点 这是第二个
通过这样子呢
我们可以得到一个
电路图的抽象的版本
这个图里面的顶点呢
就是① ② ③ ④ ⑤
边就是8条
那么对于这样一个图呢
我们可以讨论它的回路
一个回路是什么呢
一个回路呢
它是原来这个图的一个子图
它的边构成的路呢
起始点和终点是相同的
比如上面这个图
我们看从①到②再到⑤再到①
这就是一条回路
而注意
我们回路并不要求方向
比如说从①到②再到③
然后⑤再到①
这也是一条回路
那么大家看在③和⑤这块呢
它的箭头方向
并不影响我们考虑回路
我们回路的时候呢并不考虑
这个一定要按方向是一致的
好 下面我们来看一下
给定一张图呢
我们可以相关若干种矩阵
那么在这里面
我们主要讨论三种矩阵
一个定向图的邻接矩阵
迎接矩阵和拉普拉斯矩阵
我们先来看
一个定向图的关联矩阵是什么
关联矩阵
它的每一行对应着一条边
我们来看下面这个图
这个图有四个顶点七条边
它对应的关联矩阵
是左边这个样子
那我们来看一下关联矩阵的结构
它的每一列就对应着
跟①这个顶点相关的一些边
比如说跟①这个顶点相关的有
1这条边 2这条边 4这条边
7这条边
那么我们可以看到
在第一列中就有四个数是非零的
其他都是零
那么第一个数-1
-1表示的是第一条边的1
是从①这儿出去的
所以我们用4 1表示
那么4这个也是-1
②这个也是-1
就是从①这个顶点呢
有三条边是出去的
就是1 2 4这三条边
7这条边是从②进入①的
所以呢它是1
而这个关联矩阵
那么关联矩阵的每一条
每一个行代表什么呢
代表的是一条边
我们来看它的每一行呢
具有两个非零元
每一行只有两个非零元1和-1
比如说第一行-1代表的是
从①这个顶点出发到②这个顶点
又比如说第6条
第6行代表的是第6条边
是从③这个顶点指向④这个顶点
出来我们用-1表示
进去的用1
那么可以看到
这个关联矩阵的一个特点
就是它的元素只有0 1 -1
三种情况
每一条每一行只有两个非零元
1和-1
每一列呢
它表示的是经过这个顶点的边
是出来的 从这个顶点出来的
我们用-1表示
从进入这个顶点的
我们用1表示
其他部分就用0
这是关联矩阵
第二种跟图相关的矩阵
我们叫邻接矩阵
那么一个邻接矩阵
它是一个n乘n的矩阵
n就表示顶点的个数
我们还是以上例为
我们来看上例
我们在这儿再画一下上例②
这一个③ ④
这是我们刚才这个例子
刚才这个例子呢
这个第1条边 第2条边
这是第4 第5 第6
第3 第7
那么这个图呢它有四个顶点
那么我们就可以形成一个
4乘4的矩阵
那么这个矩阵的元素怎么取呢
这个元素的第i行第j列的元素
实际上是顶点i到j有多少条边
那么现在这个图呢
从i到j呢我们看只有0边
0条边或1条边这两种情况
所以我们这个矩阵的元素
只有0和1
而注意我们这个边
表示的就是长度为1的路
那比如说大家可以看到
第一行这个1是第1行第2列
那么就是指从第①顶点
指向第②个顶点有一条边
又比如说这个第3行第4列
就表示的是
从第③个顶点指向第④个顶点
那么也有一条边
那么第③个顶点
从它出去的边没有了
所以这三个呢是取0
所以大家看到
如果一个顶点它这个
没有边从它出去
比如说③这个顶点
这种顶点没有边从它出去
那么它所在的
那么我们讨论这一行呢
只有一个非零元
如果一个顶点没有边进去
都是从它出来的
那么我们考虑的某一列
就完全只有一个非零元
其他的都是0
这个叫邻接矩阵
一个定向图呢
我们还可以结合一个
拉普拉斯矩阵
一个拉普拉斯矩阵呢
它等于A＾TA
其中的A
就是我们刚才说的关联矩阵
那大家回忆一下
关联矩阵它的行代表的是边
它的每一列代表的是
每一个顶点的连接情况
每一条边只有
每一行只有一个非零的-1和1
其他地方都是0
那么我们可以看出
这个拉普拉斯矩阵
它的定义是A＾TA
那么根据A的定义我们可以算出
这个拉普拉斯矩阵
第i行第j列的元素
那大家可以想一下
l_ij实际上来自于
A＾T的第i行乘上A的第j列
A＾T的第i行
实际上就是A的第i列
所以l_ij实际上是A的第i列
和第j列的内积
那么我们确切地算一下
就可以看出
A的第i列和A的第j列
分别反映的是
经过i这个顶点的边的情况
第j列分别反映的是
经过j这个顶点的边的情况
大家想如果i和j它们没有边相连
i不等于j i和j没有边相连
那么我们知道A的每一行
代表的是什么意思呢
每一行代表的是
它的非零元代表的是
某一个边的两个顶点
那么如果i和j没相连呢
那么对于任何一条边呢
i和j没有共同的
在这一行有共同的非零元
所以当它们元素相乘的时候
就是0
就是说当这一块我们取一个a
这一块取b的话
那么当a取1的时候
或者a取-1的时候
b必须取0
否则的话 那么i和j呢
实际上就是一条边相连
所以i和j不相邻的时候
那么它只能取0
i和j如果是通过几条边相连的话
那么我们看到l_ij呢
就是它们连接的边数的相反数
如果i等于j呢
那么经过顶点i的边数
那表示l_ij
我们可以看一个具体的例子
比如说这个矩阵
这个矩阵的关联矩阵呢
我们看到 这个矩阵有
这个图有6个顶点 有8条边
那么我们得到的关联矩阵呢
是一个8行6列的
行数代表的是边的个数
列数代表顶点个数
我们使用A＾T乘A
我们可以得到一个拉普拉斯矩阵
那么大家可以看一下具体元素
3代表的是经过①
这个顶点的边数
那么大家可以看到
经过①这个顶点的有3条边
分别是1 3 4这三条边
又比如说我们看这个②
这个是在第4行第4列
那么它代表的是
经过④这个顶点的边数
那么正好是3和7两条边
我们看第5个这个5
是第5行第5列
那么它表示经过⑤
这个顶点的边数
经过⑤这个顶点我们可以看一下
分别是4 5 6 7 8
这5条边都经过⑤这个顶点
所以这个矩阵的对角线元素
确切刻划了经过每一个顶点的边数
跟方向没有关系
在非顶点处比如说这个-1
它在第1行第5列
那么这个代表的是①和⑤
这两个顶点相连的边数的相反数
而另外这样一个图呢
我们还可以结合一个邻接矩阵
因为这个顶点有6个
所以邻接矩阵是6乘6的
那么我们现在也可以看出
这三种矩阵是相互关联的
拉普拉斯矩阵它等于A＾TA
所以它是个半正定矩阵
那么它跟邻接矩阵的关系呢
我们可以通过定义确切看出来
就是当你把L的对角线元素
提出来
这个D就是L的对角线元素
非对角线
大家可以看到L的非对角线元素
部分都是负的
然后把负号提出来呢
它恰好是B加B＾T的形式
所以拉普拉斯矩阵
跟邻接矩阵的关系呢
相当于一个对角阵减去邻接阵
那么大家可以看到矩阵A
这个关联矩阵
它的每一个元素只有两个非零元
-1和1
那么这两个非零元呢
导致了A的每一行的元素之和
是等于0的
所以当你用A
去乘上这样一个列向量
就是全是1
这样一个列向量的时候
乘完的结果相当于每一行求和
那么最后等于零向量
由此我们看到A
它不是一个列满秩的矩阵
所以L它的每一行元素之和
也等于0
因为L乘上这个1 1 1
等于A＾TA乘上1 1 1 1
是等于0的
所以L的每的一行之和也等于0
而且因为A不可逆
或者说A它不是个列满秩的
所以L是一个奇异阵
-1.1 实对称矩阵A正定的充要条件
-1.2 典型例题
--1.2 典型例题
-1.3 半正定矩阵及其判别条件
-1.4 二次型
--1.4 二次型
-1.5* 有心二次曲线(central conic)
-1.6* 三维空间中的二次曲面-6类基本的二次曲面
-1.7 二次型的分类
-1.8 矩阵的合同
-1.9* 惯性定理的证明
-1.10 惯性定理的应用 —— 实对称矩阵的特征值与主元符号
--1.10 惯性定理的应用 —— 实对称矩阵的特征值与主元符号
-1.11* 正（负）定矩阵在函数极值问题中的应用
-第一讲：正定矩阵--课后习题
-2.1 引言
--2.1 引言
-2.2 相似矩阵的性质
-2.3 Jordan标准形
-2.4 定理的证明
-2.5 Jordan标准形的应用
-第二讲：相似矩阵--课后习题
-3.1 引言
--3.1 引言
-3.2 奇异值分解(Singular Value Decomposition)
--3.2 奇异值分解(Singular Value Decomposition)
-3.3 例题
--3.3 例题
-3.4 奇异值分解的应用
-第三讲：奇异值分解--课后习题
-4.1 线性变换的定义和性质
-4.2 线性变换的运算
-4.3 线性变换的矩阵表示
-4.4 线性变换与矩阵之间的关系
-第四讲：线性变换 I--课后习题
-5.1 恒同变换与基变换
-5.2 图像压缩——基变换的应用
-5.3 线性变换在不同基下的矩阵
-5.4 矩阵分解与基变换
-5.5 线性变换的核与像
-5.6 不变子空间
-5.7* 幂零变换
-5.8* Jordan标准形
-第五讲：线性变换 II--课后习题
-6.1 伪逆
--6.1 伪逆
-6.2 Moore – Penrose 伪逆
-6.3 最小二乘法
-第六讲：伪逆--课后习题
-7.1 简介
--7.1 简介
-7.2 弹簧模型
--7.2 弹簧模型
-7.3 变量的线性关系
-7.4 刚度矩阵
--7.4 刚度矩阵
-7.5 从离散到连续
-第七讲：工程中的矩阵--课后习题
-8.1 简介
--8.1 简介
-8.2 图和矩阵
--8.2 图和矩阵
-8.3 网络和加权Laplacian矩阵
-8.4 关联矩阵的四个基本子空间
-8.5 注记
--8.5 注记
-第八讲：图与网络--课后习题
-9.1 问题引入
--9.1 问题引入
-9.2 Markov矩阵
-9.3 正Markov矩阵
-9.4 正矩阵
-第九讲：Markov矩阵和正矩阵--课后习题
-10.1 引言
--10.1 引言
-10.2 内积空间
-10.3 傅里叶级数
-10.4 投影
--10.4 投影
-10.5 关于Fourier变换的注记
-第十讲：Fourier级数--课后习题
-11.1 引言
--11.1 引言
-11.2 平移
--11.2 平移
-11.3 伸缩
--11.3 伸缩
-11.4 旋转
--11.4 旋转
-11.5 投影和反射
-第十一讲：计算机图像--课后习题
-12.1 引言
--12.1 引言
-12.2 复矩阵
--12.2 复矩阵
-12.3 复正规阵
-12.4 离散Fourier变换
-12.5 快速Fourier变换
-第十二讲：复数与复矩阵--课后习题
-结课寄语
--结课寄语
