算法合集之生成树的计数及其应用.ppt

算法合集之生成树的计数及其应用
第1页，共31页，编辑于2022年，星期一
引入
最小（大）生成树
最小（大）度限制生成树
最优比率生成树
……
生成树
生成树的计数
第2页，共31页，编辑于2022年，星期一
[一个无向图G，它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值。
所谓n-1阶主子式，就是对于任意一个r，将C的第r行和第r列同时删去后的新矩阵，用Cr表示。
第9页，共31页，编辑于2022年，星期一
Matrix-Tree定理
让我们通过一个例子来解释一下定理。如图所示，G是一个由5个点组成的无向图。
它的Kirchhoff矩阵C为
第10页，共31页，编辑于2022年，星期一
Matrix-Tree定理
我们取r=2，根据行列式的定义易知|detC2 | =11，这11颗生成树如下图所示。
这个定理看起来非常“神奇”，让我们尝试着去证明一下吧！
第11页，共31页，编辑于2022年，星期一
定理的证明
经过分析，我们可以发现图的Kirchhoff矩阵C具有一些有趣的性质：
C的行列式总是0。
如果图是不连通的，则C的任一个n-1阶主子式的行列式均为0。
如果图是一颗树，那么C的任一个n-1阶主子式的行列式均为1。
证明略。
第12页，共31页，编辑于2022年，星期一
定理的证明
我们知道，C=BBT，因此，我们可以把C的问题转化到BBT上来。
设Br为B去掉第r行得到的矩阵，容易知道Cr =Br Br T。这时，根据Binet-Cauchy公式，我们可以将Cr的行列式展开。
其中， 是把Br中属于x的列抽出后形成的新矩阵。
第13页，共31页，编辑于2022年，星期一
定理的证明
注意观察上面的式子， 实际上是图Gx的Kirchhoff矩阵的一个n-1主子式。其中Gx是由所有的顶点和属于x的边组成的一个G的子图。
若属于x的n-1条边形成了一颗树时，由Kirchhoff矩阵的性质可知 等于1。
若属于x的n-1条边没有形成树，则Gx中将至少含有两个连通块，这时 等于0。
因此，我们认为：每次从边集中选出n-1条边，若它们形成了生成树，则答案加1，否则不变。
第14页，共31页，编辑于2022年，星期一
定理的理解
当x取遍边集所有大小为n-1的子集后，我们就可以得到原图生成树的个数。这样我们成功证明了定理！
刚才的证明过程看起来有些“深奥”，下面就让我们从直观上来理解一下这个定理的原理。
第15页，共31页，编辑于2022年，星期一
定理的理解
试求方程
x1 +x2 + x3 =2
所有非负整数解的个数。
这是大家都很熟悉的一道组合计数问题。
通常的解法是，设有2个1和两个△，我们将这4个元素任意排列，那么不同的排列的个数就等于原方程解的个数，即 。
为什么要这样做呢？
第16页，共31页，编辑于2022年，星期一
定理的理解
我们将所有6种排列列出后发现，一种排列就对应了原方程的一个解：
△ △ 11对应x1=0，x2=0，x3=2
△ 1 △ 1对应x1=0，x2=1，x3=1
△ 11 △对应x1=0，x2=2，x3=0
……
也就是说，我们通过模型的转化，找出了原问题和新问题之间的对应关系，并利用有关的数学知识解决了转化后的新问题，也就同时解决了原问题。
这种转化的重要意义在于：在不同问题之间的架起了互相联系的桥梁。
第17页，共31页，编辑于2022年，星期一
定理的理解
回到我们讨论的Matrix-Tree定理上来。
我们同样是经过模型的转化后（将图模型转化为矩阵模型），发现Binet-Cauchy公式展开式中的每一项对应着边集一个大小为n-1的子集。其中，值为1的项对应一颗生成树，而没有对应生成树的项值为0。这样，将问题转化为求展开式中所有项之和。再利用已有的数学知识，就可以成功解决这个问题。
第18页，共31页，编辑于2022年，星期一
两个问题的对比
方程的解
图的生成树
类似
排列方案
展开式的项
类似
对应
对应
不同之处在于：
相互之间的对应关系更加隐蔽、复杂
需要更加强大的数学理论来支撑
第19页，共31页，编辑于2022年，星期一
定理的扩展
利用该定理，我们可以容易得到著名的Cayley公式：完全图Kn有nn-2颗生成树。
我们刚才只对图中没有重边的情况进行了分析。实际上，图中有重边时该定理仍然成立，并且证明与没有重边的情况类似。
该定理也可以扩展到有向图上，用来计算有向图的外向树的个数。
第20页，共31页，编