谱图与代数图论读书笔记7

Aug 23, 2020 00:00 · 447 words · 3 minute read graph math spectral algerbraic graph theroy

这两章定义了两个物理上的知识，通过定义等效电阻来表征一个电阻网络的性质以及特点。

walk，spring and resistor networks

调和函数

对于一个图$ G = (V,E,\omega) $，以及一个边界的点集$ B \subseteq V $，其他的点组成一个点集$ S = V - B $，同时，假定图为连通图并且B不为空，对于一个函数$ x:V \rightarrow R $并满足$ x(a) = \dfrac{1}{d_a}\sum_{b~a}w_{a,b}x(b) $即在x(a) 是a的邻居节点的值的加权平均。

图上的随机游走

我们对于一个标准的图G以及标准的游走矩阵，每一个点a往其邻居移动的概率为$ w_{a,b}/d_a $ ，设开始节点为a结束节点为s而不经过t那么对于一次游走而言，$ x(s) = 1,x(t) = 0$对于另外的一些节点，我们可以有:

$$ x(a) = \dfrac{1}{d_a}\sum_{b~a}w_{a,b}x(b) $$

很明显，x就是$ V - B $的每一个节点的调和函数，例如在一个path graph中，$ s = n,t = 1 $那么我们有$ x(n) = 1,x(1) = 0 $，那么很简单构造调和函数的一个解$ x(a) = \dfrac{a-1}{n-1} $，这个解意味着对于从1开始的一次游走在n点停止的概率是此解。

对于懒散随机游走，我们也可以得到这样的一些解，比较简单就不在赘述。

网络

弹性网络以及电阻网络其实都是差不多的网络，所以在这里一起进行说明。

根据小学二年级教的胡克定律，我们可以得到$ F = xa $，首先假设弹性系数为1，那么我们知道$ x(a)-x(b) $就是各个点所受的力，对于一个网络中间的点来讲，每一个点的受力都是平衡的，于是很简单的列出:

$$ \sum_{a~b}(x(a) - x(b)) = 0 \Leftrightarrow \sum_{a~b}x(b) = d_ax(a) \ \ \ \ （1） $$

如果边上的权值不为1即变得弹性系数不是1，那么我们可以得到类似调和函数的式子$ x(a) = \dfrac{1}{d_a}\sum_{b~a}w_{a,b}x(b) $。

对于电阻网络，我们有同样的性质，我们根据欧姆定律$ V = IR $可以得到$ i = V * 1/R $，并且V代表的是电势差，即$ v(a) - v(b) $，于是我们可以得到

$ i(a,b) = \dfrac{1}{r_{a,b}}(v(a)-v(b)) = w_{a,b}(v(a)-v(b)) $

由于电流与弹力不同，是有方向的，$ i(b,a) = -i(a,b) $为了将电流表示为矩阵相乘的形式，我们定义带符号边顶点邻接矩阵

$$ U((a,b),c) = \begin{cases}1 \ \ \ \ \ if \ a=c \\ -1 \ \ \ if \ b=c \\ 0 \ \ \ otherwise \end{cases} $$

U的每一行有$ U((a,b),:) = \delta_a^T-\delta_b^T $

定义另一个对角矩阵W为对角矩阵并且其列和行由边以及对角线上的边权重所决定。

这样我们就有了$ i = WUv $，U的目的主要是向W提供一个符号，而W其作用是表征电阻网络中的各向电阻。

使$ i_{ext} = \mathbb{R}^V $作为外部电流，也就是说$ i_{ext}(a) $就是整张图流向a的电流之和，于是就有了$ i_{ext}(a) = \sum_{b~a}i(a,b) $

用矩阵形式表示，就是$ i_{ext} = U^Ti = U^TWUv $

根据第三章的内容，我们将拉普拉斯矩阵可以写作$ L = U^TWU $，那么对于任何一个节点，$ i_{ext} = Lv $，对于一个无权图以及一个内部节点a，$ i_{ext}(a) = (\delta_a^TL)v = d_av(a) - \sum_{a~b}v(b) = 0 $,很明显v在a上也是一个调和函数。

回到弹性网络的体系中，改写（1）式可以得到$ d_ax(a) - \sum_{b\notin B:(a,b)\in E}w_{a,b}x(b) = \sum_{b\in B:(a,b)\in E}w_{a,b}x(b) $

对于每一个在B中的点，设满足$ f(a) $，那么上式就可以进一步被改写，对于上式左边部分，写成矩阵的形式就是$ L(S,S)x(S) = r $，r被定义为$ M(S,:)f $，$ L(S,S) $代表的是包含在S中的L的一个子图，用矩阵的等式表示为$ L(S,S) = L_{G(S)}+X(S) $，$G(S)$是子图，而$ X(S) $是对角矩阵并且相应的元素是权重的和。对于L的子矩阵，由于L是正定的并且对称的，我们可以知道$ L(S,S) $一定是对称的，另外，也是正定的。

摩尔·彭罗斯广义逆（moore-penrose pseudo-inverse）

对于一个矩阵满足：

  1. AGA = A, AG 不一定是单位矩阵但是一定不会改变A的列向量。
  2. GAG=G, G是乘法半群的弱逆
  3. $(AG)^H = AG$，AG是埃尔米特矩阵
  4. $ (GA)^H = GA $，GA也是埃尔米特矩阵

于是称G为摩尔彭罗斯广义逆，将其简称为广义逆，对于逆，我们具有一些性质：

  1. $ (A^H)^+ = (A^+)^H $
  2. $ A^+AA^H = A^HAA^+ = A^H $
  3. $ AA^H(A^H)^+ = (A^H)^+A^HA = A $
  4. $ A^+A,AA^+,(I-A^+A) $都是幂等矩阵

effective resistance and schur complement

有效电流与有效电阻

根据上面有关电压的表述，我们可以得到$v = L^+i_{ext} $当$ i_{ext} $为从a流向b的单位电流，这样可以把该式重新写作：

$$ v = L^+(\delta_a - \delta_b) $$

$$ v(c) - v(d) = (\delta_c - \delta_d)^Tv = (\delta_c - \delta_d)^TL^+(\delta_a - \delta_b) $$

由于$ i(a,b) = \dfrac{v(a)-v(b)}{r_{a,b}} $ 并且电流为单位电流，所以我们有：

$$ R_{eff}(a,b) = (\delta_a - \delta_b)^TL^+(\delta_a-\delta_b) $$

将$ L^+ $的平方根写作$ L^{+/2} $于是上式可以接着画，从而证明等效阻值是$ L^{+/2} $从a到b的欧式距离的平方：

$$ (\delta_a - \delta_b)^TL^+(\delta_a-\delta_b) = ((L^{+/2}(\delta_a - \delta_b))^TL^{+/2}(\delta_a-\delta_b)) = ||L^{+/2}(\delta_a-\delta_b)||^2 $$

在这里设计两个简单的图来说明等效电阻的性质：

  1. 串联（series）通过串联多个电阻，我们可以根据上面的式子得到$ r = r_{1,2}+…+r_{n-1,n} $
  2. 并联（parallel）通过并联电阻，阻值为$ \dfrac{1}{1/r_1+…+1/r_n} $

等效电阻同时也有很多性质：

  1. $ \delta(a,a) = 0 $
  2. $ \delta(a,b) \geq 0 $
  3. $ \delta(a,b) = \delta(b,a)$
  4. $ \delta(a,c) \leq \delta(a,b) + \delta(b,c) $

高斯消元与舒尔补

B是一个图上的边界点组成的点集 ，$v(B)$是B上的电压组成的向量，对于矩阵$ L_B $，可以得到$ i_B = L_Bv(B) $。

$ L_B $事实上是一个拉普拉斯矩阵，并且是经过高斯消元后形成的矩阵，高斯消元是一种通过乘除加减来消去矩阵的值的方法，在这里对其加以证明：

首先一个图$ G = (V,E,w) $，设$ B = {2,…,n} $那么中间的节点就只有去，那么$ v(1) = \dfrac{1}{d(1)}\sum_{a\in N}w_{1,a}v(a) $ 。

对于节点b，有$ i_{ext}(b) = d(b)v(b)-\sum_{c~b}w_{b,c}v(c)$，将1提出来，$ i_{ext}(b) = d(b)v(b) - w_{1,b}v(1)-\sum_{c~b,c\neq 1}w_{b,c}v(c) $将上面的$ v(1) $带入这式子，并进行展开:

$$ i_{ext}(b) = d(b)v(b) - \sum_{a\in N}\dfrac{w_{b,1}w_{a,1}}{d(1)}v(a) - \sum_{c~b,c\neq 1}w_{b,c}v(c) $$

将第二个小狮子的a=b提出来，这样凑出来了L：

$$ i_{ext}(b) = d(b)v(b) - (w_{b,1}^2/d(1))v(b) - \sum_{a\in N,a\neq b}\dfrac{w_{b,1}w_{a,1}}{d(1)}v(a) - \sum_{c~b,c\neq 1}w_{b,c}v(c) $$

采用矩阵形式来表示我们可以进行推倒，无非是设$ v^TLv = v(B)^TL_Bv(B)$经过计算后得到$ L_B = L(B,B) -\dfrac{L(B,1)L(1,B)}{L(1,1)} $

矩阵方式比上述方法直观，我们之后就对矩阵进行拓展，移除S的点后，得到$ L(B,B)-L(B,S)L(S,B)L(S,S)^{-1} $这被称为schur complement。