2020-2021:teams:farmer_john:jjleo:矩阵树定理
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:矩阵树定理 [2020/06/25 23:15] jjleo |
2020-2021:teams:farmer_john:jjleo:矩阵树定理 [2020/08/12 17:25] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =======矩阵树定理======= | =======矩阵树定理======= | ||
| * <del>数学太菜，不会证明。</del> | * <del>数学太菜，不会证明。</del> | ||
| - | * 对于无向图，基尔霍夫矩阵的任意一个主子式是所有生成树边权权值之积的和。基尔霍夫矩阵构造方法如下，对于一条连接$x,y$权值为$z$的边，令$a_{xx}+=z,a_{yy}+=z,a_{xy}-=z,a_{yx}-=z$即可。 | + | * 对于无向图，基尔霍夫矩阵的任意一个余子式是所有生成树边权权值之积的和。基尔霍夫矩阵构造方法如下，对于一条连接$x,y$权值为$z$的边，令$a_{x,x}+=z,a_{y,y}+=z,a_{x,y}-=z,a_{y,x}-=z$即可。 |
| - | * 对于有向图，基尔霍夫矩阵的任意一个主子式是所有生成树权值之积的和。基尔霍夫矩阵构造方法如下，对于一条连接$x,y$权值为$z$的边，令$a_{xx}+=z,a_{yy}+=z,a_{xy}-=z,a_{yx}-=z$即可。 | + | * 对于有向图，基尔霍夫矩阵$a_{x,x}$对应的余子式是以$x$点为根生成的根向/叶向生成树边权权值之积的和，根向就是所有边指向根节点，叶向就是所有边指向叶节点。基尔霍夫矩阵构造方法如下，对于一条由$x$指向$y$权值为$z$的边，令$a_{x,y}-=z$，根向则$a_{x,x}+=z$，叶向则$a_{y,y}+=z$即可。 |
2020-2021/teams/farmer_john/jjleo/矩阵树定理.1593098113.txt.gz · 最后更改: 2020/06/25 23:15 由 jjleo
