注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

基尔霍夫定理  

2013-12-26 10:20:56|  分类: 知识点 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

英文叫Kirchhoff's Matrix-Tree Theorem。

基尔霍夫的矩阵树定理……?基尔霍夫定理 - vfleaking - vfleaking的博客

用[P]表示P为真时为1,假时为0。
用e.v,e.u表示边e的两端。
用x^2表示x的平方。
用A^T表示矩阵的转置。

首先我们考虑一棵n个结点的树,假设树上的边为{Ed[k]},那么我们构造一个矩阵:
T[v, k] = | v == Ed[k].v   : 1
          | v == Ed[k].u   : -1
          | otherwise      : 0          1 <= v <= n, 1 <= k <= n - 1
至于Ed[k]中谁当v谁当u其实无所谓……
共n个点n - 1条边,所以这个矩阵是n * (n - 1)的。

好……那么我们现在把它的第一行给删了。
于是变成方阵了233……我们还是称为矩阵T。

举一个栗子:
基尔霍夫定理 - vfleaking - vfleaking的博客
相当于把1号点炸了,与之相连的边还剩个线头。
我们称之为被轰炸了的树。

现在我们来研究一下这个家伙的行列式。
考虑几个初等行列变换,由于每一列代表一条边,所以我们主要关注的焦点在列身上:
把第i列乘以-1:对其所对应的被轰炸了的树没有任何影响。反正E[k]中谁当v谁当u无所谓。
交换两列:行列式的值虽然取反了,但是对被轰炸了的树没有任何影响。反正边不分先后。
把第i列加到第j列上去:这个有点奇葩……但是我们可以考虑特殊情况,就是第i列中值为1的那一行在第j列恰好为-1,这样就成功消了个酱油。即T[u, i] = 1而T[u, j] = -1,相加后T[u, j]消成0。然而第i列中值为-1的那一行(如果有的话),在第j列中一定为0,否则就有重边了。所以在第j列又会添上一个-1。对于被轰炸了的树来说,相当于这样:
基尔霍夫定理 - vfleaking - vfleaking的博客
第j条边从(v, u)变为了(v, w)。
而把第i列乘以-1加到第j列上去也是类似的。
这样一来,我们在被轰炸了的树上把边的一端改到别处去,就可以很开心地对应到行列式里的操作。而把第i列的值乘以k加到第j列上去行列式的值不变。

于是我们把刚才那棵被轰炸了的树玩一玩:
基尔霍夫定理 - vfleaking - vfleaking的博客
这样我们把所有的边的其中一端都炸飞了。
严格地说,我们可以这样玩:以已经被炸飞的1的灵魂为根,把每个结点连向父亲的那条边的父亲那一端炸飞。顺序从上到下,每次都通过自己已炸飞的父亲的边的线头让自己连向父亲的那一端变为线头。
这意味着什么?我们把行列式的列疯狂地交换一下,把某些列乘以-1,就得到了:
基尔霍夫定理 - vfleaking - vfleaking的博客
反正一开始的时候给定的边的顺序是任意的,也不好说det(T)到底是1还是-1吧……
我们索性写成det(T)^2 = 1好了。

这有什么用呢?其实我们得到了一个判断一个图是否是树的装置。
我们设一个n个点m条边的图G的边集是{Ed[k]}。定义G的神奇关联矩阵E
E[v, k] = v == Ed[k].v   : 1
          | v == Ed[k].u   : -1
          | otherwise      : 0          1 <= v <= n, 1 <= k <= m
当然了,m != n - 1的话肯定不是树了……我们仅考虑m == n - 1的情况。
把E的第一行给炸了。
这样我们得到E'
如前所述,如果G是一棵树,那么det(E')^2 = 1。
要是不是树呢?
那么一定有环。好……如前所述,我们一定能把一个环上的边的端点乱改一通,从环上某一点v开始把环上的其它边的一段炸到v上去。
这样制造了一条重边!
在行列式里啥意思?随便乘以一下-1调整一下,就发现有两列相等!
于是根据行列式性质,det(E') = 0。
显然det(E')^2 = 0了。

1和0不是超开心?
1就是方案数++,0就是不管。
我们记一个图G的神奇关联矩阵为E(G),炸了一行的神奇关联矩阵为E'(G)。具体炸哪一行其实无所谓。
所以我们可以搞一个超大的式子算最后答案:
基尔霍夫定理 - vfleaking - vfleaking的博客
但是我们完全可以写得更开心一点:
基尔霍夫定理 - vfleaking - vfleaking的博客
注意我在某个神奇的地方加了个转置。为啥要这么干呢……
因为这个!
基尔霍夫定理 - vfleaking - vfleaking的博客
我们把几个矩阵神奇地拼成一个大矩阵。
其中I表示的是一个m*m的单位矩阵。
举一个栗子:
基尔霍夫定理 - vfleaking - vfleaking的博客
然后就帅气了。基尔霍夫定理 - vfleaking - vfleaking的博客
为了方便起见,我们令A = E'(G), B = E'(G)^T。令n' = n - 1
M = |A  0|
    |-I B|
这究竟是是个啥?
根据行列式的那个啥定义,我们要选取所有排列p,然后把M[i, p[i]]乘起来再乘以(-1)^(p中逆序对个数)加起来。
形象地说就是在这个方阵中摆m + n'个车,使之不能互相攻击。对于每个车来说,它要统计位于它右上方的车的数目,然后加起来就是逆序对。
我们把M的那四块用虚线分格的区域分别称作左上,右上,左下,右下。同时也称呼前n'行、后m行,前m列、后n'列表示横、竖虚线划分开的区域。
那么由M的样子知道……由于M的右上全是0,所以前n'行的车一定要放在左上才会对结果有贡献,也就是说在前m列中选n'列出来。
那么现在到了后面的m行,列已经被瓜分了n'列走了,前m列还剩m - n'列,后半部分保存完好。
注意此时还是不能轻举妄动,因为车只要放在0上就sb了。
所以如果单位矩阵第i列未被取走,那么要有个车放在它的第i行第i列,也就是M的第n' + i行第i列。否则一定会导致有个倒霉车放在0上。
而剩下来的行,若编号为n' + i,一定是第i列已在前n'行放了车的。那么该行位于左下的唯一一个非0项已经不能放车了,于是它一定只能在后n'列放车。

于是我们好像发现了什么?
假设我们已经选好了前n'行要放车的n'列,那么也就在后m行中删去了m - n'行使得只剩下了n'行,贡献了m - n'个-1。于是剩下前面的那n'行随意放,后面删剩下的那n'行随意放车
相当于说,我选好了n'列后,把大家都删干净了,A变成一个n'*n'的A'了,B变成一个n'*n'的B'了,然后这部分对答案的贡献就变成了:det(A') * det(B') * (-1)^(m - n' + 一些额外的逆序对数)
现在我们来考察“一些额外的逆序对”。假设我们将我们选取的那n'列以及因此被选中的n'行全染成黑色,其它为白色。那么我们得到了n'个竖着的黑条条和n'个横着的黑条条。
对于每个来说,它要统计位于它右上方的车的数目,然后加起来就是逆序对。
在det(A')中摆的车一定在det(B')中摆的车的左上方,可以无视。
关键要关注的就是单位矩阵里所有主对角线上的白色格子。它们都是要放车的。考虑其中一个格子v的右上方。显然,如果右上方的车是det(A')里的,那么它所在的竖着的黑条条一定在v的右边。如果右上方的是det(B')里的,那么它所在的横着的黑条条一定在v的上边。反着证回去就可以发现这是充要的。这样格子v对答案的贡献就是右边的竖着的黑条条 + 上边横着的黑条条 = n'
所以:
一些额外的逆序对数 = 单位矩阵里主对角线上的白色格子数 * n' = (m - n') * n'
所以选好n'列后对答案的贡献是:
  det(A') * det(B') * (-1)^(m - n' + (m - n') * n')
det(A') * det(B') * (-1)^(m + m * n' - (n' + 1) * n')
det(A') * det(B') * (-1)^(m + m * n')
det(A') * det(B') * (-1)^(m * (n' + 1))
事实上n'列我是可以随意取的,取遍所有可能的m列中取n'列的组合后,就是答案。
所以我们就推得了一个神奇的结论:
假设矩阵A是n * m,矩阵B是m * n,且m > n
则:
基尔霍夫定理 - vfleaking - vfleaking的博客
其中:
A[n*S]表示把A的m列删成只有编号属于S的列。
B[S*n]表示把A的m行删成只有编号属于S的行。
M = |A  0|
    |-I B|

还能更简洁么……
当然可以……
det(M) = |A  0|
         |-I B|
       = | 0 AB|
         |-I B |
看起来是以矩阵为一个整体消元……其实是狂用“一行乘以k加到另一行上去,行列式的值不变”的性质。
然后我们给它们换一下位置:
|AB  0|
| B -I|
这里是把n列提到前面去了。相当于每次提一个到前面去,重复n次,于是由于交换两列导致的正负号变化为:
(-1)^(n * (n + m - 1)) = (-1)^(n * (n - 1) + n * m) = (-1)^(n * m)
那么我们现在得到的是个啥……
AB是n*n的,-I是m*m的。
要想一个排列对行列式的值的贡献不为零,那么前n行不能取到右边的0那里去,所以只能在AB中玩。于是后m行也就只能在-I中玩了。
这样,实际上:
det(M) = (-1)^(n * m) * det(AB) * det(-I)
而det(-I) = (-1)^m
所以det(M) = (-1)^(m * (n + 1)) * det(AB)
(-1)^(m * (n + 1))之前见过吧……基尔霍夫定理 - vfleaking - vfleaking的博客
于是我们就得到了柯西比内公式:
基尔霍夫定理 - vfleaking - vfleaking的博客
我废话那么多是干什么的?这样我们证明了:
基尔霍夫定理 - vfleaking - vfleaking的博客
于是我们只要求出E'(G)(E'(G)^T)这个矩阵,然后求出它的行列式就行了!
那么E'(G)(E'(G)^T)到底是个*?以下把E(G)简写为E
不妨来看E(E^T),因为E'比E少一行,所以最后乘积会少一行一列,所以先研究E(E^T),然后删去第1行第1列就是。(当然根据前面的推导,你删第2行第2列其实也行……反正不会影响行列式的值)
再来回顾E是啥:
E[v, k] = v == Ed[k].v   : 1
          | v == Ed[k].u   : -1
          | otherwise      : 0          1 <= v <= n, 1 <= k <= m
设L=E(E^T)
则:L[v, u] = sum(E[v, k]E[u, k])     1 <= k <= m
只要E[v, k]和E[u, k]中一个为0就对答案无贡献了。
所以我们貌似知道这到底是在干啥了……
v = Ed[k].v, u = Ed[k].v时,C[v, v]++
v = Ed[k].v, u = Ed[k].u时,C[v, u]--
v = Ed[k].u, u = Ed[k].v时,C[v, u]--
v = Ed[k].u, u = Ed[k].u时,C[u, u]++
所以其实L这个矩阵啊………设mat[v][u] = v与u间边的数量, deg[v] = v的度数。
他是这样的:
L[v, u] = | v != u  : -mat[v][u]
          | v == u  : deg[v]
即L = 度数矩阵 - 邻接矩阵
L我们称之为拉普拉斯矩阵。(怎么拉普拉斯的变换也神、算符也神、矩阵也神……)

所以我们花了一番周折,得到了基尔霍夫定理:
【基尔霍夫定理】一个无向图G的生成树个数为det(L')。其中L'是G的拉普拉斯矩阵去掉第i行第i列的矩阵(1 <= i <= n)。至于i具体是几其实无所谓。

呼啦啦……搞完了……基尔霍夫定理 - vfleaking - vfleaking的博客
  评论这张
 
阅读(3723)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017