$Matrix-Tree$
矩阵的行列式
这个东西看了好久才明白 _ (:з」∠)_ 时间不够可以直接跳到第六段。
看到这种新定义，第一反应还是去翻百度百科：
但是这个讲解真的让人很迷惑...关键就是第二段的开头，突然出现了“n阶行列式”这么一个词，我到现在也没有明白...在这个地方好像就是“n阶矩阵”的意思？而且它还出现了奥妙重重的递归计算，导致完全看不懂行列式到底是个什么东西。
点开一个叫做“余子式”的词条，里面有这么一句话：
“行列式的阶越低越容易计算，于是很自然地提出，能否把高阶行列式转换为低阶行列式来计算。”
这才像话嘛，虽然没有说行列式是什么，但是至少说明了为什么一上来就是一通递归。后来又看了一些资料，发现行列式的关键是“式”，而不能将它简单地认为是一个数，否则很难理解。首先二维矩阵的行列式相当于叉积，三维矩阵的行列式也有几何意义，就是一个平行六面体的体积。所以说了这么多还是不知道行列式是什么啊
${det(K)=}\sum_{P}^{ }\;{(}{(-1)}^{\tau{(P)}}\times{K}_{1,p1}\times{K}_{2,p2}\times{K}_{3,p3}\times\cdots\times{K}_{N,pN}{)}$
然后找到这么一个式子，也是算行列式的，这里面 $P$ 是一个$1-n$ 的排列， $\tau{(P)}$ 表示排列 $P$ 的逆序对数目。
其实上面那些都没什么用处，毕竟最后我也没弄明白...其实学这些关键还是要用，所以跳过证明，直接看结论：
1.交换矩阵的两行或两列，行列式变号；
2.如果矩阵有两行或两列完全相同，行列式为0；
3.将矩阵某行或某列的所有元素同乘以k后，行列式的值也乘以k；
4.将矩阵的某一行/列加上另一行/列的k倍，行列式的值不变；
有了这些结论，事情就变得非常简单。将矩阵用高斯消元消成一个上三角矩阵，发现一个有趣的性质：
上三角矩阵的行列式是对角线的乘积；
这里要用到的是最复杂的那个行列式，当且仅当 $P$ 为 $1$ $2$ $3$ $4$ $...$ 时，连乘的那些项中才会没有 $0$ ，所以就可以很简单的求出行列式的值了。可喜可贺！
$Matrix-Tree$
别忘了今天的主题是什么呀...
首先看一个新概念：$Kirchhoff$ 矩阵；为了理解它，还要复习两个比较简单的旧概念：
度数矩阵：一个 $N \times N$ 的矩阵，其中 $D[i][i]$=$i$ 的度数；
邻接矩阵：一个 $N \times N$ 的矩阵，其中 $A[i][j]$=$i,j$ 间的边数；
$Kirchhoff$ 矩阵：$K=D-A$
事情突然变得简单起来....先求出$Kirchhoff$ 矩阵，任意删掉一行一列，再求行列式，就是生成树的个数啦！是不是非常神奇呢？复杂度 $O(n^3)$。
对于用这种方法求出来的值，我们还可以有另一种理解方式：
$\sum_T\prod_{e \in T} \omega_e$
这个式子的意思是，枚举每棵可能存在的生成树，将边的存在性相乘，如果每条边都存在，也就是一棵生成树，答案就加一。有了这个式子，就可以扩展出一些有趣的东西来了。
随机推荐
-
使用Asp.Net Core MVC 开发项目实践[第二篇:EF Core]
在项目中使用EF Core还是比较容易的,在这里我们使用的版本是EF Core 2.2. 1.使用nuget获取EF Core包 这个示例项目使用的是SQLSERVER,所以还需要下载Microsof ...
-
[转]git提交代码时遇到代码库有更新以及本地有更新的解决方法
本文转自:https://blog.****.net/myphp2012/article/details/80519156 在多人协作开发时,经常碰到同事把最新修改推送到远程库,你在本地也做了修改,这 ...
-
VS2015企业版专业版密钥
亲测可用,有需要的可以mark一下! 专业版:HMGNV-WCYXV-X7G9W-YCX63-B98R2企业版:HM6NR-QXX7C-DFW2Y-8B82K-WTYJV
-
minitab的鱼骨图的制作
Minitab的操作路径为:主菜单Stat > Quality Tools > Cause-and-Effect 先分别选择列"Man.Machine.Material.Meth ...
-
yum 安装 php5.6.36
PHP安装测试可以 rpm -Uvh http://ftp.iij.ad.jp/pub/linux/fedora/epel/6/i386/epel-release-6-8.noarch.rpm; rp ...
-
php soapclient 超时 设置
用php的soapclient,默认是60秒.可在php.ini里配置, 重启APache 或者在PHP代码里做设置 ini_set('default_socket_timeout', 300);// ...
-
loadrunner 运行脚本-Run-time Settings-Browser Enmulation设置详解
运行脚本-Run-time Settings-Browser Enmulation设置详解 by:授客 QQ:1033553122 浏览器模拟 所有Internet Vuser Header包含一个标 ...
-
聊聊setTimeout和setInterval线程
在聊setTimeout和setInterval这两个事件的前,先聊另外一个与之密切关联的知识点,那就是线程(thread).而线程有常常跟另外一个词语--“进程”一起出现.那么何为线程?何为线程呢? ...
-
[Android] 设置AlertDialog中按钮的可用(Enable)状态
弹出一个保存文件的对话框,要控制输入内容限制,同时内容为空时保存按钮不可用. 原文地址请保留http://www.cnblogs.com/rossoneri/p/4140184.html 直接上代码: ...
-
(后台)详细了解java中的null(转)
转自****: 相信大家对于NullPointException 这个让人又爱又恨的不陌生吧..对于Java程序员来说,null是令人头痛的东西.时常会受到空指针异常(NPE)的骚扰 .今天我们就来谈 ...