Java教程

计算方法5 图的代数性质

本文主要是介绍计算方法5 图的代数性质,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

感觉这部分穿插的有些怪

前置

对于实对称矩阵 \(A\),其最大特征值 \(\lambda_\max(A)\geq \frac{x^\intercal Ax}{x^\intercal x}\),其中 \(x^\intercal x\neq \bold 0\)

证明:

\(A\) 实对称,因此存在一组单位正交基恰好为特征向量 \(V=(v_1,v_2\ldots v_n)\)。设 \(x\) 在 \(V\) 下的坐标为 \(u=(u_1,u_2\ldots u_n)^\intercal\),则

\[\begin{aligned} \frac{x^\intercal Ax}{x^\intercal x}&=\frac{(Vu)^\intercal A (Vu)}{(Vu)^\intercal(Vu)} \\ &=\frac{u^\intercal (V^\intercal AV)u}{u^\intercal (V^\intercal V)u} \\ &\le \lambda_\max\frac{u^\intercal u}{u^\intercal u}=\lambda_\max \end{aligned} \]

最后一个不等号要用到 \(V\) 正交,再把 \(V^\intercal AV\) 的所有特征值放成最大特征值。等号在 \(x\) 为属于特征值 \(\lambda_\max\) 的特征向量时取到。

图的代数性质

即对于给定的图 \(G\),通过观察 \(G\) 的邻接矩阵/拉普拉斯矩阵的性质来获得某些 \(G\) 的性质。

邻接矩阵

记为 \(A\),规定 \(A_{x,y}=[xy\in E(G)]\),其中 \([\cdot]\) 为指示函数。

\(A\) 还可以写成如下形式

\[A=\sum_{xy\in E(G)} A^{(xy)} \]

其中 \({A^{(xy)}}_{x,y}=1\) 其余位置皆为 \(0\)。即一张图的邻接矩阵可以由所有的边的邻接矩阵拼起来。

特征值

\(\lambda_\max(A_G)\leq d_\max(G)\)

不妨设最大特征值为 \(\lambda\),属于 \(\lambda\) 的特征向量 \(x\) 的绝对值最大的分量为 \(x_i\)(不妨设 \(x_i>0\)),那么有

\[\lambda x_i=(\lambda x)_i=(Ax)_i=\sum_{j=1}^n A_{i,j}x_j\leq x_i\sum_{j=1}^n A_{i,j}=d(i)x_i \leq d_\max(G) x_i \]

\(\lambda_\max(A_G)\geq d_{\text{avg}}(G)\)

只需要用到前置中的定理,令 \(x=(\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}}\ldots \frac{1}{\sqrt{n}})^\intercal\) 即可。

拉普拉斯矩阵

也叫调和矩阵,在矩阵树定理里面叫做基尔霍夫矩阵。

规定 \(L=D-A\),其中 \(D=\text{diag}\{d_1,d_2\ldots d_n\}\) 是度数对角阵。

\(\bold 1\) 是 \(L\) 的一个特征向量,对应特征值为 \(0\)。即 \(L\bold 1=\bold 0\)

证明:拆开即得。

剩下的咕咕咕

这篇关于计算方法5 图的代数性质的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!